Video在线视频

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

叫做迭代深人搜索

那么这种搜索策略是为了结合

宽度优先搜索和深度优先搜索的优点

想到的一个新的盲目搜索策略

也就是说宽度优先搜素策略有一个最优性的优点

深度优先搜索策略有一个线性存储空间的优点

迭代深入搜索策略就是结合了它们两者的优点的
一个搜索策略

那么大家看到它是什么意思

为什么叫做迭代深入搜索

其实上它就是运用深度优先搜索来实现的

只不过是把深度限制一点点加大（加深）

来实现这么一个迭代深入搜索

就是一层一层深入搜索下去

那么这个迭代深入算法的输入就是问题的形式化

它只有一个参数

然后它返回也只有两种情况

要么是找到解，要么是整个空间里没解，他返回
一个失败给你

那么这个算法有解的话就一定会找回解给你

要么这个空间是没解的

或者是这个空间是一个无限空间，并且没有解

那么这个算法可能会无限的循环下去

那么大家看到这个算法的输入就是问题的形式化

然后这个算法的主体是一个for循环

它是通过深度限制从零开始一直递增下去

直到找到解或者是整个的搜索空间搜索完毕

它才会退出这个循环

然后返回一个解或者是失败给你

那么它是由深度有限搜索来实现的

也就是说一开始深度限制设为零

一开始从第零层开始搜索

那么它去搜索看下有没有解

我们前面讲过深度有限搜索有三种返回值

一种是返回一个解，如果这个result是一个解的话

那么它就会执行这条语句

也就是说这个语句不是返回cutoff

也就是说不是到达了深度限制

这种情况返回来的是找到了解返回来的

那么它就会把这个解返回去

这个for循环就不再执行下去了，就从这个函数里
面return出来了，就回去了

那么如果这个result还有一种情况就是返回的是失
败

意思就是整个的空间我已经搜索完毕了，我也没
有找到解

那么把这个失败也返回去

这个for循环也不再执行了

意思就是整个的搜索空间已经搜索完毕了，也没
有找到解

所以就会返回给你告诉你

那么如果result是由于到达了深度限制没找到解

也就是说深度限制一开始是第零层

第零层没有解

那么是由于到达深度限制导致它没有往下搜索

那么这条语句肯定是不执行的

也就是说result会等于cutoff

那么这个for循环就会继续下去

那么这个深度限制就会加1，它就会变成1

那么这个时候就开始深度限制为1的一个深度有限
搜索

也就是说去看一下深度限制设为1的时候它能不能
找到解

那么同样的如果发现由于深度限制的原因导致我
没有找到解

那么它就会把深度限制又在加1，变成2

那么直到找到解或者整个空间搜索完毕为止

这个for循环才会结束，返回解或者失败给你

那么这就是迭代深入搜索的思想

所以从宏观上可以看出来

随着深度限制的加深，它是一层层往下搜索的

一开始深度限制为零当然就只搜索第零层

那么再接下来就是深度限制为1

那么它就是搜索到第一层

那么在接下来深度限制为2，搜索第二层

然后第三层，一直到找到解为止

如果你这个空间里有解，那么它一定在某个深度

只要它把深度限制设为最浅层的这个解所在的深
度

那么它扫到这一层的时候，他就找到了这个解

他就返回了，他就不在往下找了

所以它一定是找到一个最浅层的解给你

因为它这个限制是一点点加深的

它一旦找到最浅层的这个解

那么更深层的解它就不再找下去了

所以他就能够保证找到一个最浅层的（最优的）
解给你

这个是它的一个优点

另外的话因为它每一次实现的主体是通过深度有
限搜索来实现的

也就是说深度设置 设置好了之后

深度有限的限制设置好了之后

它的实现是用深度有限搜索来实现的

所以它对于空间复杂度的要求就很小，是线性的

也就是说它用的也是深度搜索的思想

也就是所一条路径一条路径搜索下去

一旦发现哪条路径没解它就会抛掉

所以它从宏观上来讲有宽度优先搜索最优性的优
点

从微观实现上来说，它用的是深度有限搜索

所以它又具有深度有限搜索线性空间复杂度的优
点

那么这个是迭代深入搜索策略的思想

看一下迭代深入搜索的过程

那么一开始深度限制是设为零的

那么设为零的话我们调用深度有限搜索

首先看一下这个初始结点是不是目标

不是目标在看一下它有没有到达深度限制

然后发现它到达深度限制了

那么这个迭代搜索就知道

没有解了又到达深度限制了

所以它就把这条路从内存里移出去了

表明没解了，然后这一次for循环就结束了

那么第二次for循环的时候这个深度限制就设为1

那么设为1的话它又去调用这个深度有限搜索

只不过是这个时候的深度限制是1

所以它从头开始，从初始结点开始

然后把初始结点拉出来看一下是不是目标

不是目标，有没有到达深度限制

没到达，所以呢就对它进行拓展

