❤️：文中可能会看到一些莫名的”*”，这是本地markdown转到博客里来有些地方转换的有问题，忽略即可，不影响阅读。

🧠经典的搜索算法搜索

搜索问题的定义

为达目标，寻找从初始状态到目标状态的行动序列的过程被称为搜索。

搜索算法输入的是问题，输出的是问题的解，问题的解以行动序列的形式返回。

搜索算法要做的就是生成后继并区分目标状态与非目标状态，这些搜索策略是以节点扩展的次序来分类的。

能知道一个非目标状态是否比其它状态更有希望接近目标的策略，称为有信息搜索策略或者启发式搜索策略。

对于算法性能考量的四个方面：

  • 完备性：当问题有解的时候，这个算法能否能保证找到解？

  • 最优性：这个搜索策略能否找到问题所要求的最优解？（例如：在罗马尼亚问题(城市路径问题)中，路径耗散值最小的即为最优解。）

  • 时间复杂度：完成求解过程需要花费多少时间？

  • 空间复杂度：执行算法的过程中需要多少内存？

对以下图（初始状态S，目标状态G）

选区_082

树搜索：

选区_083

图搜索：

选区_084

open表与closed表：

open表(开结点表，或称为边缘集)：即为待扩展的结点的集合（自然，待扩展的结点都是叶结点，还没被扩展嘛）。

在树搜索（TREE-SEARCH）算法的基础上，我们增加了一个新的结构–探索集，如此得到的新算法叫做图搜索（GRAPH-SEARCH）算法。

closed表(或称探索集)：即为已经扩展过的结点的集合。

♥️做closed表的目的主要是为了记住已经走过的路，避免探索冗余路径（即重复探索,如下图若不去避免可能二次探索Arad,而上面的三幅图展示的可以看出图搜索算法中在后面的探索中则把已扩展结点c和e都给舍弃不再向下扩展了。）。一个新生成的结点B若是与已经生成的某个结点A相匹配的话（即这个结点B（或者说A）已经在探索集或是边缘集中了。不管是在哪个集子里都说明我们已经访问过了，在closed表中自然不用说，这表明它可扩展的结点已经全部扩展完了，我们不需要再去访问它；而如果它是在open表中，那么我们需要做的是待到这个新生成结点的父结点将自己可以扩展的结点都扩展完了，再根据我们的搜索策略按顺序去对A结点进行扩展，因此我们我们不需要对它做什么多余的操作或者说不该把它当成另一个待扩展的有效新结点，即➡️括号外面接下去那句话👉），那么它将被丢弃而不是被加入到边缘集中（因为我们不该去反复记录同一个结点，否则这两个表就失去了它避免重复探索的意义了。）

l1

（ frontier即边缘集：已生成未拓展；closed即探索集：已拓展）

下面展示的便是一次搜索过程，可以看到在生成新结点的时候若该结点已经存在于边缘集或探索集中了则被舍弃。

l2

​ :arrow_down:

l3

​ :arrow_down:

l4

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ :arrow_down:

l5

无信息搜索策略（盲目搜索）：
无信息指的是除了问题定义中提供的状态信息外，没有任何附加信息		 有信息搜索策略（启发式搜索）：
指的是使用问题本身的定义之外的特定知识——比无信息的搜索策略更有效地进行问题求解
宽度优先搜索
(广度优先搜索,breadth-first search,BFS)		 贪婪最佳优先搜索
一致代价搜索（uniform-cost search） A*搜索（顺便说一下启发函数）
深度优先搜索（deepth-first search,DFS） 随机搜索
深度受限搜索（depth-limited search） 爬山搜索
迭代加深的深度优先算法
(iterative deepening search)		 模拟退火算法
双向搜索（不展开） 遗传算法

1.无信息搜索（盲目搜索）

解释：无信息指的是除了问题定义中提供的状态信息外，没有任何附加信息，无信息搜索方法只能访问问题的定义。

1.1宽度优先搜索 （广度优先搜索,breadth-first search,BFS)

69542

算法：

先扩展根结点，接着扩展根结点的所有后继，然后再扩展它们的后继，依此类推，即总是扩展深度最浅的结点。因此，一般地，在下一层的任何结点扩展之前，搜索树上本层深度的所有结点都应该已经扩展过了。

实现：

由于总是先扩展深度最浅的结点，故可以通过将边缘组织成FIFO队列来实现（就是说从根结点开始我们总是把新结点（该结点的深度自然要比父结点深）加入到队尾，这样我们会将一层的所有结点依次加入到队列，接着才是下一层的结点依次加入队列，如此一来浅层的所有老结点必然会在深层的结点扩展之前被扩展开来。）

⚠️注意点：宽度优先搜索具有一般图搜索框架，会忽视所有的边缘结点或已扩展结点的新路径（意思就是已经在open或者close表中的结点不会再走一遍了），因为可以看出，这样的路径至少和已经找到的一样深了（这里仅仅是从深度来看，未考虑路径权值）。所以说，宽度优先搜索总是有到每一个边缘结点的最浅路径。

性能：

完备性：✅（假设分支因子b是有限的）。

如果最浅的目标结点的深度为d，那宽度优先搜索在扩展完比它浅的所有结点之后最终一定能找到该目标结点。目标结点一经生成我们就知道它一定是最浅的目标结点，因为所有比它浅的结点在此之前都已经生成并且肯定没能通过目标测试（即判断是否为目标状态）。最浅的目标结点未必就是最优的目标结点（因为我们深度的加深不一定意味着路径代价的增大，要看具体的路径代价是怎么定义的。例如同样是从北京到上海，路线1: 北京➡️乌鲁木齐➡️成都➡️上海，和，路线2: 北京➡️天津➡️济南➡️扬州➡️南京➡️上海。如果以路程长度作为代价，那可以看出虽然第一条路线从北京仅仅往下三个结点就到了上海，而第二条路线则往下五个结点才到上海，然而从地理上来看可以知道明显是第二条路线路程更短，即在仅有这两条路线的情况下，走路线2才是最优解）。从技术上来看，如果路径代价是基于结点深度的非递减函数，那么宽度优先搜索是最优的。（🍎简单来看递增即意味着结点越深代价也越来越大；即使路径代价是非递减函数，那深处的结点也自然不会比浅处的结点代价小，那同样也没必要去换一条新的路径。）

附录中的【1.罗马尼亚地图】供以参考，可以看到路径权值并不是规律的，像这样的图在搜索时我们自然不能保证代价会随着深度的增加而变大。

🎍注：深度优先搜索的目标测试是在结点被生成的时候做，而不是结点被选择扩展的时候，原因是完备性中讲的，“目标结点一经生成就一定是最浅的目标结点”，即在结点生成时我们就能做目标测试看当前结点状态是不是目标状态，是的话问题就解决了 (虽然我们说的时候说的是所谓“最浅”的目标结点，就是说还可能找到其它的目标结点，但那就是最优不最优的问题了，就问题能够得到解决而言找到一个目标结点那这个问题就已经解决了。)，就不用再继续让其它结点往下扩展了，自然也不用等到这个结点被扩展的时候了。

最优性：

从技术上来看，如果路径代价是基于结点深度的非递减函数，那么深度优先搜索是最优的，因为越往下代价越大嘛。因此宽度优先搜索在单位代价或者说是每一步行动代价相等的情况下是最优的。

时间和空间复杂度：

想象一个每个结点有b个子结点，深度为d的搜索树，搜索的时间和空间复杂度都将达到指数级别。时间复杂度达到O(b^d^),空间复杂度将达到O(b^d^)。

🎍注1：对于任何类型的图搜索，如果每个已扩展的结点都已保存在探索集中，空间复杂度总是在时间复杂度的1/b内。

🎍注2👹👹👹 :出于对时间和空间复杂度的考虑，一般来讲，指数级别复杂度的搜索问题不能用无信息搜索的搜索算法求解，除非是规模很小的实例。

🎍注3：一般来说宽度优先遍历找到最浅的目标结点就算完成任务了，因此说不一定能得到最优解，如果对其进行改进，即在找到最浅目标结点时不立即退出，而是记录下这个目标结点的路径和路径代价（路径耗散），然后继续搜索如能得到多个目标结点，将它们加以比较，留下较优的结点，这样等把所有可能的路径都搜素完了之后再输出记录的最优路径，即得到的便是最优解了。

总结：

​ 缺点：问题规模上升时，时间复杂度和空间复杂度可能会很大。由于在找到目标结点之前需要把每一层都给遍历一遍，故消耗的时间大，而在上一层结点全部扩展完之前需要把所有生成的新结点都给存起来，因此占的空间要比深度优先大得多，在程序设计中必须要考虑溢出和节省内存空间的问题。

