Video在线视频

再来看第三种盲目搜索策略,深度优先搜索策略

那么这种深度优先搜索策略是拓展最深层的未拓
展结点

也就是说它和我们的宽度优先搜索策略相反

宽度优先搜索策略是拓展最浅层的未拓展节点

那么深度优先策略怎么样实现拓展最深层的未拓
展节点呢

它是让fringe采用后进先出的队列

也就是说后来的让它排到队首去，让它先出来进
行搜索

比如说像这里一开始只有一个初始结点

我们的A结点放到队列里面，所以毫无疑问它排在
队首

优先出来，目标测试，看一下是不是目标

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

所以呢A就出去了

现在拓展新产生出来了B、C

那B和C是放在队首

也就是说每一次新产生出的结点都放到队首去

所以我们的B和C就在队首

然后呢下一次就把B拿出来进行目标测试

如果发现它不是目标然后对B进行拓展

拓展之后呢就产生D和E

所以B出去之后新产生的两个后续结点

同样的让它放到队首去

也就是说后来的放到队首去，让它先出来

所以这个时候我们的表里是D、E、C

那么D和E的深度是第二层，C是第一层

所以这个队列就自动把更深层的结点放到队首让
它现出来

所以就会优先拓展更深的这些未拓展结点

所以下一次就把D取出来进行拓展

D取出来我们看一下它是不是目标

不是目标对它进行拓展，产生H和I

那么同样新产生出的H和I放到fringe表的队首去

所以现在的fringe表里未拓展的结点是这样排序的

H、I、E、C

所以H、I是最深层的结点，放在最前面，优先进行
拓展

所以下一次把H拉出来看一下它是不是目标

发现它不是目标，然后又对H进行拓展

发现它已经没有后续了，也就是说这条路已经走
到头了

所以这个结点就变黑了

变黑的意思就是这个结点已经没有用了

因为我知道这条路已近走到头了，又没有后续

而且这个结点又不是解

所以这个结点就没有必要在内存里放着

他已经没有用了所以把它变黑了

那么像这个灰色的结点A、B、D是什么意思呢

就是它们已经拓展过了但是它们还有用的

因为有可能它们下面是有解的

所以他们还在内存里面

那么I、E、C这种白色底的结点是表明它们在
fringe表里面

他们是待拓展结点

就是属于叶子结点，到当前为止还没有拓展的结
点

然后也就是说现在我们fringe表的排序是I、E、C

那么下一次我就把I拿出来看一下是不是目标

然后如果不是目标我就进行拓展

那么进行拓展的时候我就发现这个I没有后续

没有后续的话那么I就要从内存里面踢出去

也就是说它没有用了

那么I一踢出去，那么D也没有用了

因为D下面的两条路都试探过了，搜索过了

没有解，那就意味着D下面是没有解的

那么这个D也是没有用的，我已经知道D下面是没
有解的

所以D和I都可以从内存里面删除

所以我们这三个节点就同时变黑了

现在我们的fringe表里是E、C在排序

那么下一次就是我们的E结点拿出来进行拓展

那么E结点拿出来进行拓展之后

同样的先看一看它是不是目标

发现它不是目标，然后呢就对它进行拓展

拓展发现它可以产生两个儿子J和K

那么J、K同样新产生出来的结点放到fringe的队首
去排队

所以现在排队是J、K、C

所以我们的J、K排在前面

所以下一次就把J拿出来进行拓展

同样的发现J不是目标

对J进行拓展的时候又发现它产生不出来儿子了

也就是说这条路已经走到头了，也没有解

所以J立马从内存里抹掉

然后接下来就是我们的K排在前面

所以K同样的拿出来进行目标测试，发现不是目标

然后对它进行拓展，发现K同样也产生不出来儿子

也就是说K这条路已经走到头了都没有解

所以K也没有用了，把它从内存里抹掉

那么K一抹掉，E就可以抹掉

因为E下面的两个分支路径都没有解

也就意味着E下面是没有解的

所以E就没有必要在内存里面存在了

所以E、K同时从内存里抹掉

那么E、K一从内存里抹掉，这个B就可以抹掉

为什么呢？因为B下面的两个分支都没有解

所以整个B下面都是没解的，这一部分搜索空间是
没解的

所以这个B也可以从内存里去除出去

所以K、E、B一试探完就从内存里剔除出去了

所以这个时候fringe表里C排在最前面

所以下一次就把C拿出来进行拓展

那么C进行拓展之前看一下它是不是目标

不是的话就让它进行拓展产生目标F、G

那么新的结点F、G就放入fringe表的队首

然后同样的下一次就是我们的F进行拓展

