Properties of greedy search A'search dea:avoid expanding paths that are already expensive Evaluation function f(n)) al from Space?? (Alo rquire()for any goal C.) Enever overestimates the actuaroad distance Properties of greedy search A'search example Time??O().but a good heuristic can give dramatic improvement Space??O()-keeps all nodes in memory Optimal7? Properties of greedy search A search example 之 im7)butagod heuristic cangvdramatic improvement 品 Space??nodes in memory Optimal7?NoProperties of greedy search Complete?? No–can get stuck in loops, e.g., Iasi → Neamt → Iasi → Neamt → Complete in finite space with repeated-state checking Time?? O(b m), but a good heuristic can give dramatic improvement Space?? Chapter 4, Sections 1–2 13 Properties of greedy search Complete?? No–can get stuck in loops, e.g., Iasi → Neamt → Iasi → Neamt → Complete in finite space with repeated-state checking Time?? O(b m), but a good heuristic can give dramatic improvement Space?? O(b m)—keeps all nodes in memory Optimal?? Chapter 4, Sections 1–2 14 Properties of greedy search Complete?? No–can get stuck in loops, e.g., Iasi → Neamt → Iasi → Neamt → Complete in finite space with repeated-state checking Time?? O(b m), but a good heuristic can give dramatic improvement Space?? O(b m)—keeps all nodes in memory Optimal?? No Chapter 4, Sections 1–2 15 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 to goal from n f(n) = estimated total cost of path through n to goal A ∗ search uses an admissible heuristic i.e., h(n) ≤ h ∗ (n) where h ∗ (n) is the true cost from n. (Also require h(n) ≥ 0, so h(G) = 0 for any goal G.) E.g., hSLD(n) never overestimates the actual road distance Theorem: A ∗ search is optimal Chapter 4, Sections 1–2 16 A∗ search example Arad 366=0+366 Chapter 4, Sections 1–2 17 A∗ search example Zerind Arad Sibiu Timisoara 393=140+253 447=118+329 449=75+374 Chapter 4, Sections 1–2 18