1.2 一致代价搜索（uniform-cost search，UCS）

解释：

从1.1的分析可以知道由于宽度优先搜索总是先扩展深度最浅的未扩展结点，所以它需要在所有结点路径代价随深度增加都非递减的时候才能实现最优（如当每一步的行动代价都相等时。）

而现在我们希望找到一个能对任何单步代价函数都是最优的算法。

于是我们不再选择扩展深度最浅的结点，一致代价搜索（uniform-cost search）扩展的是路径消耗g(n)最小的结点n。

算法：

上述目的可以通过将边缘结点集组织成按g值排序的队列来实现，每次扩展的都是g值最小的点。

实现：

如上所述的优先级队列

🎍注1：除了按照路径代价对队列进行排序外，一致代价搜索与宽度优先搜索还有两个显著的不同：

​ 看不懂下面的解释说的意思，就先看下面的具体例子(🤡)，然后结合着看看。

  • 一👤是目标检测是在结点被选择扩展时，而不是在结点生成时进行。因为第一个生成的目标结点不一定是在最优路径上。

    解释：当这个结点M被它的父结点A生成的时候，如果M恰好是一个目标结点，我又对它做了目标检测，那么自然符合目标状态，我便会选择它作为问题的一个解；

    「

    补充，这部分想了解一下就看看

    🧠要知道目标检测不是白做的，不是说做了之后如果它恰好是目标结点，我照样不选它还去看别的结点别的路径。目标检测只要是做了，做了之后找到目标结点了，那这个算法的任务就结束了，这个目标结点就是我最后要返回的值了，就是最后认定的这个问题的解了，否则目标检测就失去了它的意义了（见下面🎍注1.1：）。【🍎在搜索的过程中目标结点当然可能会出现多次，但要是被做了目标检测那就得被当作解没跑了。关于目标结点（假设叫B）出现多次的问题，在一般的图搜索框架里，如果B第二次出现（不管是和探索集还是边缘集中的结点重复了）那它就得被丢到垃圾桶里了不会被理睬，但是在一致代价搜索中则引入了一个额外测试（即下面要说的二👥），可以保留一个依赖于路径代价的更优结点（虽然它们都叫B，但是附带的路径代价可不一样）。】

    这也引出了一致代价搜索中另一个需要关注的点：即在一个结点被选中为要扩展的结点之前，我们是不知道它就是一个目标结点的，只有在它作为一个边缘集中普通的待扩展结点因g值小而被选中进行扩展的时候才会对它去做目标检测，这个时候我们会发现它就是目标结点，返回之。下面就来解释为什么在被选中要扩展时才进行目标检测。

    」

    继续解释：如果像上面所说生成就检测那找到一个目标结点这个算法就结束了，而我们随便想想，在整个图中明显是可能会存在更好的路径的（即代价小更优的解），当然不希望在这里就停下脚步而是想找到一个方法直接把那个最优的给检测出来，因此这就是不能一生成就检测的原因。

    🍎正向推理为啥被选中扩展时做目标检测可以得到最优解：

    我们选择把每一个新生成的结点都视作图中一个普通的结点（没做检测之前，自然每个结点看上去都是一样的普通的结点。）加入边缘集中，继续按照路径代价最低原则选择其中的结点进行扩展，可想而知如果有其它结点的g值比B低，那B就得一直呆在边缘集里，只能让其它某个g值小的结点P先被选中，并做目标检测，发现P不是目标结点，则将P扩展开来，如此继续下去（这过程中可能还会遇到其它结点扩展后也得到了B的情况，和普通结点一样使用「额外测试」（见二👥）留下一个代价小的），直到某时B的g值是边缘集中最小的那个，那么自然B被选中，做目标检测，发现它恰好是一个目标结点，找到解了！而此时边缘集中的那些结点的g值都比它大，那继续扩展下去自然路径代价越加越大（这里我们默认每个单步的代价都是正的），所以说此时到达B的路径代价就是最小的（放在更一般的结点上也可以知道，被选中扩展的结点必然已经找到了到达该点的最优路径），也就是说现在我们找到了问题的最优解！这里通过上面的分析也可以知道在算法运行过程中，每次有两条都能通往B的路径冲突时，是能选出代价更小的那条的，因此即使有冲突我们得到的也是路径代价路径代价越来越小的B，即每次冲突时B都能得到当前最优路径，直到像我们上面说的到了它有资格被选出做目标检测了，它所附带的路径代价必定是最低的，也就是得到了最优解了。

🎍注1.1： 目标检测，即判断当前结点状态是否为目标状态（也就是到这里我是不是已经完成了任务了），目标状态是看解的，是解就行，而不是还去管它是不是最优解。因此之前的宽度优先搜索为啥说得到的不一定是最优解呢？就是因为它的目标检测发生在结点生成的时候，当目标结点生成了，被检测到了，那任务就结束了，所以宽度优先搜索它最后得到的解永远只是最浅层目标结点所对应的一个解，只有在路径代价符合随深度非递减的时候**（关于这点的解释到上面去看宽度优先中「完备性处的🍎」，「🎍注」和「最优性」就明白了），返回的才是最优解，当然这个最优解此时就是在宽度优先搜索的最浅层，所以才会被返回。因此我们说如果想要一个“宽度优先搜索”总能够得到最优解，那就要对它作出改进「见宽度优先搜索🎍注3：」。

  • 二👥是如果边缘中的结点有更好的路径到达该结点那么会引入一个测试。

    解释：这里说有更好的路径说对任意结点说的（即对于某个结点M，有更优的路径到达这里），目标结点当然也适用。当边缘集中已经有了一个结点M，而某时当我正常地「依据路径代价最小的原则」对边缘集中的一个g值最小的结点P进行扩展时，扩展后也得到了M（即也得到了一条到达M的路径），但是一个边缘集中当然不能有两个一样的结点啦（这点没啥好深究的，边缘集里面就是这张图里面的一些点嘛，肯定不会放两次进去，在前面的一般图搜索中也说了遇到已经在边缘集中的会直接舍弃不会再放进去一次，不过这里涉及路径的更优代价，所以我们会做比较。），所以我要比较到达这两条路径的代价（即PATH-cost或是g），比如下面的B(278)，B(310)【我们定义的结点都是附带路径代价值的】，去选择代价更小的一条路径，边缘集中只保留这个路径代价值更小的M（如B(278)），这也说明了边缘集中加入的结点M其路径代价都是「当前」能找到的最低的路径代价，即其路径是「目前」能找到起点到M的最优路径。

🤡以具体例子说明：

下图五座城市简写为S，F，B，R，P。S为初始状态，B为目标状态，

设边缘集为E，Path-cost即为当前结点路径代价，下面用g(X)，（或称g值）表示。

当S扩展结束之后，边缘集中应该有F，R两个结点，现在则要对它们进行扩展，

E={F，R}，g(F)=99,g(R)=80;显然R的g值小，那么扩展R，「目标检测：当前结点状态非目标状态」，得到P，g(P)=97+g(R)=177；加入边缘集，

E={F,P}，g(F)=99，g(P)=177，g(F)<g(p)，选择扩展F，「目标检测：当前结点状态非目标状态」，得到B，g(B)=310(注意哦这个时候没有对B进行检测)，加入边缘集，

E={P,B}，g(P)=177，g(B)=310，g(p)<g(B)，选择扩展P，「目标检测：当前结点状态非目标状态」，得到B， g(B)=278，本应该将B(278)加入边缘集，但此时边缘集合已经存在B(310),

此时引入一次额外的测试，即判断两条到达B的路径哪个Path-cost更小，显然会选择B(278)，B(278)加入边缘集覆盖B(310)，成为边缘集中唯一的B结点，🎾我们当然不能让一个集合中有两个都叫做B的结点啦🎾。

现在要做的是对边缘集中的待扩展结点进行扩展，此时边缘集合中只有B(278)，于是选择对B(278)进行扩展，「目标检测：B(278)正是目标结点」，将B(278)作为问题的解返回，♥️且B(278)必然是最优解！♥️（不知道为啥是最优解🤷‍♂️？看上面的“🍎正向推理为啥被选中扩展时做目标检测可以得到最优解：”。）

IMG_6955

性能：

完备性：

AIMA3书上面的表述“一致代价搜索总是考虑当前路径的总代价，而不去考虑步数，所以如果存在零代价的行动，那么就可能陷入死循环—-例如NoOp行动。如果每一步的代价都大于等于某个正值$\varepsilon$，那么一致代价搜索就是完备的。”

