Video在线视频

那么我们首先来回顾一下这个树搜索

首先我们知道这个树搜索有一个搜索策略要告诉
它

也就是说首先不但问题的形式化要作为输入

还有一个搜索策略

然后它返回一个解，或者是返回失败

首先它要根据问题形式化里的初始状态来初始化
搜索树

也就是说根据问题的初始状态

产生一个初始结点作为搜索树的根结点

然后开始不断的进行搜索进行循环

就是说它会有一个数据结构来储存待拓展结点

那么如果它发现没有待拓展结点了

那么它就意味着我所有的空间都搜索完毕了

也没有找到解，它就返回一个失败

否则就从待拓展结点里选择一个结点

当然这个结点还是没有拓展过的

那么在搜索树里就是一个叶子结点

那么选择的方案是根据搜索策略来决定的

选择好待拓展结点取出来进行拓展的时候呢

那么我们先判断待拓展结点是不是目标结点

也就是说它是不是一个目标状态

如果是的话就意味着找到了解，就把这个解返回
去

否则就对这个结点进行拓展

并把新产生的儿子结点加到搜索树里面去

那么这个就是整个树搜索的一个框架

那么这里面非常重要的就是一个搜索策略

因为这个策略就决定着这个算法的性能

也就是说搜索策略就是结点拓展顺序的一种选择

那么我们前面在讲盲目搜索策略的时候

只是根据问题形式化的信息来对待拓展结点进行
排序

也就是说并没有用到什么先验信息和其他知识

那么这一章我们就讲一下启发式的搜索策略

也就是说这一章的搜索策略可能会用到一些其他
的信息

来对这些待拓展结点进行评估排序

首先看到第一大类叫做最佳优先搜索策略

那么这种最佳优先搜索会使用一个评估函数

一般我们后面把评估函数命名为f（n）

也就是n结点给他一个评估值

那么给每个结点估计他们的一个希望（期望）值

这里的期望（希望）值是什么意思呢

就是认为它最有希望（期望）到达目标结点

也就是说某个结点下面最有希望优先到达目标结
点

也就是说它最有希望找到一个解

也就是说通过这个评估就可以优先拓展这些最有
希望到达目标结点的待拓展结点

从而能够快速找到解得这么一个思想

那么他的实现也很简单

如果程序员自己设计好了评估函数之后呢

那么这个fringe表（边缘表）就可以通过评估函数
值从大到小排序

排在前面的就认为它最有希望到达目标结点

那么优先把它拿出来进行拓展

就是这么一个实现方法

那么我们的最佳优先搜索策略有两种

这里我们会讲两种，一种叫贪婪优先搜索

另外一种叫A*搜索

也就是说这两种搜索策略都定义了一个评估函数
f（n）

只不过是贪婪优先搜索定义的f（n）

和我们的A*搜索定义的f（n）是不一样的

那我们来看一下

贪婪优先搜索的f（n）是怎么定义的呢？

它是这样定义的，它定义这个评估函数f（n）

就等于h（n），那么等于h（n）

h（n）我们后面也会一直用这个函数名字

这个h的意思就是启发式的意思

就是启发式函数这个英文字母的首字母

也就是说它估计的是从结点n到目标的代价

也就是说它是一种估计值

它估计的就是从结点n到达目标可能会发生的消耗
（耗散、代价）

当然因为他还没有实际的搜索到目标

所以这个代价它其实上是不知道的

但是它通过我们程序员的设计它只是一种估计值

也就是说它通过这个估计值来对这个结点n进行排
序

他认为只凭从结点n到目标结点的代价来对这些待
拓展结点进行排序

那么比如说我们在前面讲过的罗马尼亚问题

罗马尼亚问题就可以定义一个这样的启发式函数

也就是说我在城市，也就是结点n

城市n到达Bucharest的直线距离作为城市n（结点
n）实际到达目标距离的一个估计

这是可以的，也就是说它只是一种估计值

这个可以用来定义评估函数

那么贪婪优先搜索的评估函数是由启发式函数来
定义的

为什么它取名叫贪婪呢？

因为贪婪的意思就是他总是优先拓展那些看上去
更接近目标的结点

也就是说它是根据这个启发式函数看一下，哪个
结点离目标更近

也就是说当结点的代价更小好散更小离目标更近

那我就优先拓展哪个节点

那么从这个就是贪婪的意思

那么这个是贪婪最佳优先搜索的定义

然后它就根据这个定义，当然如果你定义的是一
种代价的话

那就是代价从小到大排序

小的就认为它是最有希望的，就是认为它更接近
我们的目标

所以优先取出来进行拓展

那么我们看到这个罗马尼亚问题

这个问题就是我们前面章节讲过的

就是说这个假设智能体在罗马尼亚度假

他有一张第二天早上从Bucharest起飞的航班

所以它就需要从Arad开车到Bucharest去，不能误
了航班

然后它就需要找到一条路去Bucharest，这么一个
问题

然后它找路的话

这是一张简单的罗马尼亚主要城市地图

那他就需要评估城市不同的节点离目标距离的一
个估计

然后做出选择应该走哪条路，那么这是这个问题

那么我们来看一针对这个问题

用刚才定义的启发式函数来看一下

贪婪优先搜索是怎样进行罗马尼亚问题的求解的

那么一开始我们是用初始结点产生搜索树的根节
点

也就是说对搜索树进行初始化

那么要计算出来每个待拓展结点的评估函数值

那么我们的贪婪优先搜索的评估函数值就等于启
发式函数值

也就是说这个f（n）就等于h（n）

