Video在线视频

那么接下来我们再来看第四种盲目搜索策略

叫做深度有限搜索

那么这种深度有限搜索是为了克服深度优先搜索
的第一个问题

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

也就是说有可能在无限状态空间里面

它找了一条路，这条路无限长，然后又没解

导致它可能就回不来

那么为了克服这个问题就对它进行改进

加了一个深度限制

也就是说呢让深度优先搜索走下去的时候

走到一定的深度层如果还没有找到解

就要让它回来换另一条路进行试探

就是这么一个思想

那么深度限制的深度优先搜索其实上实现起来是
很简单的

就是说和深度优先搜索是一样的，也是后进先出

但是出来对他进行拓展的时候，首先判断它是不
是解

然后还要判断它有没有达到深度限制

如果达到了深度限制，也不对它进行拓展

也是直接把它从内存里抹掉

这里的使用一个递归的方法来实现深度有限搜索

让我们来看一下怎么样用递归的形式来实现

也就是说它定义了一个递归函数

定义了一个递归算法来实现它

我们来看一下

也就是说这个是一个深度有限搜索

输入和前面的算法一样，问题的形式化给它

然后他还有一个输入参数是你给定的深度限制

当然这个限制的选择是要用户设定的

那么有的时候如果你的深度限制设置的太浅了

那么有可能有解你都找不到解就回来了

那么如果你深度限制设置的太大，对性能的改进
又没有多大的意义

所以深度限制的设置要取决于先验知识

或者说你通过不断的试探获得这么一个参数值

那么有了这个深度限制之后就给这个函数作为输
入

那么这个函数（算法）的返回值就是

要么返回一个解给你

要么它觉得整个空间都搜索完毕了，没有找到解

告诉你没解

另外一种失败的情况就是cutoff

cutoff意思就是说有可能空间里面有解

但是我没有找到解的原因是到达深度限制了

可能深度限制之下的结点可能是有解的

但我不清楚，所以它返回的是cutoff

告诉你我没有找到解是在深度限制条件之下没有
找到解

所以它是有三种返回值返回来的

那么整个的主体是由一个递归函数来实现的

这个递归函数的名字叫RECURSIVE-DLS

那么递归函数开始的输入是

也就是说他接受的初始参数是

问题的形式化，初始状态形成的一个初始结点

然后第二个参数就是问题的形式化要告诉它

然后第三个参数是深度限制

所以它就直接调用这个主体，就是这个递归函数

那么我们来看一下这个主体在这里

递归函数调用的主体

这个第一个参数 结点

那么一开始初始的时候，我们的Node是一个初始
结点进来的

然后问题的形式化，和深度限制

然后返回值也有三种，一种是解

一种是整个空间搜索完毕没找到解

另外一种就是我是达到了深度限制回来的

那么首先我们来看一下第一条语句

第一条语句是设定了一个旗标变量

这个旗标变量是一个cutoff

有没有发生过的一个旗标变量

那么这个旗标变量到时候会起到一个什么作用呢

就是到时候他要告诉到底是不是整个的搜索空间
没有解

还是整个的搜索空间是因为有一些路下面我没搜
索完，导致我没找到解

所以它设了这么一个旗标

当然它一开始是给它赋值为假

那么这个箭头是表示赋值的意思

那么再看第二条语句

第二条语句就是看一下

就是对调用它的这个结点，在进行拓展、搜索、
探索之前

先看一下这个结点对应的状态是不是目标状态

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

如果是目标结点，那用不着再往下进行搜索了

因为我已经找到一个解了，所以它马上回去了

就把这个解返回去，返回给调用它的这个人

也就是说一开始初始结点就是目标结点

那它就返回到这里来，返回到这里来之后

那直接这个算法就结束，就告诉你这个初始结点
就是目标结点

那么如果它不是目标结点，else，就是不满足

他不是目标结点，我们还要去判断它有没有到达
深度限制

也就是说如果它到达了深度限制

那么它也回去了，那么这个结点也不再往下进行
拓展

那么它也返回给调用它的这个人

就是我已近到达了深度限制，也没找到解

所以这条路没找到解，返回给调用它的这个人

如果又不是目标有不是到达了深度限制

那么才对这个结点进行拓展

所以它就对这个结点进行拓展

那么拓展的话呢可能会产生多个后续结点

也就是说多个儿子结点

那么我们就要一条一条路的试探下去

也就是说每一个儿子结点对应着一个搜索空间

那么我就从左到右按顺序对这些

分支结点（儿子结点）下面的状态空间进行搜索

所以呢它这里是一个for循环

这三条语句就是这个for循环的主体

那么假设对第一个儿子进行搜索，进来这个for循
环

搜索的思路呢还是深度有限递归搜索

那么这个搜索的思路呢还是深度有限递归搜索

往下走都是对结点进行拓展对结点进行判断

所以功能是一样的

只不过是这个时候我们要试探（搜索）的节点变
成了我的儿子

就是我要去搜索第一个儿子，第二个儿子

第三个儿子，一个一个来

也就是说搜索这个儿子下面有没有解

那再来根据这个儿子下面路径搜索的结果

来判断我要做什么样的操作

那么假设它的第一个儿子回来的结果是一个解

也就是因为这个函数有三种返回值

解、失败、cutoff

那么如果它返回来是一个解，那我们看一下它会
怎么做

那么返回来是一个解