我猜想这里存在零代价的行动应该是没法让当前结点某个扩展去到一个新的结点，而是指向自身（停留在当前结点），这样被指向的自身又是一个新结点，那这个新结点的代价自然还是最小的，所以还是选择它来扩展，然后又指向自身，所以是死循环吧。我本来想的零代价是，比如我要从北京到上海，那么如果中间有一个山东济南，然后从北京到济南的机票是免费的（以费用为代价的话那着一步就是零代价了），那么路径还是可以从北京扩展到山东然后去上海的，就不会有死循环。所以我感觉说死循环的话应该是上面那个猜想吧？另外它说是可能陷入死循环，那这两种都算是可以考虑进去的情况吧。

最优性：

经过前面的一通分析，显然一致代价搜索是最优的(当然是在上面所说的完备性的前提下)。

并且过程中也是按照每个结点的最优路径顺序进行结点扩展的（算法最是按照最小路径代价来选择扩展结点，所以越到后面被扩展的结点路径代价也就越大，或者叫做代价沿着路径是递增的）。由此往后，第一个被选择的目标结点也一定是最优解（本算法里讨论的都是代价都为正值，可以回看前面的分析，边缘集中无疑只能保留一个B结点，如果有更优的路径那被保留下来最后被选择的肯定就是那条路径了，而不会是现在这条(B(278))，所以既然最后被选择那就说明前面一定把比它长的都干掉了，可能会问那会不会还有没被发现到B的路径呢？也不会，如果边缘集中有一个P结点可以扩展到B并且代价更低，那首先P的代价就肯定比B(278)要小，可既然现在B(278)在边缘集中被选出来了，那说明它比边缘集中其它任何结点代价都要小，即也比P的代价小，P再往后扩展路径肯定就更大了。），所以选择完了目标检测符合了，这个算法也就结束了。

时间复杂度、空间复杂度：

一致代价搜索是由路径代价而不是深度来引导的，所以不能单纯的用b,d来表示算法的复杂度。

我们引入一个C^*^用来表示最优解的代价，假设每个行动的代价至少为$\varepsilon$，则最坏的情况下算法的时间和空间复杂度为b^k^

(因为符号冲突原因我好像打不了这么复杂的公式，

所以这里说明一下：

令C^*^= k1 , 最优解的代价

k1/ $\varepsilon$ =k2, 即需要多少步(在生成最后最优解的目标结点时的探索深度，也就是最优结点上一层)

1+$\lfloor k2 \rfloor $=k；因为被生成时不检测，所以生成后最优目标这一层在选择被扩展结点时还要再扫一遍，所以+1

宽度优先其实也是这样，如果深度优先不选择生成时检测，而是扩展时检测,那时间复杂度准确来说就是该就是O(b^d+1^)了。)

这个代价其实要比b^d^ 大得多，因为一致代价搜索在搜索包含大代价的行动之前，经常会搜索代价小的行动所在的很大的搜索树（因为结点扩展是按g值从小到大来的嘛），当所有的单步耗散都相等的时候，b^k^ 就是b^d+1^ ，此时一致代价搜索除了终止条件外与宽度优先搜索类似（因为此时往前扩展一个点，即深一层，那么总代价就多一个单步耗散值，因此所有的同层结点往下延伸的时候都是增加一样的代价，和宽度优先搜索类似）。 宽度优先搜索找到一个解就终止了，而一致代价搜索则会检查目标深度所有结点看谁的代价最小，如此一来一致代价搜索在深度d做了很多无意义的工作，不过当然了这样可以找到最优解。

从下面的图中可以看出来，S扩展开来之后，扩展顺序是

先扩展R，得到P，代价177，

再扩展F，得到B，代价109，

再扩展U，得到V，代价150，

这时选择扩展B，目标检测发现它是目标结点，任务结束。

可以看到第二步就已经得到我想要的B了，可是我却不能知道它就是目标结点（因为目标检测必须得在被选中扩展的时候做），但是为了防止有更小的代价路径，不得不再去和其它结点做代价比较，如果比下来就是它最小那还算好，可是这里居然U的代价比它还小，那就得先扩展U，完了之后再比较，这时候发现B的代价最小，选它做扩展，结果目标检测一做发现它就是目标结点。。。也就是说从我得到这个点到我确定它是解我又多走了了两步。

当所有的单步耗散值都一样时，比如都是1，那从s出发F，U，R的代价都是一样的，那在找最小的代价时可以知道这三个点都会被扩展开来，得到B，V，P，代价也都是一样的，在对它们进行比较之后，它们都会被选中扩展，这时候B就会被检测出来是目标结点。可以看出这样一来一致代价搜索就宽度优先搜索一样都是逐层向下了，只是每次扩展的时候还是会多出比较的步骤。

IMG_6958

1.3 深度优先搜索（deepth-first search,DFS）

算法：

深度优先搜索总是扩展搜索树中当前边缘集中最深的结点，如此一来搜索很快就会推进到搜索树的最深层，那里的结点没有后继，当那里的结点扩展完了之后，就从边缘集中去掉（即发现它没有后代了，没法再继续扩展了就不要留在边缘集里了，因为它无后了，即不再有其它结点与它相连，因此把这些没有后代的结点从内存中删除即可。），然后搜索算法回溯到下一个还能扩展的深度稍浅的结点。

实现：

使用LIFO队列（后进先出，即用栈），最先生成的结点将最早被选择扩展。可以以递归实现。

图1

性能：

深度优先搜索的效率严重依赖于使用的是图搜索还是树搜索。

完备性：

图搜索可以避免重复状态和冗余路径，因此在有限状态空间是完备的，因为可以扩展到所有结点。

而要是使用树搜索，则不完备了。

（可以看一下附录里面的罗马尼亚地图，如果用树搜索算法以以下所示搜索树进行扩展（默认从左子树先开始）。从Arad开始，下一个则是Sibiu，由于没有重复避免，则下面又到了Arad，如此便陷入了死循环，故不完备。）

在无限状态空间中，都是不完备的。因为在无限状态空间里，如果遭遇了无限的又无法到达目标结点的路径，则无论是图搜索还是树搜索都会失败。

IMG_6966

图2

最优性：

无论是基于图搜索还是树搜索的深度优先搜索都不是最优的。

例如图1中的例子，假设J和C代表的都是目标结点，但是由于深度优先搜索会先搜索整个左子树，那么当它搜索到J时就会返回J，即使C是更优解也没用，这其实和宽度优先搜索是一个道理，看到解就返回根本不去管后面有没有更好的解了。

时间复杂度、空间复杂度：

深度优先搜索的时间复杂度受限于状态空间的规模，甚至可能是无限的

从上面可以看出深度优先搜索似乎没啥优势，事实上它最大的优点就是在空间复杂度上了，只有线性大小。

深度优先搜索只需要存储一条从根结点到叶结点的路径，以及该路径上每个结点的所有未被扩展的兄弟结点即可。一旦一个结点被扩展，当它的所有后代都被探索过后该结点就从内存中删除，可参见图1.假设状态空间分支因子为b，最大深度为m，深度优先搜索只需要存储**O(bm)**个结点。

以d=16,b=10为例，宽度优先要存10^19^ 字节，而深度优先只要156K字节，节省了大约7000亿倍空间。。。

因此深度优先搜索在AI的很多领域成为工作主力，其中包括约束满足问题（第六章），命题逻辑可满足性（第七章）和逻辑程序设计（第九章）。

深度优先搜索的一种变形称为回溯搜索，所用的内存空间更少（详见第六章）。回溯搜索每次只产生一个后继，而不是生成所有的后继，每个被部分扩展的结点要记住下一个要生成的结点，如此内存只要O(m)而不是O(bm)。

回溯搜索催化了另一个节省内存和时间的技巧：通过直接修改当前的状态描述而不是先对它进行复制来生成后继，这可以吧内存需求减少到只有一个状态描述以及O(m)个行动。为了能达到这个目的，当我们回溯生成下一个后继时，必须能够撤销每次修改。对于状态描述相当复杂的问题，例如机器人组装问题，这些技术是成功的关键。

1.4 深度受限搜索（depth-limited search）

在无限状态空间中，深度优先搜索会比较尴尬，我们可以通过对深度优先搜索设置界限L来避免，简单来说就是深度为L的结点就被当作没有后继来对待了。深度界限解决了无穷路径的问题。

然而这也有很多问题。