那么我们刚才定义的启发式函数是

用的是这个城市到目标城市Bucharest的直线距离
作为它的一个估计

也就是用的是这边的一个直线距离

那么我们来看一下这个Arad到达Bucharest的直线
距离是366

这里写了直线距离，这是可以通过地图测量出来
的

那么它就用366作为待拓展结点的评估函数值

因为现在待拓展结点只有初始结点

那么毫无疑问它就排在前面

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

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

不是的话就对它进行拓展，产生三个儿子

三个儿子如PPT所示

然后产生出来的三个儿子就要插到fringe表里去

那么插到fringe表里每个结点还记录了它相应的评
估函数值

那么也就是我们这里的启发式函数值

那么Sibiu到达首都的直线距离是253

Timisoara到达首都的直线距离是329

Zerind到达首都的直线距离是374

所以排队的时候我们就能看得出来

有理由相信它离我们的目标更近

也就是根据我们的启发式函数值

我们知道这个结点离我们的目标更近

所以Sibiu就排在最前面Timisoara排在第二Zerind
排在第三

然后我们就优先拓展Sibiu，把它取出来进行拓展

那么拓展的时候同样的看一下它是不是目标

不是目标所以对它进行拓展

然后拓展就新产生出来了这些结点

也就是说从Sibiu能直达这四个城市

那么直达这四个城市同样的道理

然后新产生出来的这四个结点也要去计算它的评
估函数值，也就是启发式函数值

那么Arad到首都目标城市直线距离是366

Fagaras是176，Oradea是380，Rimnicu Vilcea是
193

然后这六个待拓展结点通过评估函数值排序

看一下谁离目标最近，谁最有希望到达目标

那么就是Fagaras评估函数直线距离最小

所以它排在最前面，所以就先把它取出来进行拓
展

那么拿出来进行拓展同样的看一下是不是目标

不是目标，所以对它进行拓展

拓展的话Fagaras可以直达Sibiu和Bucharest

那么可以直达这两个城市

同样这两个结点也插到fringe表里去

那么插得时候也同样的是会计算这两个新产生的
结点的评估函数值

那么Sibiu到首都的直线距离是253

那么Bucharest到首都的距离是0，因为它就是目
标

所以根据评估函数值进行排序的话它是离目标最
近的

也就是说它会排在最前面，那么就把它取出来进
行拓展

那么进行拓展的时候先看一下它是不是目标

发现它是目标所以这个搜索就结束了

然后就把这个解返回去

它就会告诉机器人从Arad出发先去Sibiu

再去Fagaras，再到Bucharest这个城市去

找到了一条路径给它

这个就是我们的贪婪优先搜索的实例过程

那么我们来看一下贪婪最佳优先搜索的属性

或者说它的四个性能指标

第一个就是完备性，那么贪婪优先搜索有没有完
备性呢？

是没有的

就是在有限的状态空间里它也可能会陷入死循环
当中的

比如说我们的罗马尼亚问题

那么如果我们把这个问题改成从Iasi出发

第二天要到Fagaras这个城市去

那么我们的初始结点就变成了Iasi

那么初始结点变成了Iasi我们就对它进行

先看一下是不是目标，不是

然后对它进行拓展

那么拓展的话就会产生这两个待拓展结点

那么这两个待拓展结点就要进行排序

那么根据贪婪最佳优先搜索呢？

它排序的原则就是启发式函数

那么启发式函数值我们来看一下

Neamt到Fagaras的直线距离

以及Vaslui到Fagaras的直线距离

我们可以看得出来Neamt到Fagaras的直线距离更
小

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

那么对它进行拓展的话，发现它不是目标

就对它拓展产生一个后续Iasi

所以现在我们的待拓展结点是Iasi和Vaslui

这两个是待拓展结点

那么来看一下这个Iasi到Fagaras的直线距离

也要比Vaslui到Fagaras的直线距离要小

所以它会优先拓展Iasi

那么优先拓展Iasi，它就变成死循环了

那么Lasi拓展就会产生Neamt和Vaslui

那么Neamt到Fagaras的直线距离又更短所以又是
拓展它

所以就会变成一个死循环

这个死循环就如ppt绿色字体不部分

就会在这个死循环里出不来了，就会找不到解

那么这个是完备性

当然这有一个原因是这个树搜索没有检查重复状
态

导致一个有限的状态空间变成了一个无限的状态
空间

那么这个是第一个性能指标

那么第二个我们的时间复杂度呢

它是依赖于我们的启发式函数

因为对于贪婪最佳优先搜索来讲我们对结点拓展
的优先顺序完全取决于启发式函数

那么如果你的启发式函数定义的一点都不好

那么可能要将整个状态空间都搜索个遍

所以它最大的上限就是把整个空间搜索个遍

是b的m次方，这个m我们讲过就是搜索树的最深
层

但是如果你的启发式函数定义地好的话

可能时间就会大大的节省，带来巨大的改善

那就会比盲目搜索策略要好的多的多

那么我们再看空间复杂度

那么空间复杂度的话

我们的贪婪优先搜索又不是像深度优先搜索一样

那条路一直走到底

那么它也是根据启发式函数值来进行排序的

所以它在找到解之前它也不太清楚那一个结点下
面会找到解

所以产生出来的结点都要保存在内存里面

所以它的空间复杂度和时间复杂度是一样的

那么有么有最优性呢？它这个就不能够保证

他只是根据启发式函数值来排队的

那么它并没有计算那个节点从那条路总共的代价
来排序

所以它是不能够保证最优性的

那么这个是贪婪优先搜索的四个指标