人工智能原理复习3
Informed Search
Blind search vs. “warmer” “colder”
Info about where goal is.
Optimal solution, explore less of the tree.
Search Heuristics
A heuristic is:
A function that estimates how close a state is to a goal
Designed for a particular search problem
Pathing?
Examples: Manhattan distance, Euclidean distance for pathing
Function takes a state, returns a number.
Not everyday term. Not “Look both ways before you cross the
street”
How far I am? Could run search, but that defeats the purpose!
Not perfect, but something!
A* expanded 8100 ; Path cost = 33
UCS expanded 25263 . Path cost = 33
Greedy expanded 10 . Path cost = 41
[0, 7, 5, 3, 2, 1, 4, 6]
(7, 0, 5, 3, 2, 1, 4, 6)
(6, 4, 1, 2, 3, 5, 0, 7)
(3, 2, 1, 4, 6, 5, 0, 7)
(1, 2, 3, 4, 6, 5, 0, 7)
(5, 6, 4, 3, 2, 1, 0, 7)
(6, 5, 4, 3, 2, 1, 0, 7)
(0, 1, 2, 3, 4, 5, 6, 7)
Expand the node that seems closest…
Is it optimal?
No. Resulting path to Bucharest is not the shortest!
Numbers of heuristic, since that’s what greedy cares about.
Got to Bucharest, but not by shortest path.
End up with some kind of goal, but not what you want. You get a smelly
shoe instead of to the airport on time.
Strategy: expand a node that you think is closest to a goal state
Heuristic: estimate of distance to nearest goal for each state
A common case:
Best-first takes you straight to the (wrong) goal
Worst-case: like a badly-guided DFS
A* Search
What we’ve been building to. Cornerstone. Goes to the goal like
greedy, but backtracks as needed.
When it works, it’s magic!
Uniform-cost orders by path cost, or backward cost g(n)
Greedy orders by goal proximity, or forward cost h(n)
A* Search orders by the sum: > f(n) = g(n) + h(n)
UCS. Cumulative cost of arcs back to root. backward cost g(n). Computed as you go as part of the fringe.
Greedy. Heuristic forward cost h(n). NOT cumulative. Just a function of the state.
What is A*. Sum of the two! Doesn’t go to c early cuz h is high (far from goal).
Doesn’t do a->e branch g is high (expensive).
When should A* terminate?
No: only stop when we dequeue a goal
Inadmissible (pessimistic) heuristics break optimality by trapping good plans on the fringe
Admissible (optimistic) heuristics slow down bad plans but never outweigh true costs
If heuristic lies, and overestimates. Mistake.
Underestimate might reduce to UCS.
Coming up with admissible heuristics is most of what’s involved in using A* in practice.
Optimality of A* Tree Search
UCS ragged based on cost.
A* narrows when near goal, heuristic
Uniform-cost expands equally in all “directions”
A* expands mainly toward the goal, but does hedge its bets to ensure optimality
Change problem – same or easier. And cheaper.
Imagine a new direct road.
Walk through walls spell.
Inadmissible – a little bit suboptimal is okay.
Another relaxation, but “harder” than previous.
Lower bound.
Show it’s relaxed or prove.
At LEAST 18 away.
As heuristic gets close to the true cost, you do less search.
Looks great. Each node launches search as hard as the original
problem.
You’ll might see this in P1. Come up with great heuristic, makes
solution slower.
Graph Search
Failure to detect repeated states can cause exponentially more work.
Exponential unrolling. Generally what happens.
May need to consider both paths to B, but what’s underneath B is the
same.
Should be able to save the work.
Idea: never expand a state twice
How to implement:
Tree search + set of expanded states (“closed set”)
Expand the search tree node-by-node, but…
Before expanding a node, check to make sure its state has never been
expanded before
If not new, skip it, if new add to closed set
Important: store the closed set as a set, not a list
Can graph search wreck completeness? Why/why not?
How about optimality?
A*: Summary
A* uses both backward costs and (estimates of) forward costs
A* is optimal with admissible / consistent heuristics
Heuristic design is key: often use relaxed problems
Optimality of A* Graph Search
Consider what A* does:
Expands nodes in increasing total f value (f-contours) Reminder: f(n) = g(n) + h(n) = cost to n + heuristic
Proof idea: the optimal goal(s) have the lowest f value, so it must get expanded first
There’s a problem with this argument. What are we assuming is true?
Proof:
New possible problem: some n on path to G* isn’t in queue when we need
it, because some worse n’ for the same state dequeued and expanded first
(disaster!)
Take the highest such n in tree
Let p be the ancestor of n that was on the queue when n’ was
popped
f(p) < f(n) because of consistency
f(n) < f(n’) because n’ is suboptimal
p would have been expanded before n’
Contradiction!
可接受性与一致性
分别对应不同的h计算公式
然而，如果启发式函数不是可采纳的或一致的，A算法可能会找到次优路径。在实际应用中，选择合适的启发式函数对于A算法的性能至关重要。如果启发式函数过于乐观，可能会导致搜索过程中忽略实际的最优路径。如果启发式函数过于保守，可能会导致搜索过程效率低下，尽管最终仍然能够找到最优路径。
因此，要确保A*算法搜索的路径是最优的，需要选择一个既不过于乐观也不过于保守的启发式函数，这通常需要对特定问题的领域知识有深入的理解。
原文链接：https://blog.csdn.net/abcwoabcwo/article/details/139211597
总结就是必须满足上市条件A*才是最优的！
Combining UCS and Greedy
上面很重要
树搜索需要启发式是可接受的
图搜索需要启发式是一致的
一致性意味着可接受性，大多数算法是一致的！