加入最浅目标结点在所在深度为d，而我们设置的L<d，那最浅的目标结点的深底都超过了深度限制了，显然当算法结束时我们回以找不到解失败而告终，也即这种搜索算法是不完备的。

而如果我们设置的L>d,那像上面分析一般的深度优先所说的那样，也可能找不到最优解，即这种搜索算法不是最优的。

而且对于大多数问题，我们根本没法提前判断怎么样去设置一个合适的深度界限。

由于深度界限的设置，深度受限搜索的失败原因可能会有两种：一是标准的failure返回值表示无解，二是cutoff代表在深度界限内无解。（如果搜的过程中碰到界限了此时没搜到目标结点，那就算是深度界限内无解了，要是搜完了都没碰到界限而且还没解，那就是正常的问题无解了。）

深度优先搜素可以被看作是特殊的深度受限搜索，其深度界限为L=∞，也就是没设限呗。

1.5 迭代加深的深度优先算法（iterative deepening search，IDS）

解释：

迭代加深的深度优先搜索是一种常用策略，经常和深度优先搜索结合使用来确定最好的深度界限。

算法：

做法是不断增大深度限制，首先是0，接着是1，然后为2，依此类推——直到找到目标。当深度界限达到d,即最浅的目标结点所在深度时，就能找到目标结点。（可看下图）

完备性与最优性：

和宽度优先搜索一样，当分支因子有限时，该算法是完备的；当路径代价是结点深度的非递减函数时该算法是最优的。

当我们说深度优先搜索时候我们说他打不到最优是因为(不妨设搜索树中先搜左子树，再搜右子树)，我们在左子树中一查到底在很深的地方A找到了目标结点(即找到了一个解)，但是可能右子树上第一个结点B就是目标结点，可是深度优先也是找到解就返回了，所以它找不到B这个最优解。

而迭代加深就不一样了，它的探索深度是一层一层往下加深的，所以当我们的当前深度限制为1的时候，就已经可以找到B了，即是可以找到最优解的, 有点儿宽度优先那个味儿了。(当然也需要代价关于深度非递减就是啦。)由上所说，也可以知道，我们最先找到的，其实就是最优解(就是在最浅层嘛)。

时间与空间复杂度：

b: 分支因子数；d：目标结点深度

迭代加深的深度优先搜索算法结合了深度优先搜索和宽度优先搜索的优点，它的空间需求是合适的O(bd);

这个算法看起来比较浪费，因为状态被多次重复生成。但是事实上代价并不是很大，原因是在分支因子相同(相似)的搜索树中，绝大多数的结点都在底层，所以上层的结点重复生成多次影响不大。在迭代加深的深度优先搜索中，底层(深度d)结点只被生成了一次，倒数第二层的结点被生成了两次，依此类推，一直到根结点的子结点被生成了d次，因此生成结点的总数为：

​ N(IDS)=d*b+(d-1)*b^2^ +……..+1b^d^ ，

时间复杂度为**O( b^d^ )**，与宽度优先搜索相近。重复生成上层结点需要付出额外的代价，但不是很大。如，

当b=10，d=5时，数目分别为：

N(IDS) = 50+400+3000+20000+100000 = 123450;

N(BFS) = 10+100+1000+10000+100000 = 111110;

如果还是担心状态的重复生成的话，那可以将本算法和宽度优先混合使用，先用宽度优先搜索直到有效内存耗尽，然后对边缘集中的所有结点应用迭代加深的深度优先搜索。

迭代加深的深度优先搜索和广度优先搜索相似，每次迭代要把当前层的新结点全部探索一遍。

还有一种算法是将一致代价搜索和迭代加深的深度优先搜索结合，在一致代价确保最优化的同时避免了大量的内存需求，主要思想是用不断增加的路径代价界限代替不断增加的深度界限，基于这种思想的算法被称为迭代加长搜索(iterative lengthening search)。不幸的是，与一致代价搜索相比，事实上迭代加长搜索将导致额外的开销。

总结：一般来说，当搜索空间较大并且不知道解所在深度时，迭代加深的深度优先搜索是首选的搜索方法。

IMG_6969

1.6 双向搜索

解释：

同时运行两个搜索，一个从初始状态向前搜索，同时另一个从目标状态向后搜索，我们希望他们在中间某点相遇，此时搜索终止。

算法：

将目标测试替换为检查两个方向的搜索的边缘集是否有相交，如果交集不为空那么就找到了一个解了（通过那个结点就可以把正反向路径给连接起来了）。但是这样找到的可能不是最优解

1.7 无信息搜索基本算法的一些结论：

IMG_6970

  • 宽度优先搜索：总是扩展搜索树中深度最浅的结点。算法是完备的，在单位代价的情况下是最优的，但是具有指数级别的空间复杂度。

  • 一致代价搜索：扩展的是当前路径代价g(n)最小的结点，对于一般性的步骤代价而言是最优的。

  • 深度优先搜索：扩展搜索树中最深的结点。它既不是完备的，也不是最优的，但是它具有线性的空间复杂度。深度受限搜索在深度优先搜索上加了深度限制。

  • 迭代加深搜索：在不断增加的深度限制上调用深度受限搜索直到找到目标。它是完备的，在单位代价的情况下是最优的，它的时间复杂度可与宽度优先搜索比较，具备线性的空间复杂度。

  • 双向搜索：可以在很大的程度上降低时间复杂度，但是它并不总是可行的并且可能需要太多的内存空间。

搜索算法 备注 结点扩展方式 完备性 最优性 时间复杂度 空间复杂度
宽度优先搜索 总是扩展搜索树中深度最浅的结点 ✅（当然需要分支因子有限就是了） 单位代价情况下是最优的 O(b^d^ ) O(b^d^ )
深度为d,每一层都有b个结点
一致代价搜索 扩展的是当前路径代价g(n)最小的结点 分支因子有限，对于每个单步代价都是正数的问题✅ 一般性的步骤代价而言是最优的 b^k^(令C^*^= k1 ,k1/ $\varepsilon$ =k2, 1+$\lfloor k2 \rfloor $=k) b^k^(令C^*^= k1 ,k1/ $\varepsilon$ =k2, 1+$\lfloor k2 \rfloor $=k)
深度优先搜索 扩展搜索树中最深的结点 ❌ ❌ O(b^m^ ),甚至可能是无限的 线性，O(bm)
深度受限搜索 在深度优先上加了深度限制 L<d,不完备；
L>d,当正常的有限状态空间的深度优先看也不完备		 L<d都找不到解更别说最优了；
L>d,当正常的有限状态空间的深度优先看也不是最优		 O(b^l^ ) O(bl)
迭代加深搜索 在不断增加的深度限制上调用深度受限搜索 ✅（需要分支因子有限） 单位代价情况下是最优的 可与宽度优先比较O(b^d^ ) 线性O(bd)
双向搜索 并不总是可行 分支因子有限，双向都使用宽度优先搜索时✅ 单步代价，双向都使用宽度优先搜索✅ 很大程度上降低时间复杂度,双向都用宽度优先O(b^d/2^ ) 可能需要太多的内存空间，双向都用宽度优先O(b^d/2^ )

2 有信息搜索（启发式搜索）

解释：有信息搜索即除了使用问题本身的定义之外，还能利用特定的知识，能比无信息搜索策略更加有效地进行问题求解。

我们要考虑的一般算法称为最**佳优先搜索(best-first search)**。

最佳优先搜索是一般TREE-SEARCH和GRAPH-SEARCH算法的一个实例，结点基于评价函数f(n)值被选择扩展。

评估函数被看作是代价估计，因此评估值最低的结点被选择首先进行扩展。

最佳优先图搜索的实现与一致代价搜索类似，只不过最佳优先搜索是根据f值而不是g值对优先级队列排队。

对f的选择决定了搜索策略，大多数最佳优先搜索算法的f由**启发函数(heuristic function)**构成：

​ h(n) = 结点n到目标结点的最小代价路径的代价估计值；

(要注意的是h(n)以结点为输入，但它与g(n)不同，它只依赖于结点状态，拿罗马尼亚问题举例，我们可以用Arad到Bucharest的直线距离来估计从Arad到Bucharest的最小代价路径的代价值。)

启发式函数，是在搜索算法中利用问题额外信息的最常见的形式。目前我们假设启发信息是非负的由问题而定的函数。有一个约束：若n是目标结点，则h(n) = 0;

2.1 贪婪最佳搜索（greedy best-first search）

解释：

贪婪最佳搜索总想扩展离目标最近的结点，理由是这样可能可以快点儿找到解。

