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