Best-first search ldea:use an evaluation function(评价函数)for each node 一estimate of“desirability" =Expand most desirable unexpanded node A heuristic is: A function that estimates how close a state is to a goal Designed for a particular search problem Implementation:fringe is a queue sorted in decreasing order of desirability 一priority queue(优先级队列) Special cases:greedy search,A*search 日◆4日4三+1=，￥9QC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Best-first search ▶ Idea: use an evaluation function (评价函数) for each node — estimate of“desirability” =⇒ Expand most desirable unexpanded node ▶ A heuristic is: ▶ A function that estimates how close a state is to a goal ▶ Designed for a particular search problem ▶ Implementation: fringe is a queue sorted in decreasing order of desirability — priority queue (优先级队列) ▶ Special cases: greedy search, A* search
Best-first search Best-first search( cdo3 ed list=[】 open list[start node] do if open list is empty then( return no solution n=heurstic best node ifn-final node then f return path from start to goal node foreach direct available node dof if node not in open and not in closed list do add node to open list etnashis parent node 1 delete n from open list add n to closed list while (open list is not empty) Best-first search is an instance of the general TREE-SEARCH or GRAPH-SEARCH algorithm in which a node is selected for expansion based on an evaluation function. 0,,4告生分双
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Best-first search ▶ Best-first search is an instance of the general TREE-SEARCH or GRAPH-SEARCH algorithm in which a node is selected for expansion based on an evaluation function
Romania with step costs in km 71只Oradea Straight-line distance to Bucharest Neam Arad 366 87 Bucharest 0 151 Cralova 160 Dobreta 242 140 Eforie 92 Sibiu 下gr 99 Fa9a网 178 118 Giurgiu 7 ▣ ▣Vaslui Hirsova 151 lasi 226 白imisoar Rimnicu Vilcea Lugoj 244 142 Mehadia 211 24 L9别 977 Neamt 234 Oradea 70 380 98 Pitesti 146 ▣Mehadia 10叶 85 ▣Hirsova U所rziceni Rimnicu Vilcea 193 75 138 86 Sibiu 253 Bucharest Timisoara Dobreta▣ 120 890 Urziceni Eforie Vaslui 图 口Giurgiu Zerind 374 4口◆4⊙t1三1=，￥9QC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Romania with step costs in km
Greedy search Evaluation function h(n)(heuristic function启发函数) estimate of cost from n to the closest goal (节点n到目标节点的最低耗散路径的耗散估计值) E.g.,hsLD(n)=straight-line distance from n to Bucharest Greedy search expands the node that appears to be closest to gol(试图扩展离目标节点最近的点) 口卡回t·三4色，是分Q0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Greedy search Evaluation function h(n) (heuristic function 启发函数) = estimate of cost from n to the closest goal (节点 n 到目标节点的最低耗散路径的耗散估计值) E.g., hSLD(n)= straight-line distance from n to Bucharest Greedy search expands the node that appears to be closest to goal (试图扩展离目标节点最近的点)
Greedy search example Arad 366 4口卡404三·1怎生00
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Greedy search example