搜索算法的一般描述：

基于树的搜索算法都是通过扩展 $fringe$ （边缘节点）来搜索整个状态空间的。
所谓的 $fringe$ 就是叶子节点，也被称为： $cadidate \: \: expansion$ （候选扩展节点）；
首先要确定当下所有的叶子节点，然后根据不同的搜索策略进行扩展。
对于某个叶子节点，如果它能够继续被探索，证明这条路还有可能存在解；如果不能进行探索操作，那么就代表解不可能存在于当下节点的扩展当中。

1.1 宽度优先搜索

宽度优先搜索（breadth-first search）的描述：

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

宽度优先搜索是一般图搜索算法的一个实例，每次总是扩展深度最浅的结点。

具体实现：

通过将边缘组织成 $FIFO$ 队列来实现。就是说，新结点（结点比其父结点深）加入到队列尾，这意味着浅层的老结点会在深层结点之前被扩展。

目标测试的时机：

目标的测试是在结点被生成的时候，而不是结点被选择扩展的时候。

注意：

算法具有一般的图搜索框架，忽视所有到边缘结点或已扩展结点的新路径；可以容易地看出，这样的路径至少和已经找到的一样深。所以，宽度优先搜索总是有到每一个边缘结点的最浅路径。

下图给出了伪代码并显示了一个简单二叉树的搜索过程：

完备性（当算法有解时，是否能够保证算法找到解）：宽度优先搜索是完备的。

如果最浅的目标结点处于一个有限深度 $d$ ，宽度优先搜索在扩展完比它浅的所有结点（假设分支因子 $b$ 是有限的）之后最终一定能找到该目标结点。请注意目标结点一经生成，我们就知道它一定是最浅的目标结点，原因是所有比它的浅的结点在此之前已经生成并且肯定未能通过目标测试。

最优性（算法能否找到最优解）：宽度优先搜索不一定是最优的。

最浅的目标结点不一定就是最优的目标结点；从技术上看，如果路径代价是基于结点深度的非递减函数，宽度优先搜索是最优的。最常见的情况就是当所有的行动要花费相同的代价。（路径代价符合宽度优先的价值观）

时间复杂度（找到解需要花费多长时间）： $O(b^{d})$ 。

假设搜索一致树（uniform tree）的状态空间中每个状态都有 $b$ 个后继。搜索树的根结点生成第一层的 $b$ 个子结点，每个子结点又生成 $b$ 个子结点，第二层则有 $b^{2}$ 个结点。这些结点的每一个再生成 $b$ 个子结点，在第三层则得到 $b^{3}$ 个结点，依此类推。现在假设解的深度为 $d$ 。在最坏的情况下，解是那一层最后生成的结点。这时的结点总数为：

$b+b^{2}+b^{3}+...+b^{d}=O(b^{d})$

如果算法是在选择要扩展的结点时而不是在结点生成时进行目标检测，那么在目标被检测到之前深度 $d$ 上的其他结点已经被扩展，这时时间复杂度应为 $O(b^{d+1})$ 。

空间复杂度（执行算法时需要多少内存）： $O(b^{d} )$ 。

对任何类型的图搜索，每个已扩展的结点都保存在探索集中，空间复杂度总是在时间复杂度的 $b$ 分之一内。特别对于宽度优先图搜索，每个生成的结点都在内存中。那么将有 $O(b^{d-1} )$ 个结点在探索集中， $O(b^{d} )$ 个结点在边缘结点集中。所以空间复杂度为 $O(b^{d} )$ ，即它由边缘结点集的大小所决定。即使转换为树的搜索问题也节省不了多大的存储空间，如果状态空间有重复路径的话，这种转换会耗费大量时间。

指数级的复杂度 $O(b^{d} )$ 令人担忧。下图说明了原因：

$Bidirectional \: \: Search$

从起点和终点同时进行 $BFS$ ，复杂度比 $BFS$ 低。

完备性：和 $BFS$ 相同。

最优性：和 $BFS$ 相同。

