人工智能原理复习3

alt text

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!

alt text

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)

alt text
alt text

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.

alt text

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

alt text

What we’ve been building to. Cornerstone. Goes to the goal like greedy, but backtracks as needed.
When it works, it’s magic!

alt text

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?

alt text

No: only stop when we dequeue a goal

alt text
alt text

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.

alt text

Coming up with admissible heuristics is most of what’s involved in using A* in practice.

alt text
alt text
alt text
alt text
alt text
alt text

UCS ragged based on cost.
A* narrows when near goal, heuristic

alt text

Uniform-cost expands equally in all “directions”

A* expands mainly toward the goal, but does hedge its bets to ensure optimality

alt text

Change problem – same or easier. And cheaper.
Imagine a new direct road.
Walk through walls spell.
Inadmissible – a little bit suboptimal is okay.

alt text
alt text
alt text

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.

alt text

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.

alt text
alt text

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.

alt text

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?

alt text
alt text

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

alt text
alt text

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?

alt text

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!

alt text

可接受性一致性

分别对应不同的h计算公式

然而,如果启发式函数不是可采纳的或一致的,A算法可能会找到次优路径。在实际应用中,选择合适的启发式函数对于A算法的性能至关重要。如果启发式函数过于乐观,可能会导致搜索过程中忽略实际的最优路径。如果启发式函数过于保守,可能会导致搜索过程效率低下,尽管最终仍然能够找到最优路径

因此,要确保A*算法搜索的路径是最优的,需要选择一个既不过于乐观也不过于保守的启发式函数,这通常需要对特定问题的领域知识有深入的理解。

原文链接:https://blog.csdn.net/abcwoabcwo/article/details/139211597

总结就是必须满足上市条件A*才是最优的!

alt text

Combining UCS and Greedy

alt text

上面很重要

树搜索需要启发式是可接受的

图搜索需要启发式是一致的

一致性意味着可接受性,大多数算法是一致的!


人工智能原理复习3
http://jrhu0048.github.io/2024/06/18/ren-gong-zhi-neng-yuan-li/ren-gong-zhi-neng-yuan-li-fu-xi-3/
作者
JR.HU
发布于
2024年6月18日
更新于
2024年10月15日
许可协议