拓展就产生了B和C，产生B和C呢它先试探B

那么先把B看一下是不是目标，发现不是

那么有没有到达深度限制，到达了

所以他知道这个B这条路我已经搜索了，没有解

所以它把它从内存里移出去了

然后接下来就去搜索另外一条路C

这个C看一下是不是目标，不是

然后看一下有没有到达深度限制，到达了

所以呢它也认为这条路找过了没有解

所以把它从内存里移掉

那么A的两个分支都找过了，没有解

那么A也没解，所以它整个这条路全部从内存里移
出去了

所以这一轮for循环也结束了

表明在这个限制下我没有找到解

所以下一次for循环这个l就设为2

设为2的话就是我们的深度限制设为2去调用深度
有限搜索

同样的它又是从初始结点开始

看一下是不是目标，不是

不是目标呢，就看一下有没有到达深度限制

没有到达深度限制就对它进行拓展，产生B和C

那么先探索B这个儿子

那么探索B这个儿子呢，看一下B是不是目标

不是，有没有到达深度限制，没到达

所以对它进行拓展，产生D和E

拓展之后先对它的第一个儿子进行搜索

那么第一个儿子D先看一下是不是目标

不是，有没有到达深度限制，到达了

所以它认为这条路已经搜索完毕了

也没有找到解，所以这条路就从内存里移出去了

然后呢就搜索另一条分支，就是E这个儿子

那同样的看一下是不是目标，不是

看一下有没有到达深度限制，到达了

所以它认为这个分支他已经搜索完毕

没有找到接，所以这个也从内存里面移掉

那么B下面两条路都没有找到解

那么意味着B整条分支都没有找到解

所以整个的分支都从内存里移出去了

所以它去搜索另外一个分支就是C结点这个分支

那么C看一下是不是目标，不是

有没有到达深度限制，没到达

所以对他进行拓展产生F和G

那么先对它的第一个儿子F进行搜索

F拿出来看一下是不是目标，不是

然后呢有没有到达深度限制，到达了

所以它认为F下面这条路我也搜索过了，没有解

所以把它从内存里移出去了

所以接下来就搜索另外一个儿子G

看一下是不是目标，不是

有没有到达深度限制，到达了

所以它认为G这条路我也已经走过了，没有找到解

所以这个C下面没解，C下面没解就意味着A下面
没解

所以整个的都从内存里面移出去了

所以呢这个时候深度限制为2的时候我也没有找到
解

那么接下来我们的for循环就让他的深度限制设为3

那么深度限制设为3呢同样去调用深度有限搜索算
法，从头进行

从初始结点开始，先看一下A是不是目标，不是

有没有到达深度限制，没到达，然后产生两个儿
子

然后对第一个儿子先进行搜索

然后第一个儿子不是目标

然后呢有没有到达深度限制，没到达

然后呢就进行拓展产生D和E

然后又对D这条路优先进行拓展、搜索

D发现不是目标，又没有到达深度限制

所以对D进行拓展，产生H和I两个儿子

然后对H这个儿子进行拓展搜索

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

有没有到达深度限制，到达了

所以它认为这条路没有解，我已经搜索过了

所以把它从内存里移掉

然后搜索另外一条分支路I

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

有没有到达深度限制，到达了

所以它把这个I认为已经搜索过了，没解

可以从从内存里移掉了

那么这两个分支都没解可以从内存里移掉

那么他们的父亲结点D也可以从内存里移掉，整个
下面都没解

然后就去搜索另外一个分支E

然后看一下E是不是目标，不是

有没有到达深度限制，没到达

就对它进行拓展产生J和K

然后先试探J这个儿子，先看一下J是不是目标，
不是

有没有到达深度限制，到达了

那么就意味着这个分支下面没解

就把它从内存里移出去了

然后是另外一个分支K，看一下是不是目标，不是

有没有到达深度限制，到达了

那么意味着k这个分支也没解

那么这两个分支都没解，就意味着这个父亲E没解

那么整个这个都没解的话，那么整个B下面都是没
解的，没有用的，搜索过了的

所以都从内存中移出去了，开始探索另一条路

就是往右边的这条路

所以它就开始看一下C是不是目标，不是

有没有到达深度限制，没到达

所以对它进行拓展产生F和G

那么先试这条路F

那么F看一下是不是目标，不是

有没有到达深度限制，没到达

所以它就对它进行拓展产生L、M

那么首先也是先试探L这个分支

是不是目标，不是

有没有达到深度限制，到达了

那么发现没有解，所以把它从内存里面移出去

然后再试探另外一个分支

直到把限制为三的这些结点和路都试探完毕

如果都没有解的话再让它把我的深度限制变为4

所以整个的过程就是这样的

就是我们的深度限制一层一层的加深

但是在每一次设定好深度限制的时候

它实现又是由深度有限搜索来实现的

所以它任何时候储存的结点个数都是一条路径下
的结点

它不会储存多于一条路径下的结点

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