时间复杂度： $O(b^{d/2})$ 。

$O(2*(b+b^{2}+b^{3}+...+b^{d/2}))=O(b^{d/2})$

空间复杂度： $O(b^{d/2})$ 。

1.2 一致代价搜索

当每一步的行动代价都相等时宽度优先搜索是最优的（路径代价符合宽度优先的价值观），因为它总是先扩展深度最浅的未扩展结点。

更进一步，我们可以找到一个对任何单步代价函数都是最优的算法。不再扩展深度最浅的结点。

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

扩展的是路径消耗 $g(n)$ 最小的结点 $n$ 。这可以通过将边缘结点集组织成按 $g$ 值排序的队列来实现。

一致代价搜索和宽度优先搜索的不同：

一致代价搜索按路径代价对队列进行排序。

目标检测应用于结点被选择扩展时，而不是在结点生成的时候进行。理由是第一个生成的目标结点可能在次优路径上。

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

目标检测的时机：

目标检测应用于结点被选择扩展时，而不是在结点生成的时候进行。理由是第一个生成的目标结点可能在次优路径上。

算法执行过程举例：

图中的搜索是从Sibiu到Bucharest。

Sibiu的后继包括Rimnicu Vilcea和Fagaras，代价分别为80和99。
最小代价结点为Rimnicu Vilcea（80）被选择扩展。
此时加入了Pitesti代价为 $80+97=177$ 。所以这时的最小代价结点为Fagaras，扩展它得到Bucharest代价为 $99+ 211=310$ 。
目标结点已经生成，但是一致代价搜索算法还在继续，选择Pitesti扩展得到到达Bucharest的第二条路代价为 $80 + 97 +101 =278$ 。
现在算法则需要检查新路径是不是要比老路径好；确实是新的好，于是老路径被丢弃。Bucharest，g代价为278，被选择扩展算法返回。

完备性：不存在零代价行动时一致代价搜索是完备的。

一致代价搜索对解路径的步数并不关心，只关心路径总代价。所以，如果存在零代价行动就可能陷入死循环业例如 $NoOp$ 行动（无行动）。如果每一步的代价都大于等于某个小的正值常数 $\varepsilon$ ，那么一致代价搜索是完备的。

最优性：一致代价搜索是最优的。

首先，我们观察到当一致代价搜索选择结点 $n$ 去扩展时，就已经找到到达结点 $n$ 的最优路径【否则，在从开始结点到结点 $n$ 的最优路径上就会存在另一边缘结点 $n^{'}$ 。（根据定义， $n^{'}$ 的 $g$ 代价就会比 $n$ 小即应被选择扩展）】。

接着，由于每一步的代价是非负的，随着结点的增加路径绝不会变短。

这两点说明了一致代价搜索按结点的最优路径顺序扩展结点。所以，第一个被选择扩展的目标结点一定是最优解。

一致代价搜索由路径代价而不是深度来引导，所以算法复杂度不能简单地用 $b$ 和 $d$ 来表示。引入 $C^{*}$ 表示最优解的代价，假设每个行动的代价至少为 $\varepsilon$ 。

时间复杂度：最坏情况下，算法的时间复杂度为 $O(b^{1+\left \lfloor C^{*}/\varepsilon \right \rfloor})$ 。

空间复杂度：最坏情况下，算法的空间复杂度为 $O(b^{1+\left \lfloor C^{*}/\varepsilon \right \rfloor})$ 。

最坏情况下，算法的时间和空间复杂度为 $O(b^{1+\left \lfloor C^{*}/\varepsilon \right \rfloor})$ 。要比 $b^{d}$ 大得多。这是因为一致代价搜索在探索包含代价大的行动之前，经常会先探索代价小的行动步骤所在的很大的搜索树。

当所有的单步耗散都相等的时候， $b^{1+\left \lfloor C^{*}/\varepsilon \right \rfloor}$ 就是 $b^{d+1}$ 。

