Greedy best-first search example Sbiu Timisoala Zerind 32 374 Aiad FagaiasOradea ria Vice的 356 380 193 SbiuBuchaiest 253
Greedy best-first search example
Properties of greedy best-first search 0 Complete?No-can get stuck in loops, e.g.,lasi→Neamt→lasi→Neamt> ● 。 Time?O(bm),but a good heuristic can give dramatic improvement ● 。 Space?O(bm)--keeps all nodes in memory
Properties of greedy best-first search • Complete? No – can get stuck in loops, e.g., Iasi → Neamt → Iasi → Neamt → • • Time? O(bm), but a good heuristic can give dramatic improvement • • Space? O(bm) -- keeps all nodes in memory • • Optimal? No
A'search Idea:avoid expanding paths that are already expensive ● Evaluation function f(n)=g(n)+h(n) ● g(n)=cost so far to reach n h(n)=estimated cost from n to goal f(n)=estimated total cost of path through n to goal
A* search • Idea: avoid expanding paths that are already expensive • • Evaluation function f(n) = g(n) + h(n) • • g(n) = cost so far to reach n • h(n) = estimated cost from n to goal • f(n) = estimated total cost of path through n to goal •
A'search example DAiad 36-0+360
A* search example