Video在线视频

我们首先来看到宽度优先搜索

那么宽度优先搜索这种搜索方法，这种搜索策略

它是怎么实现拓展结点的排序

也就是说它怎么样来选择结点进行优先拓展的呢?

它是优先拓展最浅层的未拓展结点，候选拓展结点

那么这是什么意思呢？

就是说有可能这些叶子结点（待拓展结点）

是位于不同的层的，它是优先拓展最浅层的结点

那么这种方法如何通过树搜索的fringe表来实现呢

只要我们的fringe表采用先进先出的队列

也就是说first in first out

它就可以实现优先拓展浅层结点的思想

然后我们来看到这个例子

这里有一个A结点，也就是假设A结点为初始结点

它一开始插到fringe表里，它是第一个待拓展结点

那么进行搜索的时候我们就把它从fringe表里取出来

因为fringe表只有一个结点

所以当然就把它放在队首

把它取出来，先看一下这个节点是不是目标状态

不是，不是的话就对这个节点进行拓展

那么这个A结点可以分别执行两个动作

分别产生B、C两个后续结点

那么B、C两个结点一产生 就把这两个结点插到这个队列里去

那么插到这个队列里面去呢

因为它们是同时产生，那么假设我们先左后右排序

这样的排放到队列里面去

那么A的话已经从队列里取出来了

进行拓展的时候已经把它取出来了

然后B、C放到fringe表里面去了以后

B排在fringe表的最前面

所以我们把B取出来进行拓展

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

然后就对它进行拓展

它就会产生D、E两个后续

所以B出来以后D和E就插到fringe表里去

那么插的时候，我们讲了

我们的fringe表采用的是先进先出

就是说后来的是排在这个fringe表的队尾的

也就是说插到它的尾巴上面去

就和我们平常排队一样，后来的人是排在尾巴上的，所以是后出的

接下来虽然有D、E、C三个叶子结点（待拓展结点）

但是我们的C，最浅层的C排在队首

所以它就优先拓展C，而不是拓展D和E

所以它就拓展C，所以下一次它就把这个C取出来

C取出来对它进行判断，不是目标

然后拓展产生F、G插到队尾去

所以排到后面去 F、G

所以下一次排在队首的D会被取出来进行拓展

所以我们只要使用fringe表

让它采用这种先进先出的队列形式

就可以实现宽度优先搜索

就可以让浅层的结点排在前面

也就是让浅层的结点优先进行拓展

那么宽度优先搜索的性能指标是什么样的呢？

首先我们来看一下它有没有完备性

完备性我们前面讲过

就是如果这个状态空间里面有解

它保证能找到解

那么一般情况下我们认为它是具有完备性的

也就是说只要最大分支个数b是有限

也就意味着每一层都能在有限的时间内搜索完毕

那么我们这个解肯定在某一层

那么我们一层一层的搜索下去

总能够搜索到解所在的这一层

把这个最浅层的解返回给你

在通常意义下，只要分支因子个数是有限的

我就能够找到解返回给你

那么我们再来看宽度优先搜索的时间复杂度

那么它的时间复杂度就是说在整个搜索过程中

在找到解返回之后，它总共产生的结点个数

也就说这里的时间复杂度

它估计的是一个上限

并不是要你准确的计算出来产生的结点个数

也就是说它是一个估计值，是一个上限

估计的是最坏情况下，最多不会超过这么多结点个数

那么来看一下假设这个问题我们的分支因子个数最多为b

也就是说结点最多产生b个儿子

这些分支点呢 最多有b个后续

那么我们来看到初始结点，就是b0层b的零次方产生了一个结点

然后到了第一层就是我们的初始结点

它最多产生b个儿子所以第一层就是b的一次方

然后第二层 第一层的b个儿子

每一个最多产生b个后续

所以到了第二层最多就是b*b也就是b的平方

然后到了第三层 这b的平方个结点

每一个也最多产生b个后续

所以到了第三层就是b的平方乘b，b的立方个结点

那么宽度优先搜索一直拓展 一直搜索

假设已经搜索到了第d层

那么第d层就是产生b的d次方个结点

这里d的意思就是最浅层的解所在的深度