因此，它只用启发式信息，即f(n) = h(n) ;

将此算法应用到罗马尼亚问题中，使用直线距离启发式，记为hLSD。

如果目的地是Bucharest，那么我们需要知道到达Buchares的直线距离，如下图所示。

如hLSD(In(Arad)) = 366。要注意的是，hLSD是不能由问题本身的描述计算得到的，所以说是在利用额外的信息嘛。而且根据日常经验，hLSD和实际路程是相关的，因此这是一个有用的启发式。

IMG_6972

下面👇是使用了hLSD的贪婪最佳优先搜索寻找Arad到Bucharest的路程的过程。

A生成了新结点S，T，Z，即从A出发可以到达S，T，Z，而根据上面给出的表格，S到B的直线距离最近，故扩展S，下面同样的道理选择扩展F，而F生成的新结点中就有Bucharest,也就是目标结点。

对于这个问题，使用了hLSD的贪婪最佳优先搜索在没有扩展任何不在解路径上的结点的情况下就找到了问题的解，因此我们说他的搜索代价是最小的。这就是为啥说他是贪婪的，因为每一步他都想要试图找到离目标最近的结点。然而事实上它却不是最优的。下面在贪婪最佳优先搜索的不足中具体说明。

IMG_6974

👹贪婪最佳优先搜索的不足👹：

  • 不是最优的。比如上面的例子中(A,S,RV,P,B)实际上要比（A,S,F,B）的路径要短32公里，也就是说它贪婪到最后反而跑远了，这是因为它过度依赖hLSD，总是看着最短的直线距离，可事实上直线距离短的真正走的时候他的路不一定就短，导致最后反而多走了，也就是没能找到最优解。

  • 是不完备的。也就是它不只是像上面说的找不到最好的路，它可能到都到不了。比如它可能会沿着一条无限的路径走下去而不回来做其他的尝试，到死也找不到目标结点，比如下面的螺旋上经过无限个点才能到达Bucharest；或者再举个例子，加入在Bucharest周围有一圈儿城市，但是他们就是没往Bucharest修路，而最近的往Bucharest修路的城市C在这个城市圈的外面，哪怕城市圈理由很多路可以去C，那这个算法也一直都不会去找到外面那个城市。

    这两个例子大致情形如下图所示：

IMG_6977

图1中设置了无限个城市点，那么他也就有了无限状态空间，如此一来这个算法总可以找到距离B直线距离更近的城市，但是却在这条无限路径上永远到达不了B。而事实上我们完全可以从A到C再到B，甚至即使选择了D也还有路到C去再到B，但是这个算法却选不出来，因为“他觉得C离B太远了”。

图二中设置了环形城市圈，当他由D到E进入城市圈了之后，如果按照树搜索的方式，那她最后会在城市圈儿里陷入死循环；而即使按照图搜索的方式在圈上走，走过的我们就不再走了，那最后当他把所有城市都走过一遍，边缘集里没有待扩展的结点了，那也就没法再往下走了，只能以failure告终。而事实上，不管是从A到C再到B，还是从圈上的E，F，G，H到C再到B都可能得到这个问题的解，可按照这个算法最后就是找不到解(图搜索也有另一种情况，就是假如走完一圈之后到了圈上E左边那个点，叫M，假如M有一条道C的路，那从M倒是可以扩展到C，然后是可以找到解的)。

当然如果不考虑图二这种城市圈孤立点的特殊情况的话，就是正常的像罗马尼亚问题那样相互都有路径连接（即结点距离都为常数而不是无限的话）的情况的话，那图搜索版本的该算法在有限状态空间则是完备的，而树搜索（见下面一点）则是不完备的了，无限空间都是不完备的。这点结论和深度优先一样。

  • 启发函数代价最小化这一目标会对错误的点比较敏感，比如在罗马尼亚地图中，想要从Isai到Fagaras。

k356

从图上来看Iasi扩展得到的结点有两个，故得到边缘集{N,V}，而Neamt到Fagaras的直线距离明显要比Vaslui到Fagaras的直线距离小得多，故贪婪最佳优先搜索算法必然会选择Neamt进行扩展，不料这里是个死胡同，N扩展会得到Iasi，那么此时边缘集就变成了{Iasi,V}，而同样可以知道论到Fagaras的直线距离，Iasi要比V更近，因此此时算法便又会选择Iasi进行扩展，而下面自然又会选择N进行扩展，如此一来便进入到了死循环中，永远找不到解。可事实上Iasi ➡️ V ➡️ U ➡️ B ➡️ Fagaras，便得到了一个解。

🍎 这一点看上面的环形城市圈的例子也是一样的意思。

  • 最坏的情况下，贪婪最佳优先搜索算法的**时间和空间复杂度都会达到O(b^m^)**。

而事实上，如果有一个好的启发函数，复杂度可以得到有效降低，下降的幅度决定于特定的问题和启发式函数的质量。

2.2 A*搜索：缩小总评估代价

解释：

最佳优先搜索最广为人知的形式称为A*搜索，它对结点的评估综合了g(n)与h(n)，即初始状态到达此结点已经花费的代价和从该结点到目标结点所花的代价，评估函数表示为：

​ f(n) = g(n) + h(n) ；

即：

​ f(n) = 经过结点n的最小代价解的估计代价 ；

说白了就是估摸着的经过这个结点n的路径能达到的最小的路径代价（这里的代价指的是从开始结点到目标结点的总代价，故同时用上了g和h）。

按着这样的思路，那么我们在扩展结点时的合理思路就是，既然我们想要找到代价最小的解，那就应该总是先扩展g(n) + h(n)的值最小的结点。

*我们将会发现这个策略它不仅仅是合理的，假设启发式函数h(n)满足特定的条件，那A既是完备的，又是最优的（下面具体阐述）。**

可以看出，A搜索算法和一致代价搜索类似**，除了A用的是g + h而不是 g** 。

保证A*最优性的条件：可采纳性（亦称可容性）和一致性（亦称单调性）

①保障最优性的第一个条件是h(n)要是一个**可采纳**启发式

可采纳启发式是指，它从不会过高地估计到达目标的代价，也就是说我们不会把后续代价估计得比实际后续要花的代价还高，而由于g是已经当前路径到达n点的实际代价，那我们可以得出结论：

​ f(n)永远也不会超过经过n的解的实际代价。

就是估的肯定比回头实际用的代价要小。

可采纳性的启发式一个明显的例子就是之前讲的贪婪最佳优先搜索中的直线距离hLSD，两点之间直线距离最短，自然不会超出实际距离，即用直线距离去估计要跑的距离那肯定是不会高估的。

可以看一下A* 搜索算法求解罗马尼亚问题的过程，过程参见「附录：罗马尼亚问题的A*解法（h(n)=hLSD），即书上的图 3.24」，这里主要提几点说明，

  • 每次扩展都选择边缘集中f最小的结点(即我在图里写的采取全局择优搜索)，算法就是这样定义的，这不用解释了。

  • 另外就是***目标检测发生在结点扩展时，而不是结点生成时*****，这点可以从步骤(e)和步骤(f)看出，在步骤(e)的时候其实Bucharest已经生成了(Bucharest(450))，即已经被放进了边缘集中，但是却没有被选中扩展，而是选了Pitesti(417)进行扩展，因为417<450，算法认为可能经Pitesti能得到更低代价的路径，即更优的解，【补充说明：事实上我们在这里本来就不该将Bucharest(450)看得这么特殊拿出来专门比较，类比在一致代价搜索说的就可以知道，这里算法运行过程中我们应该只关注f值，在步骤(e)中450太大了，他根本就不可能被选中进行扩展，那自然也不会被检测，也就不可能知道它就是一个目标结点了，这里拿出来比较只是因为人眼看去一眼就看到了这是个目标结点，在这里说明比较一下只是为了便于理解，算法运行过程中417<450的比较只是两个边缘集结点的f值的普通比较罢了。】这样一来便由Pitesti扩展得到了Bucharest(418)，与450相比当然是把这个估价小的放入边缘集合，这时候可以看到Bucharest(418)在边缘集所有结点中是f值最低的结点了，此时显然Bucharest(418)是更好的选择，于是目标结点在Bucharest(418)被选中扩展时检测得到。

    其实这样一来也能看出，*A *和一致代价搜索确实是很像的 *，撇去结点扩展标准，其实算法过程中的思想可以说是一样的。

②第二个条件略强于第一个条件，被称为*一致性**（有时候也称作单调性）,**只作用于在图搜索中使用A算法**。

  • 假设结点n通过某个a（action）生成n的任意后继结点n^‘^,n到n^‘^的这个单步代价即为c(n,a,n‘)，那么