此时，一致代价搜索与宽度优先搜索类似，除了算法终止条件，宽度优先搜索在找到解时终止，而一致代价搜索则会检查目标深度的所有结点看谁的代价最小；这样，在这种情况下一致代价搜索在深度 $d$ 无意义地做了更多的工作。

局限性：

将所有的方向都看成等价的。
对于目标节点的方向没有任何信息，因此只能是一圈圈往外扩展去寻找解。

1.3 深度优先搜索

深度优先搜索（depth-first search）：

总是扩展搜索树的当前边缘结点集中最深的结点。

宽度优先搜索使用 $FIFO$ 队列，而深度优先搜索使用 $LIFO$ 队列。 $LIFO$ 队列指的是最新生成的结点最早被选择扩展。这一定是最深的未被扩展结点，因为它比它的父结点深1——上一次扩展的则是这个父结点因为当时它最深。

搜索过程如图所示。

搜索很快推进到搜索树的最深层，那里的结点没有后继。当那些结点扩展完之后，就从边缘结点集中去掉，然后搜索算法回溯到下一个还有未扩展后继的深度稍浅的结点。

深度优先搜索算法是下图的图搜索算法的实例：

深度优先图搜索的实例：

从起始节点 $S$ 开始，边缘节点只有 $S$ 一个节点；通过扩展 $S$ 节点，边缘节点加入 $d, e, p$ 三个节点并删除 $S$ 节点， $d, e, p$ 作为下一步的可扩展节点。
深度优先遍历会选择最深的候选节点，但是 $d, e, p$ 深度相同，因此按照字母顺序首先扩展 $d$ ，边缘节点加入 $b,c,e$ 剔除了 $d$ 。目前边缘节点有： $b, c, e, e, p$ 。
由于 $b,c$ 的深度最深，按照字母顺序探索 $b$ 节点，同理边缘节点更新成： $a, c, e, e, p$ 。
对于当前 $s \rightarrow d \rightarrow b \rightarrow a$ 的路径，发现 $a$ 不能继续扩展，所以这条路走到头了。
扩展 $c$ ， $s\rightarrow d \rightarrow c\rightarrow a$ 这条路也不能扩展，因此边缘节点剔除了 $a,b,c$ 只剩 $e,e,p$ 。
扩展 $e$ ，边缘节点更新为： $h, r, e, p$ 。延续这个过程，一直到找到 $G$ 节点，返回最终路径

完备性：图搜索时深度优先搜索是完备的，树搜索时不是完备的。

深度优先搜索算法的效率严重依赖于使用的是图搜索还是树搜索。避免重复状态和冗余路径的图搜索，在有限状态空间是完备的，因为它至多扩展所有结点。而树搜索，则不完备如图：

算法会陷入 $Arad-Sibiu-Arad-Sibiu$ 的死循环。

深度优先搜索可以改成无需额外内存耗费，它只检查从根结点到当前结点的新结点；这避免了有限状态空间的死循环，但无法避免冗余路径。在无限状态空间中，如果遭遇了无限的又无法到达目标结点的路径，无论是图搜索还是树搜索都会失败。

最优性：深度优先搜索不是最优的。

无论是基于图搜索还是树搜索的深度优先搜索都不是最优的。例如下图中：

深度优先搜索会探索整个左子树，尽管 $C$ 就是目标结点。如果 $J$ 是目标结点，那么深度优先搜索会返回 $J$ 为解而不是 $C$ ，而此时 $C$ 是更好的解；所以深度优先搜索不是最优的。

深度优先搜索的时间复杂度受限于状态空间的规模（当然，也可能是无限的）。另一方面，深度优先的树搜索，可能在搜索树上生成所有 $O(b^{m})$ 个结点，其中 $m$ 指的是任一结点的最大深度；这可能比状态空间大很多。要注意的是 $m$ 可能比 $d$ （最浅解的深度）大很多，并且如果树是无界限的， $m$ 可能是无限的。

时间复杂度： $O(b^{m})$ 。