看一下F是不是目标，不是目标，然后对F进行拓
展得到L、M

所以L、M插到队首来

然后下一次就是我们的L进行拓展

那么L的话看一下是不是目标，不是，然后对它进
行拓展

同样的发现这个L已经走到头了

没有儿子，产生不出来儿子，那么L就没有用了

就把它从内存里面抹掉变黑

那么我们的下一次就是M排在前面

那么M排在前面呢，它同样的取出来进行拓展

看一下是不是目标，如果不是目标就对它进行拓
展，整个过程就是这样的

那我们来看一下这个深度优先的性能指标

它有没有完备性呢

也就是说在有解的时候它能不能保证一定找到解

这个答案是否定的

也就是说在无限状态空间中他就不能保证找到解

因为这个深度优先搜索可能先选择了一条没有解
又无限长的路径优先进行搜索

那么它可能就在这条没有解的道路上回不来

那么它就可能找不到解，那么完备性是不能保证
的

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

也就是说呢因为考虑的是最坏情况下

假设最坏情况下我们算法的路径选择的不好

那么它可能就是把整个的空间都搜索完毕了以后
才找到解

因为它一条路一条路试探

最坏情况下就是最后才选择了有解的这条路进行
试探

所以它的时间复制度最坏情况下就是把这个状态
空间都搜索了一遍

那么整个状态空间结点的数量级就是b的m次方

我们知道这个m的意思就是搜索树的最深层

或者说状态空间最深有多少层

当在无限状态空间里面m可能是无穷大的

所以时间复杂度

当然这个是一个最大上限

一般情况下达不到这种上限，这种几率太低了

然后再看第三个指标就是我们的空间复杂度

空间复杂度看到这里是一个线性的复杂度

也就是说是b*m

为什么是线性的呢？因为我们前面看到了

也就是说我们的深度优先搜索是一条路径一条路
径的试探下去

一旦发现哪条路径没解

它就会把这条路径上的结点从内存里面删除掉

也就是说它任何时候都只保存一条路径上的结点

以及这条路径上同一层的兄弟

比如说像现在它只保存了一个结点

在下面它就相当于保存了这条路径以及这条路径
上面一个兄弟结点

也就是这里的话才保存了三个节点

也就是说第零层最多b个，第一层最多b个

然后再看往下走，也就是说它沿着这条路下来

这条路上面这里第三层也是最多保存两个

这个第一层也是最多两个，最多b个分支树

然后它要沿着这条路一直走下去

再去搜索这边

所以它就顺着这条路一直走下去，就相当于这里
一个分支走下来 走到底

然后这个情况下是它储存的一个结点数

是b，b，这里的b是二，第零层也是最多两个

这个也就是这个时候存储的结点数

然后它一旦发现H没有解了，它就抛掉

I没有了，抛掉

进而这个分支没有解了它就抛掉去

这个时候存储的结点个数都比较少了

然后再看这个E他就往这条路径搜索了

这边这条路径它就已经废除掉了

所以在这个时候它存储的就是这条路上的节点

这条路上最多就是每一层b个

所以最多就是每一层b个结点

然后他发现K没有解，删掉；E没有解删掉；B没有
解，删掉

然后整个这条路径它就知道没解了

它就把这条路径整个从内存里面删掉

然后接下来就往这边走

所以左边部分内存里面已经没有了

然后往这边走F、C存储在里面

然后开始存储这条路径了

所以它就开始存储这条路径的结点在内存空间里
面

也就是说这里最多也b个

然后往这条路径走，先试探这条

这条路发现没有，它就把这条路删掉

也就是说呢它每一层最多存储b个

因为它整个运行下来，任何时候都只储存一条路
径下的结点

所以每一层它最多存储b个结点

那么我们的状态空间，我们的搜索树最深就是m层

这个m的意思就是搜索树的最深层

也就是说最多就是m层，每一层最多储存b个结点

所以我们就有m个b相加，所以就是m*b个结点个
数

也就是说我们空间复杂度是一个线性的空间复杂
度

所以说这个是我们深度优先搜索最大的优点

也就是说我们前面讲过，时间复杂度高的话你可
以等待

但是空间复杂度高的遇到这个问题复杂一点，规
模大一点

这个b大一点 m大一点 d大一点的时候

那么如果你用宽度优先搜索是根本运行不了的

那么深度优先搜索是一个线性的复杂度可以大大
的节约空间使得算法是可行的

所以深度优先搜索以及它的变种在实际问题当中
应用的非常多

那么我们再看它有没有最优性呢

也就是说它能不能保证找一个代价最小的解

这个是不能保证的

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

如果它选择了一条路上有解，但这个解不是代价
最小的解，它就会返回给你

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