Video在线视频

所以我们来总结一下盲目搜索策略

我们总共讲了五种盲目搜索策略

宽度优先搜索，代价一致搜索，深度优先搜索，
深度有限搜索，迭代深入搜索

那么我们来看一下它们的四个性能指标

第一个是完备性

宽度优先搜索是有完备性的

也就是说有解它一定能找得到解

因为它是一层一层扫过来，而解一定在有限的深
度

所以它一定能找出这个解

代价一致搜索策略也具有完备性

也就是说随着搜索的进行，只要单步代价不是为
零，是一个大于零的正整数的话

随着搜索的进行，其他生成结点的代价会越来越
大

那么这个解的代价总有排在最前面的时候

所以总有找出这个解的时候，所以它能保证完备
性

深度优先搜索是不能保证完备性的

因为它可能先搜索的是一条无限长并且没有解的
路

它可能回不来，那么其他的解它就找不到了

深度有限搜索也没有完备性

因为如果你设置的深度限制不合理，在这个深度
限制之内无解

而解在深度限制之外，所以无法找到

迭代深入搜索是具有完备性的，它也是一层一层
扫过来的所以它具有完备性。

那么时间复杂度方面

宽度优先搜索是指数级的

代价一致搜索也是指数级的

它和最优解的代价以及单步代价有关

深度优先搜索的时间复杂度，当然这只是一个最
坏的上限，是指数级的

当然如果你优先试探了一条最浅层的路径

正好这条路径上又有解，那么这个时间复杂度就
会大大的降低

深度有限搜索的时间复杂度是跟你的深度限制有
关 就是b的l次方

迭代深入搜索的时间复杂度和最浅层解所在的深
度有关，b的d次方，所以它是比较好的

那么再看空间复杂度

宽度优先搜索要把所有产生的结点都储存下来

因为在找到解之前它不知道哪个结点下面有解

所以它无法抛弃结点

代价一致搜索也是一样的道理

它在找到解之前也不知道哪个结点下面有解

所以所有产生的结点它都要存储在内存里面

那么深度优先搜索，因为它是一条路径一天路径
搜索

任何时候它都只存储一条路径的结点

所以它是一个线性的存储空间要求

深度有限搜索也是线性的

他也是一条路径一条路径搜索

并且这些路径最长为l，所以它的空间复杂度为bl

迭代深入搜索每一次设深度限制时，它都是用深
度有限来搜索的

所以它最大的存储空间要求就是

当for循环循环到深度限制d的时候

存储的这么一条长度为d的路径上的节点

所以它是b乘以d，也是一个线性的

接下来我们看一下最优性

最优性我们考虑的是单步代价是相同的

也就是说最浅层的解是最优的

宽度优先搜索能保证找到一个最浅层的解给你

所以它有最优性

代价一致搜索考虑的是

如果单步代价不相等，那么可能最浅层的解不一
定是最优的

所以它是按照结点的代价来进行排序

那当然代价小的解节点肯定是排在前面

所以它找到的解一定是代价最小的解

所以它能保证最优性

深度优先搜索是无法保证最优性的

因为它是一条路径一条路径搜索的

如果这条路径上的解不是最优的它也不管，它就
返回给你

深度有限搜索也不能保证最优性

因为它也是一条路径一条路径搜索

只不过每条路有一个深度限制，到达深度限制它
就回来了

迭代深入搜索是可以保证最优性的

因为它的深度限制是从零递增的

所以在宏观上它相当于一层一层扫下来

当深度限制到达最浅层的解所在的深度时

它就把这个解给找出来了，不再往下走了

所以它能保证找到最浅层的解给你

这个是有最优性的

这个就是我们盲目搜索策略的一个小结

那么来看一下为什么有时候会有无限的状态空间

并不是所有情况下这个问题都复杂到有无限的状
态

有可能是因为你不能检查这种重复状态

把一个本来是有限的状态空间变成一个无限的状
态空间

把一个线性问题变成一个指数级问题

比如说这里A执行一种动作可以到达B状态

执行另外一种动作也可以到达B状态

那么由于你不检查重复状态，就会产生两个结点

两个不同的结点