所谓h(n)是一致的，即对于任意的结点n，h(n)满足：

​ h(n) <= c(n,a,n‘) + h(n^‘^ )；

也就是说对于任意一个结点n来说，

【从该结点n到目标结点的估价】，总不超过，【它到任意一个后继结点的单步代价】+【这个后继结点到目标结点的估价】

（这是一个一般的三角不等式，保证了三角形中任何一条边的长度不大于另外两条边之和。这里三角形是由n，n^‘^，和离n最近的目标结点Gn构成的。）

  • 对于可采纳的启发式，这种不等式有着明确的意义：

如果从n经过n^‘^ 到Gn 的代价小，就违反了h(n)的性质：h(n)是到达Gn的下界。

【

上面这句话这里的代价说的就是实际代价，

(其实从可采纳的定义来看就是在说明h(n)是n到达Gn的实际代价的下界)

下面的话主要是要说明在可采纳性的保证下，由一致性的不等式也可以推出h(n)是n到达Gn的实际代价的下界

用一致性来看，

首先由可采纳性知道h(n^‘^)是不超过n^‘^到Gn 的实际代价的，由于c表示的是单步实际代价，那么就有

h(n) <= c(n,a,n‘) + h(n^‘^ ) <= c(n,a,n‘) + n^‘^到Gn 的实际代价 = n经 n^‘^到Gn 的实际代价；

注意哦，我们之前假设的是n的任意后继结点，所以以上的不等式即表明：

h(n) <= n通过任意路径到达Gn的实际代价

即，h(n)是n到达Gn的下界，就是说从n出发，无论走什么路也不应该有比h(n)代价更小的了，这就是为啥说

如果从n经过n^‘^ 到Gn 的代价(实际代价)小，就违反了h(n)的性质：h(n)是到达Gn的下界。

】

  • 一致的启发式都是可采纳的

    虽然一致性比可采纳行更严格，按理来说应该有很多满足了可采纳性但满足不了一致性的启发式的例子，但实际上这样的例子并不好找（也就是说其实大多数情况下满足要求的启发式往往两个性质都满足了）。我们在本章探讨的可采纳的启发式也都是一致的。

    例如之前所说的罗马尼亚🇷🇴问题中的启发式函数hLSD，他估计的都是直线距离，肯定不超过实际距离，所以显然是满足可采纳性的 h(n) <= n到Gn 的实际代价；

    对于n，n‘，Gn，如下图所示，根据三角不等式，可知有：

                                                              c(n,a,n‘)   +    h(n' )   =   L  +   h(n' )      >=    h(n) ；

    即

    ​ h(n) <= h(n’ ) + c(n,a,n‘) ；

4k5031

证明一致的一定是可采纳的：

对于一个一致的启发式，即满足：

h(n) <= c(n,a,n‘) + h(n’ )

假设n距离目标结点的最短路径有若干个结点，n’在最短路径上，

当有1个结点，即n’ 是目标结点，则h(n’ ) =0，

有：h(n) <= c(n,a,n‘) ，即h(n)不超过n到目标结点的实际代价，h(n)是可采纳的。

现在假设在n到目标结点的最短路径上n‘距离目标结点有k个结点时，h(n)是可采纳的，则

h(n) <= c(n,a,n‘) + h(n’ ) <=c(n,a,n‘) + h*(n’ )=h*(n)

即当结点距离目标k+1个结点时，h(n)也是可采纳的。

A*算法的最优性

  • A*算法有如下性质：

    如果h(n)是可采纳的，那么树搜索A*算法是最优的；

    如果h(n)是一致的， 那么图搜索A*算法是最优的。

后半部分对我们更加有用。

h1：8扩展，找到不在位置最小的状态，

🧠局部搜索算法和最优化问题

局部搜索算法概述

  • 一般的搜索算法都会系统地探索空间，这种系统化的方法在内存里面保留一条或者多条路径和路径中的每个结点，当我们找到目标之后，到达次目标的路径就是这个问题的一个解。

    But，很多问题里面，到达目标的路径是不相关的，比如把皇后问题中，重要的是最终皇后在棋局上的布局，而不是皇后加入的先后次序。

    这种问题很多，比如集成电路设计，工厂工地布局，作业车间调度，自动程序设计，电信网络优化，车辆寻径和文件夹管理。

  • 说白了，这类问题到目标的路径是无关紧要的，如此我们的想法就是考虑一些可以不关心路径的算法。

    局部搜索算法，从单个当前结点出发（而不是多条路径），通常只移动到它的邻近状态，一般情况下不保留搜索路径。

    虽说局部搜索算法不是系统化的，但是有两个关键的优点：

    1、只用很少的内存——通常是常数

    2、经常能在系统化算法不适用的很大的或是无限的(连续的)状态空间中找到合理的解。

  • 除了找到目标上的优点，局部搜索的目标是根据目标函数找到 最佳状态，这对于解决纯粹的**最优化问题 **十分有用。

  • 一般的经典的搜索算法那种标准的搜索模型不适用于很多最优化问题。

    比如说进化问题，达尔文的进化论可以被视为对最优化的尝试，自然界给我们提供了“繁殖适应性”这个目标函数，但是这个问题本身没有目标测试（啥样算是具体的目标点呢？没有）和路径代价，所以没法蒙头往下找目标。

  • 局部搜索中常用到状态空间地形图，坐标系的坐标-标高为：状态-启发式代价函数/目标函数

    若标高对应于代价函数，那自然代价越小越好，因此目标就是找到最低谷——全局最小值

    若标高对应于目标函数，那么一般定义目标值越高越好，因此目标是找到最高峰——全局最大值

    （方便起见，这俩值可以通过插入一个负号是两者转换）

    如此，若有解，

    那么完备的局部搜索算法总能找到解，

    最优的局部搜索算法总能找到全局最小值/最大值。