先看这条语句这个循环主体的第一条语句它回来
了

然后再看第二条语句，看下这个解是不是cutoff

不是那这条语句不执行

else，否则的话再看看这个解是不是不等于失败

也就是说你返回来的是不是不是失败

也就是说你又不是cutoff又不是失败才会执行这条
语句

那么又不是cutoff又不是失败的话，那就是解了

那就跟我们刚才假设的一样，假设它返回来是解

那我们的就执行这条语句，他就会把这个解返回
去

那么这个for循环其它的也不执行了

直接返回给调用它的上一层

那么就把这个解返回去

然后它的上一层也发现是解，就返回去

所以就把这个解就返回去了，整个算法就结束了

那么如果这个儿子返回来的是一个失败

也就是死说你试探的这个儿子这条路下面没解

我都搜索搜完了这条路搜到底了，没解

没解怎么办呢？我们看一下

这个if不满足，所以这条语句不执行

else if这个if也不满足，因为它就是失败

所以这个语句它也不执行

那么这个for循环第一次迭代这三条语句就执行完
毕了

所以它就去执行这个for循环的第二次迭代

第二次迭代就去试探它的另一个儿子

也就是说你第一个儿子返回了一个失败

这个儿子下面没解，所以它就去试探第二个儿子

所以呢它就去看就去看第二个儿子，所以这个时
候后续结点就是它的第二个儿子

所以他就去试探第二个儿子下面有没有解

所以这个参数的后续结点就变成了第二个儿子

然后同样调用递归算法看一下第二个儿子下面有
没有解

假设第二个儿子返回的是cutoff

看一下它会发生什么

假设第二个儿子往下搜索的时候返回cutoff

也就是第二个儿子对应的路下面

我找找，搜索搜索，搜索到了深度限制了

都没有找到解，但是是因为到达了深度限制

不是因为这条路走不下去了，走到底了

所以它就返回一个cutoff，然后它就执行这条语句

这个条件满足确实返回的是cutoff

那它就开始把cutoff发生过的这个旗标设为true

意思就是cutoff发生过，要明白

然后再看这条语句，这条语句它会不会执行呢？

它说if我返回的是cutoff

如果返回的不是cutoff才回去执行这条语句

才会去判断这个，所以这条语句它是不执行的

那么这一次for循环它就结束了

同样的它知道第二个儿子下面已经到达深度限制

我也没有找到解，这条路我也已经试过了

试过了之后它就去试下一个儿子，第三个儿子

看一下第三个儿子下面有没有解

那么它就去试第三个儿子下面有没有解

如果第三个儿子也是返回一个失败

那么这个儿子执行到这条语句

这些都不符合条件

假设它只有三个儿子，三个儿子都试探完毕了

第一个儿子下面返回一个失败，没解

第二个儿子下面返回一个cutoff

第三个儿子也返回一个失败

我总共就拓展出来三个儿子，这个for循环执行了
三次

结束了，结束了之后我们来看一下

如果是这样的情况我们就要执行这条语句

也就是说我们中间没有找到解

也就是说这三个儿子下面都没解

它没有执行这条语句

所以这个for循环结束之后，它就会执行这条语句

那么它执行这条语句是什么意思

那么他就首先判断一下cutoff有没有发生过啊

如果发生过它就告知调用我的上一层

调用它的上一层肯定就是它的父亲结点调用的

父亲结点是一个个来试探

调用它的上一层，你调用我这条路是因为cutoff没
找到解

否则的话就告诉调用我的上一层结点

你选择试探的这条路下面没解，就告知它的上一
层

所以整个算法就是这么一个思想

所以它是利用一种递归的思想来实现的

就是父亲结点用这个算法进行搜索

然后它的每一个儿子也利用这个算法进行试探

然后再根据他们的结果来一层层返回来报告给上
一层

如果某一个分支下面没解或者cutoff

就告知它的上一层去试下一个儿子有没有解

那么一旦它在那个儿子路径下找到了解的话

它就一层层返回去，把这个解返回给你，不再去
试探别的分支了

那我们来看一下深度有限搜索的四个性能指标

或者说它所具有的性质

首先看一下它有没有完备性呢？答案是否定的

因为如果你深度限制设置的不好

可能在这个深度限制下面，这片状态空间里是有
解的

但是因为你没有往下进行搜索，导致它有解也找
不到解

由于你深度限制没设置好，设置的太浅了

导致它有解找不到解

那么再看它的时间复杂度

最坏情况下就是把所有l层以上的结点都搜索了个
遍

那么就是b的l次方

就是一直从b的零次方加到b的l次方

所以最高数量级就是b的l次方

那么再看空间复杂的

空间复杂度的话，因为它是一个深度优先搜索

也就是它是一条路一条路来进行试探的

一旦哪条路没有解它就会抛弃

所以他同样的任何时候都是只储存一条路径上的
结点

那么他最坏情况下在内存里储存这么多结点个数

就是储存整条路已近走到第l层了

那么一条有l层的路上面最多就是有b乘L个结点

所以它的空间复杂度的数量级就是b乘l

所以它是一个线性空间，这个和我们的深度优先
搜索是一样的

这个是一个很大的优点

那么他有没有最优性呢？

这个也是不能保证的

就是因为我们的深度有限搜索也是一条路一条路
进行搜索

它只要找到解它就回去了

它不会去比较、也不会去选择一个比较好的解给
你

所以这个是不能保证最优性的