Informed search algorithms Chapter 4
Informed search algorithms Chapter 4
Material ·Chapter4 Section1-3 ● 。 Exclude memory-bounded heuristic search
Material • Chapter 4 Section 1 - 3 • • Exclude memory-bounded heuristic search •
Outline ·Best--first search Greedy best-first search ·A search ·Heuristics Local search algorithms ·Hil-climbing search Simulated annealing search ·Local beam search ·Genetic algorithms
Outline • Best-first search • Greedy best-first search • A* search • Heuristics • Local search algorithms • Hill-climbing search • Simulated annealing search • Local beam search • Genetic algorithms
Review:Tree search \input{\filefalgorithmsHtree-search-short- algorithm ● A search strategy is defined by picking the order of node expansion
Review: Tree search • \input{\file{algorithms}{tree-search-shortalgorithm}} • • A search strategy is defined by picking the order of node expansion •
Best-first search Idea:use an evaluation function f(n)for each node estimate of"desirability" >Expand most desirable unexpanded node → ·Implementation: Order the nodes in fringe in decreasing order of desirability ·Special cases: greedy best-first search A search
Best-first search • Idea: use an evaluation function f(n) for each node – estimate of "desirability" – →Expand most desirable unexpanded node → • Implementation: Order the nodes in fringe in decreasing order of desirability • Special cases: – greedy best-first search – A* search –
Romania with step costs in km Straight-line distance ▣Q3dea 71 b Bucharest Neamt Arad 366 75户zerm 87 Bucharest 0 151 Craiova 160 Dobreta 242 Ar3d白 140 Eforie 161 92 Siblu Fagaras 176 9 Fagaras 11日 ▣ Giurgiu 7 ▣ 80 口Vaslul Hirsova 151 Iasi 226 白Timisoa3 Rimnu Vikea Lugoj 244 142 Mehadia 241 1T 211 Neamt 234 ▣Lugj Pitestl Oradea 390 7d 98 Pitesti 10 146 ▣ehadia 10T 85 ▣Hirsova Urzicenl Rimnicu Vikea 193 75 86 Sibiu 139 253 Bucharest Timisoara 329 Dob reta白 120 90 ▣ Urziceni 830 口Cralov3 Efor le Vaslui 199 Glurglu Zerind 374
Romania with step costs in km
Greedy best-first search Evaluation function f(n)=h(n)(heuristic) estimate of cost from n to goal ● .e.g.,hsLo(n)=straight-line distance from n to Bucharest ● Greedy best-first search expands the node that appears to be closest to goal
Greedy best-first search • Evaluation function f(n) = h(n) (heuristic) • = estimate of cost from n to goal • • e.g., hSLD(n) = straight-line distance from n to Bucharest • • Greedy best-first search expands the node that appears to be closest to goal •
Greedy best-first search example
Greedy best-first search example
Greedy best-first search example Sbiu Timisoala Zerind 253 32 374
Greedy best-first search example
Greedy best-first search example Sbu○ Timisoara Zatind 329 374 Oradea Hrria Vicea 336 78 380 193
Greedy best-first search example