也就是说这个时候假设我们的解，我们的目标结点在这个地方

那么大家看到，这个目标结点其实已经产生出来了

那么是不是到了这一层它就不再往下拓展了呢，回去了呢？

不是的，因为我们看到

这个树搜索算法什么时候才会知道这个结点是一个目标结点呢

只有当这个结点排在fringe表的队首

把它移出来准备进行拓展之前

也就是说把它取出来准备拓展之前

先判断一下这个结点是不是目标结点

如果是目标结点就不对它进行拓展就返回去

如果不是目标结点就对这个结点进行拓展

所以在它的父亲产生这个目标结点的时候

它并不知道这两个结点里有一个目标结点

只是简单的把这两个结点放到fringe的队尾进行排队

所以它还要继续往下进行，产生结点

也就是说呢，到了这一层，这些人排好了队 在fringe里面轮到它们了

那么我们最坏情况就是这个目标结点排在这一层的最后一个

所以要把这一层的其他结点先取出来进行判断是不是目标结点

不是，进行拓展，产生两个儿子

然后这个也是，先取出来看看是不是目标结点

不是，产生两个儿子

那么一直一直到这里轮到它了

从fringe表里取出来看看是不是目标结点

不是，产生两个儿子

然后最后才轮到我们的目标结点

取出来看一下是不是目标结点

是目标节点所以它就返回去了，不再对这个节点进行拓展

所以到此为止我们的宽度优先搜索算法就结束

不再进行拓展结点了

所以我们总共产生的节点个数就是这么多

最多就是这么多

所以我们来算一下

它就是b的零次方加b的一次方一直加到b的d次方

然后再加上最后一层

那么这一层产生多少个结点个数呢

我们知道除了目标结点不进行拓展

这层的其他结点每个最多产生b个节点

那么这一层本身有b的d次方个节点

减掉目标结点就有b的d次方减一个节点

每一个人产生b个儿子

所以这一层就是b的d次方减一乘以b个节点，所以加上这么多个

所以最后 这么一个式子累加起来

它的最高数量级就是b的d加1次方

所以这个就是它的时间复杂度

也就是我们用这个order来表示这个时间复杂度的数量级

那么它的空间复杂度是多少呢

我们前面讲过空间复杂度就是整个搜索过程

储存在内存里面的最大结点个数

那么我们看到宽度优先搜素

它一层一层进行拓展搜索的时候，产生出来的结点

他都不敢从内存里面删除

因为它直到找到解之前它不太清楚哪一条路径下面有解

哪一条路径下面没有解

所以它不敢把它产生出来的结点从内存里面丢弃

直到它找到目标结点发现它是解的时候

它才明白它只要储存这个

但是这个时候，到它把目标结点从fringe表里取出来看的时候

整个这些结点全部都储存在内存里面

所以整个运行过程当中的最大结点个数就是这么多

就是和我们的时间复杂度是一样的

最大的就是这个时候，这个时候就是这么多

所以它的空间复杂度和时间复杂度是一个数量级的

都是指数级的，都与b、d有关

那么这个是我们的空间复杂度

那么我们再来看宽度优先搜索有没有最优性

也就是说这个宽度优先搜索找到的解是不是一个最优的解

也就是说是不是一个代价最低的解

那么如果我们认为单步代价是一样的话

也就是说每执行一个动作它的代价都是一样的

那么就意味着最浅层的这个解是最优的

因为最浅层的这个解从初始状态到达它所执行的动作是最少的

所经过的步骤是最少的

我们的宽度优先搜索是可以保证找到一个最低代价的解给你的

因为它是一层一层搜索下来的

那么最浅层的这个解一定是被它优先找到的

所以他会把最浅层的这个解返回去给你

而最浅层的解是代价最低的

所以宽度优先搜索是具有最优性的

那么我们来看到宽度优先搜索的四个指标

那么最优性是一个很好的指标，完备性也相当令人满意

但是时间和空间都是指数级的

特别是空间复杂度，如果b、d很大

在我们的计算资源有限的情况下，那么这种算法是不实用的

也就是说不可行的

遇到复杂问题的时候，根本没有办法去做宽度优先搜索

因为空间上满足不了，这就是宽度优先搜索的性能指标