注意这里是 $m$ 不是 $d$ ， $d$ 是指代的最浅目标节点的深度， $m$ 可能远远大于 $d$ 。

空间复杂度： $O(bm)$ 。

最坏的情况就是，对于一条路径 $S$ ，S上包含的所有节点的分支因子都在边缘节点中。当S的深度最坏为 $m$ ，分支因子是 $b$ 所以最坏的空间复杂度是 $m\times (b-1)$ 即 $O(bm)$ 。

1.4 宽度优先搜索 V.S. 深度优先搜索

无障碍搜索：

BFS

DFS

有障碍搜索：

BFS

DFS

通过上面的学习，加上上面的对比图。我们发现深度优先搜索与宽度优先搜索相比似乎没有任何优势，那我们为什么要考虑它？原因就在于空间复杂度。

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

何时 BFS 优于 DFS

当在较浅的层存在解。
当我们一定要寻找最优解。

何时 DFS 优于 BFS

当解都处于较深的层。
当内存有限制。

回溯搜索（backtracking search）

深度优先搜索的一种变形称为回溯搜索，所用的内存空间更少。在回溯搜索中，每次只产生一个后继而不是生成所有后继；每个被部分扩展的结点要记住下一个要生成的结点。这样，内存只需要 $O(m)$ 而不是 $O(bm)$ 。回溯搜索催化了另一个节省内存（和节省时间）的技巧：通过直接修改当前的状态描述而不是先对它进行复制来生成后继。这可以把内存需求减少到只有一个状态描述以及 $O(m)$ 个行动。为了达到这个目的，当我们回溯生成下一个后继时，必须能够撤销每次修改。对于状态描述相当复杂的问题，例如机器人组装问题，这些技术是成功的关键。

1.5 一致代价搜索 V.S. 宽度优先搜索 V.S. 深度优先搜索

蓝色的部分表示有水，经过这些水的代价不同，经过浅蓝色的地方 $cost$ 比较低，深蓝色的地方 $cost$ 比较高。

UCS

在浅水区的步骤更多。

BFS

广度有限搜索忽略了 $cost$ ，把深水区和浅水区看成相同的，因为它关心的是 “最浅”深度，而不是 $cost$ 。

DFS

忽略了所有东西除了深度，但依然找到了解。

1.6 迭代加深的深度优先搜索

迭代加深的深度优先搜索（iterative deepening search）：

迭代加深的深度优先搜索经常和深度优先搜索结合使用来确定最好的深度界限。做法是不断地增大深度限制——首先为 $0$ ，接着为 $1$ ，然后为 $2$ ，依此类推直到找到目标。当深度界限达到 $d$ ，即最浅的目标结点所在深度时，就能找到目标结点。

算法参见下图：

完备性：分支因子有限时迭代加深的深度优先搜索是完备的。

和宽度优先搜索一样，当分支因子有限时是该搜索算法是完备的。

最优性：当路径代价是结点深度的非递减函数时该算法是最优的。

时间复杂度： $O(b^{d})$ 。

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

$N(IDS)=(d)b+(d-1)b^{2}+ .... +(1)b^{d}$

时间复杂度为 $O(b^{d})$ ——与宽度优先搜索相近。重复生成上层结点需要付出额外代价，但不是很大。如果你确实担忧状态的重复生成，可以混合使用两种搜索算法，先用宽度优先搜索直到有效内存耗尽，然后对边缘集中的所有结点应用迭代加深的深度优先搜索。

空间复杂度： $O(b^{d})$ 。

迭代加深的深度优先搜索算法结合了深度优先搜索和宽度优先搜索的优点，它的空间需求是合适的： $O(b^{d})$ 。

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

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

迭代加长搜索（iterative lengthening search）：

结合一致代价搜索的迭代搜索是有价值的，在一致代价搜索确保最优化的同时避免了大量的内存需求。它的主要思想是用不断增加的路径代价界限代替不断增加的深度界限。不幸的是，与一致代价搜索相比，事实上迭代加长搜索将导致实在的额外开销。

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】