爬山法（最陡上升版本）/贪婪局部搜索

  • 他只是简单的循环过程，就是不断向值增加(以目标函数作标高)的方向持续移动，即登高。

    算法在到达一个“峰顶”，看到邻接状态中没有比它更高的就终止，⚠️注意哦，这里说的“峰顶“并不是全局最大值，而是某个**局部极大值**，这也是爬山法的一个问题所在，后面说。

    即算法过程：loop{比较，爬高}➡️某个时刻发现邻居都比自己差，说明自己已经是局部最大值了，即局部最优，那爬山法🧗‍♂️就不继续找了，返回局部最优值。

  • 算法不维护搜索树，因此当前结点的数据结构只需要记录当前状态和目标函数值。

    爬山法也不会去考虑与当前状态不相邻的状态（就只和相邻状态比嘛，比如八皇后问题中就是指移动某一个皇后之后的棋盘状态。）

    这样的过程用书上的话来说就是个“健忘症试图登顶珠穆朗玛峰”。⚠️这也是爬山法的一个问题，比如高原问题，后面说。

  • 局部搜索算法一般使用完整状态形式化，拿八皇后来说意思就是每个状态都包含了在棋盘上放置八个皇后（每列一个）。

    后继函数指的是移动某个皇后到这列的另一个可能的方格中，由此得到一个后继状态，因此每个状态有(8x7=56个后继)

    启发式评估函数h是形成互相攻击的皇后对的数量，不管是直接还是间接。该函数的全局最小值是0，仅在找到解时才会是这个值。

  • 对于爬山法来说，假如有多个后继都是当前最大值(以目标函数看)/最小值(以代价函数来看)，那么爬山法会在这些最佳后继和集中中随机选择一个。

  • 爬山法有时候被称为贪婪局部搜索，因为它永远只是选择邻居状态中最好的一个，而不继续考虑下一步该怎么走。不过状态好的话，那图的就是贪婪算法的快嘛。

  • 🧠来说一下爬山算法的弊端：

    **1、局部极大值**，

    前面提到过了这是啥意思，这种问题带来的就是爬山法常常只能找到我们找到的这个局部极大值可能远远小于全局最大值，也就是只到了珠穆朗玛峰旁边的一个小土包上，但是因为往旁边动都会让自己先往下走才行，爬山法不愿意这么做，所以一般做法是他发现自己已经爬到了一个“山顶⛰️”了，算法就结束了，就返回这个局部极大值。

    2、山脊

    这种情况就是会有一些列的局部极大值，爬山这样的贪婪算法难以处理。

    3、高原

    就是指状态空间地图上的一个单独的平台，或者是山肩。

    山肩还有可能取得进展，但是单独的平台就会让算法“迷路”了。

    解释一下：

    本来想着可以和后继比较的时候若当前状态=后继也就停下了，可是这样的话我们就只能放弃山肩的可能了。本着我们是来解决问题的精神，所以当目前=后继的时候还是继续探索（即侧向移动，这是相对于上山下山而言的叫法），所以这就带来在单独的平台上会来回反复移动，也就是所谓的“迷路”了，因为爬山者是个健忘症患者，也不记得之前走过的路，所以马上还会再走回去，这才给整迷路了。

    但是上面的允许侧向移动的方法也不能一直让他跑来跑去，不然会在平台上迷路——即算法死循环。

    一般可以设置允许连续侧向移动的次数限制。事实证明这样可以让成功率大幅提升，不过这样的代价就是我们完成任务的平均步数可能也就大大增多了。

  • 爬山算法的变形：

    随机爬山法

    它在上山移动中随机地选择下一步，被选中的概率可能随着上山移动的陡峭程度不同而不同。

    这样随机的方式可想而知比最陡爬山法收敛速度慢不少，但是在某些状态空间地形图上它能找到更好的解，随机嘛，万一碰到最大值了呢。😌

    首选爬山法

    首选爬山法也是一种随机爬山法，也随机，只是他一直生成到生成一个优于当前结点的后继才拿这个作为后继，这个算法在后继结点很多的时候是个好策略。

    随机重启爬山法

    要知道前面说的这些方法还是跟直接后继打交道，都不能保证可以找到解，即**不完备**！那更不用说最优了。

    因为即使随机他们也可能是在某一区域反复横条，出不去。

    而随机重启爬山法则不只是跟直接后继打交道了，他一开始也是正常爬高，然后陷入局部困境（比如没有完成符合条件的八皇后状态），这时候便会重启（重新开始搜索）：即随机生成一个状态作为初始状态再从这个状态开始爬山，直到找到目标。

    它完备的概率接近于1。按书上的说法，他最终会生成一个目标状态作为初始状态。但是这也不一定吧，要不咋说是“完备概率接近于1呢。”

    假设一次爬山来说，一次爬成功的概率是p，那么需要爬山的次数为1/p。

    如此，一次完整的任务所需步数的期望为：

    step(success)+[(1-p)/p]·step(failure)

    比如对于不允许侧向移动的八皇后问题：

    已知：

    每次爬山中成功的概率p约等于0.14，那么需要迭代的次数为1/p=7，即6次失败和1次成功；

    成功找到解的平均步数是4步，被卡住的平均步数是3步（就是开始之后走三步被卡住）；

    所需步数则为：

    4+[(1-0.14)/0.14]·3=4+6*3=22

    对于允许侧向移动的八皇后问题：

    已知：

    每次爬山中成功的概率p约等于0.94，那么需要迭代的次数为1/p=1.06，；

    成功找到解的平均步数是21步，被卡住的平均步数是64步（就是开始之后走三步被卡住）；

    所需步数则为：

    21+[(1-0.94)/0.94]·64=21+64/16=25步

    • 随机重启爬山法实际上还是挺有效的，即使有300万个皇后，这法子找到解的时间也不超过1分钟。
    • 从以上所有的分析来看（包括重启），爬山法的成功与否严重依赖于状态空间地形图的形状，假如几乎没有局部极大或者高原，那可能很好找到解。

模拟退火搜索

  • 爬山法由于不会下山，会卡在局部极大值上，所以不完备。

反之存粹的随机（一直等概率的随机选择后继），是完备的，但可想而知效率极低。

  • 模拟退火算法，就是考虑到把爬山算法和随机行走以某种方式结合，同时得到效率和完备性的算法。

  • 模拟退火的内层循环与爬山法类似，不过不是选择最佳移动(最佳后继)，而是选择随机移动，如果该移动使得情况改善，则该移动被接受。（这里的描述和首选爬山法差不多，后面便不一样了。）

    否则，算法以某个小雨1的概率接受该移动。并且如果移动导致状态变坏（即对状态的评估值$\Delta$E变坏），则概率成指数级下降。这个概率也会随着温度T的降低而下降：开始的时候T很高，可能允许“坏的”移动，T越低则越不待见这种坏东西（方法就是接受的概率降低嘛）。

    如果调度让T下降得足够慢，那算法找到全局最优解的概率逼近于1。

    解释一下概念：

    T=schedule(t)，即有一个调度表，T随着时间越来越小

    $\Delta$E = next.value - current.value，即用待选后继状态值 - 目前状态值

    如果$\Delta$E>0，那么显然我们直接接受这个后继即可

    否则，只以概率e^($\Delta$/T) 接受这个后继。

    来看$\Delta$E/T，当状态变好了，我们不会接触到这个概率，

    而当状态变差时，那么$\Delta$E<0，而因为调度一直在进行，这时候的温度T和之前相比也下降了，

    所以$\Delta$E/T降低了，故概率是e^($\Delta$/T)在呈指数级下降。

    由此结合整个过程来看，开始温度较高时，我们可以“疯狂接受”差的移动，而随着温度降低的降低我们越来越不会接受差的移动，想的极端一点到最后我们只以无穷小的概率接受差的移动，也就是我们基本只会接受好的移动，（但也不是完全不接受差的移动，如果完全不接受那旁边要是没有好的，就又陷入困境了），因此我们“终有一天”（不过这就是效率比较低的情况了）可以得到一个可行的解。

    不过假如温度降的太快了，也就是我们很快就（几乎）不允许下山了，那我们就很难去往那坐最优山上去了，也就很难找到最优解了，所以办法就是让温度降的慢一点，也就是允许试错的概率大一点，那么我们还可以接着不断下山去往另一座山，以期待找到最优解，书上说温度下降足够慢，找到最优解的概率逼近于1。

⚠️想到一个问题，局部搜索里面不考虑路径问题，对于八皇后这样的问提，它似乎不存在次优解啊，只有严格符合条件才算是找到了解，所谓的次优状态（目标函数局部极大值）也只是表示当前能调整到的最好的状态，但这种状态不算是一个解啊。那用模拟退火做的时候和其他问题相比这类问题的成功率是不是还是比较低呢？

局部束搜索

  • 内存是有限的，但是内存中只保留1个结点又有些极端。

    局部束搜索算法记录k个状态而不是1个状态。

    他从k个随机生成的状态开始。每一步全部k个状态的所有后继都被生成。若其中有一个是目标状态，则算法停止。否则从它整个后继列表中选择k个最佳的后继，重复这个过程。

  • 在局部束搜索中，有用的信息在并行的搜索线程之间传递，算法会很快放弃没有成果的搜索而把资源都用在取得重大进展的路径上。

  • 如果是最简单的局部束搜索，那么这k个状态由于缺乏多样性，他们很快会聚集到状态空间中的一小块区域，是的搜索代价比高昂的爬山法版本还要多。

    因此有了随机束搜索，它随机选择k个后继状态，其中选择给定后继状态的概率是状态值的递增函数，就是说当前状态越好的，他的后继被选中的概率越大，即适者生存。

    遗传算法

  • 遗传算法是随机束搜索的一个变形，并且也是从k个随机生成的状态开始，不过他通过把两个父状态结合来生成后继，而不是通过修改单一状态进行。

  • k个随机生成的状态——种群，

    每个状态——个体，用一个有限长度的字符串表示，通常是0、1串。

  • 如果说遗传算法有啥优点的话，那就来自于杂交了，

    杂交的优势来源于它能够将独立发展出来的能够执行有用功能的字符串区域结合起来，因此提高了搜索的粒度。

  • 遗传算法用了“模式”的思想来解释运转过程，可以证明，如果某个模式的实例的平均适应度超过均值，那么种群内这个模式的实例数量会随着时间增长。

    那么，如果临近位互不相关，效果就没有这么显著，因为只有很少的邻接区域能受益。

    遗传算法只有在模式具备真正与解相对应的成分时才工作得最好。

🧠对抗搜索-博弈