那么如果你检查重复状态，那么其实这两个结点
使对应的同一个状态

其实用一个结点就够了，就是所它认为只有一个
儿子就行

那么同样这里也是

如果B执行一种动作会达到C这种状态

执行另外一种动作也是产生C这种状态

那么同样你没有检查重复状态

那么B也会产生两个儿子结点

那么其实是这两个结点是对应着同一个状态的

其实是你只要产生一个结点就够了

但是由于你没有检查重复状态

本来是只有A、B、C三个结点的一颗搜索树

变成了一颗有这么多结点的搜索树

就是把一个线性问题变成一个指数级问题

变成了2、2的平方，本来是1、1、1

所以这就是我们的树搜索框架不检查重复状态

可能就会出现这个么一个比较严重的问题

图搜索策略就是要克服树搜索策略由于不检查重
复状态把一个简单问题变得复杂了

它就加入了一个检查重复状态的一个工作

那么要检查重复状态它就需要储存已经产生的结
点或者已经扩展的结点

那么它才能去比较这些新产生的结点是不是曾经
出现过

下面我们来看一下图搜索框架是怎么做的

它和树搜索一样也有一个参数是问题的形式化

然后它也有一个数据结构fringe表

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

但是它还定义了另外一个变量closed表

就是说将已经拓展过、搜索过的结点放入这个表

一开始这个表初始化为空集

就是说表里面还没有已经拓展过的结点

那么fringe就是待拓展结点

待拓展结点表和前面的树搜索是一样的

也就是说，一开始将我们的初始结点放进去

也就是说根据问题的形式化它的初始状态

产生一个初始结点插到fringe表中，放到队首

然后开始循环，搜索

那么首先看下fringe表，边缘表中，还有没有待拓
展的结点

如果没有，那执行到这条语句也就意味着

又没有，又没找到解，那么就返回失败

就表明，没有待拓展结点了，所有的空间都搜索
完毕了也没有找到解

所以就是失败的，和前面一样

否则就在fringe边缘表里面，待拓展结点表里面

把排在队首的结点取出来

取出来之后，先看一下这个结点对应的状态是不
是我们的目标状态

也就是说这个结点是不是一个目标结点

是的话，那表明找到解了，那就返回去了

如果不是的话，就要判断这个结点对应的状态是
不是在closed表里面

也就是说前面搜索过的结点里面出现过

如果出现过它就不对这个结点进行拓展

就是下一轮迭代了，就去fringe表中取一个结点出
来进行拓展

也就是说他这里避免了重复状态的重复搜索

所以他与树搜索不同的地方就在这里

它判断了结点对应的状态是不是曾经出现过

如果没有出现过，也就是说不在closed表里面

它才进行拓展

那么进行拓展之前，先把这个结点对应的状态加
到closed表里面去

也就是说先告知后面的人，这个状态曾经出现过

所以先放进去，然后和树搜索策略一样，进行拓
展

那么对这个结点根据问题的形式化进行拓展

拓展出来的所有后续结点，插入到fringe表里面

插入过程，根据我们的搜索策略，插入到合适的
位置

所以说，这个就是图搜索与树搜索不同的地方

就是多了这一句话，多了这么一个变量closed表

用来储存曾经搜索过，曾经出现过的状态

避免重复状态的产生、搜索，所以这个是图搜索

那么这一章就是讲了这个盲目搜索策略

首先我们要把问题进行形式化

问题进行形式化需要把真实世界的一些细节进行
抽象化，就是去掉一些细节

否则的话，你没有办法解决这个问题

然后定义一个可以进行搜索，可以解决的状态空
间

可以进行问题解决的一个问题

这个就是问题的形式化，就是进行抽象化

然后我们还讲了五种不同的盲目搜索策略

这个搜索策略其实就是怎么样对待拓展的结点进
行排序

看一下应该优先搜索哪个节点

那么这个是搜索策略

通过对五种盲目搜索策略的比较

我们知道迭代深入搜索具有比较好的指标

它仅仅需要线性的储存空间

并且和其他盲目搜索策略相比它的时间复杂度也
差不多

所以它综合指标还是比较好的