Video在线视频

那么我们再来看一下第二种最佳优先搜索策略

叫做A*搜索策略

那么这个A*搜索策略它定义的评估函数

和我们的贪婪最佳优先搜索是不一样的

那么它定义的评估函数不但估计了结点n到达目标
的代价

它还计算出来了从初始节点到达结点n已经发生的
代价，给他累加起来

所以它就可以避免拓展这些已经发生很高代价的
结点

那么这会比贪婪最佳优先搜索好一些

那么来看一下评估函数f（n）是等于g（n）加上
h（n）

那么我们的g（n）定义的是从初始结点到达结点n
已经发生的实际代价

也就是说从初始结点搜索到达结点n实实在在的这
条搜索路径的代价值

那么我们的h（n）和贪婪优先搜索是一样的

它也是启发式函数

那么这个启发式函数估计的是从结点n到目标的代
价

也就是说它是一个估计值

那么我们的A*搜索就采用这么一个评估函数
f（n）

它用来估计从初始结点出发经过结点n

到目标的这么一条完整路径的代价

所以根据这么一条路径代价对待拓展结点进行排
序

优先拓展整体代价估计值比较小的结点

这是它的思想

所以我们来看一下对于我们的罗马尼亚问题

我们的A*搜索它是怎么样做的

那么我们看到假设我们的h（n）和我们的贪婪优
先搜索定义的是一样的

也就是说用结点n到目标城市的直线距离作为它的
一个估计

那么我们来看一下Arad是我们的初始结点

那么首先看一下是不是目标，不是

然后因为我们的fringe表里只有它所以也不用排队

但是它也会附带的计算一下Arad的评估函数值
f（n）

它是等于g（n）加上h（n）

g（n）就是从初始结点到当前结点的代价

那么它自己本身是初始结点，所以这个代价本身
是零，没有发生代价

然后这个结点到目标结点代价的估计值

我们用的是直线距离366作为它的估计值

所以这两个加起来就是它的评估函数值366

然后我们对Arad这个城市进行拓展

它可以到这三个城市去

那么现在我们的fringe表里面有三个待拓展结点

那么这三个待拓展结点都计算一下它的评估函数
值

那么Sibiu的评估函数值同样是两部分

g（n）就是从初始结点到这个结点的代价

那么我们知道这个实际的路径代价是140

然后h（n）就是它到目标城市的直线距离作为估
计就是253

所以加起来是393

然后这个也是同样的去计算

g（n）就是Arad到它的实际距离就是118

然后h（n）就是它到目标城市的估计值用直线距
离来估计就是329

所以出来是447

那么同样的这个我们算出来g（n）实际距离是75

h（n）到目标的直线距离是374

所以算出来是449

然后以排序的话Sibiu排在前面

因为它评估函数值代价最小

所以它排在最前面，所以对它进行拓展

那么看一下它是不是目标，不是

不是对它进行拓展

对它进行拓展它就会产生四个后续结点

那么同样的这四个后续结点我们也要去计算一下
它的评估函数值

那么它的评估函数值就是从初始结点到达这个结
点发生的代价

那就是Arad到Sibiu的距离加上Sibiu到Arad的距离
是280

然后Arad到首都Bucharest的直线距离是
366，h（n）估计值

所以算出来是646

那么这个也是一样的

就是从初始结点到达它的实际距离是239

就是图示两段距离的和就是我们的g（n）

然后再加上h（n）就是它到Bucharest的直线距离
176，所以算出来是415

那么同样的道理去算，Oradea算出来是671

Rimricu Vilcea是413

算出来之后这六个拓展结点根据评估值进行排序

那么Rimricu Vilcea的评估函数值是414是最小的

所以对它进行拓展，先看一下是不是目标

不是目标，然后对它进行拓展

拓展之后就产生了三个新的结点

那么这三个新的结点也要计算一下它的评估函数
值

然后比如说这个结点的第一部分g（n）

g（n）就等于三段路径之和等于366

然后再加上h（n）就是它到目标城市的直线距离
160，所以加起来是526

那么这些也是同样的算出来

算出来之后呢这八个待拓展结点进行排序

这个结点是排在最前面的

也就是说它的整体估计代价最小

所以对它进行拓展，先看一下是不是目标

不是，然后对它进行拓展

拓展就产生两个新的结点

那么这两个新的结点我们也要计算一下它的评估
函数值

那么这个评估函数值就是g（n）加上h（n）

那么g（n）就是上述三段和等于338

再加上这个城市到目标城市的直线距离253

所以算出来是591

那么这个结点一样的道理

那么g（n）就是上述三段和等于450

h（n）就是这个结点到目标结点的直线距离

那么其实上它到目标结点的直线距离

其实上它已经是目标城市

所以它的直线距离我们到表里面一看等于零

所以它就加零等于450

但是为什么这个时候没有停止搜索呢

因为我们的树搜索方法要结点排在fringe队首拓展
时才会拿出来检查它是不是目标

不是产生的时候检查

当然你也可以修改你的搜索算法

就是让它产生的时候就检查是不是目标

如果是目标就终止，这样可以节约一些时间

那么这个时候我们的待拓展结点就有9个

那么这9个拓展结点根据评估函数进行排序

排序的话这个摆在最前面，它是417

所以它就被取出来进行拓展

拓展之前先看一下是不是目标，不是

然后对它进行拓展，产生三个后续结点

那么对着三个后续结点进行一个评估函数的计算

那么计算出来这个结点的评估函数值等于418

也就是说也是等于g（n）加上h（n）

那么g（n）就是从初始结点到达这个结点实际的
代价

也就是以上四段和等于418

然后再加上h（n）就是他到目标的直线距离，是
等于零的

所以算出来它等于418

那么这个也同样去算等于615，这个算出来的等于
607

那么所有的待拓展结点根据评估函数进行排序

那么它排在最前面

所以下一次它拿出来进行拓展

那么拓展之前我们看一下它是不是目标

发现它是目标那么这个时候算法就结束了

算法就找到了一个解，这个解就是

从Arad先到Sibiu再到Rimricu Vilcea再到Pitesti再
到Bucharest

那么找到的这条路的代价是418

也就是说它是上述四段距离的和正好是418

那么如果换一种检查结点是不是解得顺序的话，
你可能就会找到这个解回去

而这个解得代价是450，要比这个解的代价高

所以这个解反而更好

这个是A*搜索采用树搜索框架可能会有一些更好
的优点

那么这个是A*搜索对于罗马尼亚问题搜索的一个
实例