人工智能AI-2-Search-2.ppt

Informed Search and Exploration
Chapter 4 in textbook
Outline
Informed (Heuristic) Search Strategies
Heuristic funf Fagaras is expanded we get:
Sibiu and Bucharest
Goal reached !!
Yet not optimal (see Arad, Sibiu, Rimnicu Vilcea, Pitesti)
Properties of greedy best-first search
Complete? No (cf. DF-search)
Minimizing h(n) can get stuck in loops, . Iasi to Fagaras: Iasi  Neamt  Iasi  Neamt 
Properties of greedy best-first search
Complete? No (cf. DF-search)
Time complexity?
Cf. Worst-case DF-search: O(bm)
(with m maximum depth of search space)
Good heuristic can give dramatic improvement
Properties of greedy best-first search
Complete? No (cf. DF-search)
Time complexity? O(bm)
Space complexity? O(bm)
keeps all nodes in memory
Properties of greedy best-first search
Complete? No (cf. DF-search)
Time complexity? O(bm)
Space complexity? O(bm)
Optimal? No
Same as DF-search
A* search
Best-known form of best-first search
Idea: avoid expanding paths that are already expensive
Evaluation function f(n)=g(n) + h(n)
g(n) the cost (so far) to reach the node n
h(n) estimated cost of the cheapest path from the node n to the goal
f(n) estimated total cost of cheapest path through n to goal
A* search
A* search uses an admissible heuristic
A heuristic is admissible if it never overestimates the cost to reach the goal
Optimistic
Formally:
1. h(n) <= h*(n) where h*(n) is the actual cost
2. h(n) >= 0 so h(G)=0 for any goal G
. hSLD(n) never overestimates the actual road distance
Theorem: If h(n) is admissible, A* using TREE-SEARCH is optimal
A* search example
Find Bucharest starting at Arad
f(Arad) = c(Arad,Arad) +h(Arad)=0+366=366
A* search example
Expand Arad and determine f(n) for each node
f(Sibiu)=c(Arad,Sibiu)+h(Sibiu)=140+253=393
f(Timisoara)=c(Arad,Timisoara)+h(Timisoara)=118+329=447
f(Zerind)=c(Arad,Zerind)+h(Zerind)=75+374=449
Best choice is Sibiu
A* search example
Expand Sibiu and determine f(n) for each node
f(Arad)=c(Sibiu,Arad)+h(Arad)