博弈

  • 竞争环境中，每个Agent的目标之间是有冲突的，即引出对抗搜索问题——通常称为博弈

  • 人工智能中的博弈:有完整信息的、确定性的、轮流行动的、两个游戏者的零和游戏

    游戏结束时，效用值总是相等且符号相反

    当然后面有多玩家的博弈，则规定放宽了

  • 博弈中Agent的行动数目通常受限，行动的输出都有严谨的规则来定义

  • 就像人类的下棋，博弈问题要求在无法计算出最优决策的情况下也要给出某种决策，

    并且对于低效率有严厉的惩罚

    如，其他条件相同的情况下，只有一般效率的A*算法意味着两倍的运行时间，于是只能以一半的效率利用可用时间的国际象棋程序就可能被击败，

    因此博弈会去研究如何尽可能地利用好时间的问题。

  • 博弈中会用到剪枝，使得在搜索树中忽略那些不影响最后决定的部分

    也会用到启发式的评估函数，使得在不进行完全搜索的情况下估计某个状态的真实效用值。

  • 效用函数(目标函数/收益函数)，定义游戏者p在终止状态下的数值。(如白子胜:1，黑子胜:-1，和:0)

    零和博弈中，所有的棋手总收益都是一样的，如国际象棋中棋局收益有:0+1，1+0，1/2+1/2，总收益都为1

    这也可以称作常量和，不过零和是更传统的说法。

MINIMAX算法

  • 博弈树的深度的定义:

在双方各走一步后，这可博弈树目前的深度是一步，包括了两个单方招数，每个单方招数称为一层

在课后题目中让画出某个游戏的两层博弈树则是指的两人各下一步的为止所呈现的局面

  • 当前博弈中的最优决策可以通过检查每个结点的极小极大值来觉得，

    对某个节点s，其极小极大值表示为MINIMAX(s)

    s为终止状态，取终止状态效用值;

    s为MAX结点，取直接后继的最大值(MAX结点即，当前为玩家MAX选择该怎么走)

    s为MIN结点，取直接后继的最小值

    可以看出，除了终止结点层以外每一层都接受来自后继的回传值，

    由此可以得知在跟结点的极小极大决策:对于MAX结点来说的最优选择即是，指向有最高的极小极大值的动作。

  • 在MINIMAX算法中在对MAX的最佳行棋进行求解时，做了MIN也按照最佳行棋的假设，即尽可能最大化MAX的最坏情况。

    那么加入MIN不按最佳行棋呢?按照常理也可以想到，这种情况下MAX可以做的更好。

    试想如果双方都按照最优招行棋MAX用minimax赢了，即MAX的效用值>MIN，

    那么MAX用minimax去对付次优招行棋的min，其效用值不会比对付最优招MIN时的效用值低，

    也就是说MAX照样能赢，且做的更好。

    某些策略在对付非最优化对手方面做得比极小极大策略好，但是拿它来对付最优化对手时则会得到更差的结果。

  • 极小极大算法对博弈树执行完整的深度优先搜索，

    加入树的最大深度为m(正常的树深度)，每个结点合法的行棋方式有b个，则复杂度O(b^m)

    一次性生成所有后继的算法，空间O(bm)

    每次生成一个后继的算法空间复杂度O(m)

多人博弈

  • 决策方式与双人博弈类似，只不过某个结点的效用值用向量表示，

    如三人博弈，某个结点表示为<va，vb，vc>，va，vab，vc即为从A、B、C角度出发看到的效用值

    如此，每次在做决策时，回传的都是后继中让自己的效用值最大的结点的效用值向量

  • 假如游戏是非零和的，比如去摘苹果，A和B都觉得自己摘满一百个就够了，那么他们可能会可做让自己达到这种状态

  • 而另一种想法，则是一个ABC的游戏，C太过强大，于是A和B可以通过合作来打压他，

    比如A和B在选择行动时，优先选择的不是让自己的效用值最大的行动方案而是让C的效用值更小的那一个方案。

$\alpha$ -$\beta$剪枝

  • 极小极大值搜索存在的问题:

    我们需要检查的状态数目会随着博弈的进行呈现指数级增长，

    不幸的是，这种指数增长无法消除，因此我们想办法将其减半

    也就是我们不需要遍历博弈树中每一个结点就可以计算出正确的极小极大值

    这种技术称为$\alpha$- $\beta$剪枝。

  • $\alpha$- $\beta$剪枝可以应用于任何深度的树，很多情况下可以减掉整个子树，而不仅仅是剪掉叶结点。

  • 做一下习题5。9，和图5。5对比一下可以很明显知道，$\alpha$- $\beta$剪枝剪枝的效率很大程度上依赖于检查后继状态的顺序，这对决策很不利，可能在我们没算完最佳决策的时候就没时间了，那将给不出一个好的决策。

对博弈算法的优化

  • 一个关键方法——尽早地截断搜索

    就是说我不再去搜完整棵博弈树，而是选择在某一层阶段就算阶段层为止的最优决策

    那么需要做的事有:

    ​ 1、采用棋局效用值的启发式评估函数EVAL(s)取代效用函数

    ​ 2、用“决策什么时候启用EVAL”的截断测试取代终止测试

    因此我们需要解决的问题就是: 考虑该截到哪儿?**以及，怎么设计合理的EVAL(s)函数?**

  • 设计评估函数的原则: 得能合理地估计出终止状态的情况，具体来说:

    1、评估函数对终止状态的排序应当和真正的效用函数的排序一样，即:

    ​ 赢状态的评估值一定要好于平局;而平局的评估值要好于输的状态。否则评估出来就是瞎扯。

    2、评估函数本身的计算不能花费太长时间，这是当然的，不能喧宾夺主嘛，主要的工作还是在搜索上。

    3、对于非终止状态，评估函数应当和取胜的几率密切相关

  • 下面来说截断搜索的问题

    知道了到底该在哪里截断才能去吧EVAL(s)启用啊。

    设置截断的方法:

    1、设置固定深度。

    根据游戏规则限定的时间和机器的性能可以判断这么长时间里大概可以搜多少层，找一个合适的值，那么每次就固定搜这么多层。

    2、迭代深入，这是更好的方法。

    优点是假如时间用光了，那就返回目前完成的最深的完整搜索所采用的招数。

🧠:然而，由于评估函数是我们的近似估计，所以这样的方法可能会出问题。

比如到我截断的深度为止，我找出了现在可以下的最好的一手，然后后一步可能就是显而易见的对手会把我的子吃掉的一步，但是因为采用了截断，我们没法推演到这一步，而这一步可能会把局势完全地逆转过来，可我们却无法预料。

这是因为截断之后，启发函数自然是看当前范围内招数对棋局的影响，我们无法再向前看一步。

显然我们不能这样草草截断，而需要更复杂的截断测试。

评估函数只适用于那些静态棋局，即评估值不会很快出现大的波动的棋局

非静态棋局可以进一步扩展变为静态棋局，所需要做的额外的搜索称为静态搜索，有时候他只考虑某些类型的棋招，以快速消解棋局的不确定性

另外还有一个问题就是，地平线效应，更难消除。这是指对手的一招将导致我放某个损失从理论上将无法避免(比如不管怎么走黑棋的象还是会被吃掉，只是迟早的问题)。而在有限深度内，黑棋却无发推演到这种结果，因此为了避免象被吃掉它还是会做行动来“避免被吃”，可实际上这是避免不了的，只是“超出了黑方所能看到的地平线”罢了。这就是固定深度(截断)的搜索的弊端，他相信这些延缓的招数能够解决问题，而实际上只是将那个“必然的一步”给“推出了地平线”，将其推进了“无法检测到的空间”。

避免地平线效应的一种策略是单步延伸，单步延伸至的事在给定棋局中一种棋招要明显好于其他棋招。一旦在搜索的某处发现单步延伸，牢记它。当达到指定深度界限时，算法会检查单步延伸是否合法，如果是，算法允许考虑此招。这样做可能会超出深度限制，但由于单步延伸很少，因此不会增加太多开销。

随机博弈

比如有骰子的双陆棋

这样博弈树中除了有MIN,MAX结点,还会有机会结点,这样的棋局没有明确的极小极大值,智能计算棋局的期望值:机会结点所有可能结果的平均值.

随即博弈中,和极小极大值一样,期望极小极大值的近似估计可以通过在某结点截断搜索并对每个叶结点计算其评估函数来进行.

而机会结点的存在,意味着我们更应该去考虑评估函数的函数,评估值去的范围不一样决策可能会完全不一样.

为了避免这种敏感性,评估函数应该与棋局获胜概率(更一般的说是棋局的期望效用值)成正线性变换.

时间O(b^m^· n^m^)，m,b,n:深度，分枝因子，骰子结果数目（如6种）。

在大多数机会博弈中由于额外代价(概率带来的)的存在,是的向前考虑地很远是不现实的

附录

1.罗马尼亚地图

IMG_6953

IMG_6953

2. 罗马尼亚问题的A*解法（h(n)=hLSD）

IMG_6978

69782

IMG_6979

69792