多路径剪枝

多路径剪枝：通往一个节点一般都不止一条路径。而如果只需要一条路径，那么一种搜索算法可以从任何通向它已经找到路径的节点的路径中删除。

多路径剪枝可以通过保留已扩展的节点列表来实现。已扩展的节点列表的初始集合是空的。当在下图贪婪搜索的案例(图3.4)的第13行中选择一条路径⟨n0,…,nk⟩时，如果它的最后一个节点nk位于已扩展的节点列表中，则路径可以被丢弃。否则，它的最后一个节点被添加到拓展列表中，并且算法继续进行。这种方法不一定保证最短路径不会被丢弃。为了保证找到最优解，可能需要做一些更复杂的事情。为了确保搜索算法仍然能够找到最低成本的目标路径，下面的方法可以做到:

1. 确保找到的任何节点的第一个路径都是该节点的最低成本路径，然后按照前面所讨论的，对该节点的所有后续路径进行剪枝。
2. 如果搜索算法找到一个比已经找到的节点低成本的路径，它可以删除所有使用高成本路径到节点的路径(因为它们不能在最优的解决方案上)。也就是说，如果有一条路径p是通过⟨s,…,n,…,m⟩个点的路径，p′是从s到n的新路径，并且p′消耗比P路径小，那么p′将会取代原来的s到n的p路径。
3. 无论何时，当搜索找到指向节点的低成本路径，它可以在扩展初始路径的路径上添加一个新的初始部分。

在lowest-cost-first search（如Dijkstra’s algorithm）搜索算法中，它首先找到的是到该节点的最低成本的路径。对该节点的后续路径进行修剪时，不能删除该节点的低成本路径，因此对每个节点的后续路径进行修剪仍然能够找到最优的解决方案。

例如，A* Search不能保证在第一次选择某个节点的路径时，它是该节点的最低成本路径。注意，可接受性定理admissibility theorem保证了每个路径能到一个目标节点，而不是每个路径到任意节点。是否适用于所有节点取决于启发式函数的性质。

A consistent heuristic是一个非负函数h(n),指的是在n的节点上，对于任意两节点n′，n满足条件h(n)≤cost(n,n′)+h(n′).这里cost(n,n′)是n到n‘的least-cost path的最小花费。如果对于任意goal有h(g)=0，那么一个consistent heuristic不会过高评估对于n到目标节点g的花费。

Proposition：With a consistent heuristic, multiple-path pruning can never preventA*search from finding an optimal solution.如果对于一个consistent heuristic，多路径剪枝不会影响A*搜算算法找到一个优化方案。

下边，用反证法进行证明。为了看到到节点后续路径剪枝可能移除最优解，假设该算法选择了一条路径p到节点n进行扩展，但是在节点n中存在一条较低成本的路径，该路径尚未找到。然后必然有一条路径p'在边界上，这是低成本路径的初始部分。假设路径p'的结束节点为节点n'。当然也有f(p) ≤ f(p')，因为p在p'之前被选择，这就意味着

cost(p) + h(n) ≤ cost(p')+h(n').

如果通过n'的路径p的成本比路径p’低，

cost(p') + d(n', n)<cost(p),

d(n', n)是节点n'到n的最短路径的实际代价，从这两个方程中，我们可以推导出

d(n', n)<cost(p)-cost(p') ≤ h(p') - h(p)= h(n') - h(n).

因此,我们可以确保第一个路径发现任何节点是成本最低的路径，如果|h(n')-h(n)| ≤ d(n',n)，对任何两个节点n和n '。单调限制h是|h(n')-h(n)| ≤ d(n',n)，对任何两个节点n,n '。也就是说，两个节点的启发式值的差值必须小于或等于节点之间最低成本路径的实际成本。例如，当成本函数为距离时，欧几里得距离的启发式函数(n维欧几里得空间中的直线距离)在两点之间时，或当启发式函数是一个简化问题的解决方案时，它都是适用的。

在单调约束条件下，边界上的f值是单调无衰减的。也就是说，当边界扩大时，f值不会变小。因此，在单调限制下，任何节点的后续路径都可以在A*搜索中删除。这就是反证法对于性质Proposition的证明。

多路径剪枝包含一个回环检测，因为回环是另一条通往节点的路径，因此被修剪。如果图形是直接存储的，则可以在常量时间内完成多路径修剪，通过在每个节点上设置一个bit，从而找到一条路径。如果图形是动态生成的，则可以在对数时间内(在扩展的节点数中)，通过存储已扩展的所有节点的闭列表来动态生成。对于宽度优先方法，多路径修剪是首选的，优于回环检测，几乎所有的节点都必须被存储。然而，对于深度优先搜索策略，该算法不需要存储已经考虑过的所有节点。存储它们使方法在空间中呈指数级。所以对于深度优先的方法来说，回环检测优于多路径检查。

例子：

如图s到n有两条路径，多路径剪枝会只选择其中一条消耗更小的路径，使得计算更为简单。

【描述来源：Artificial Intelligence，URL：http://artint.info/html/ArtInt_61.html】

发展历史

描述

搜索算法从刚开始的暴力搜索开始 brute-force search，意思就是穷尽所有可能，暴力地找出最大值或者最小值。还有各种各样的启发式的算法，它们利用对这个空间结构的部分内容来进行搜索，例如linear relaxation, constraint generation, 和constraint propagation。

一个重要搜索方法是局部搜索，该方法将搜索空间的元素视为图的顶点，其边缘由适用于该情况的一组启发式定义;通过沿着边缘从一个项目移动到另一个项目来扫描这个空间，例如根据最陡的下降或最好的第一标准，或者在随机搜索中。这一类别包含了多种通用的元启发式方法，例如模拟退火、禁忌搜索、A-teams和遗传编程。

19世纪，法国数学家查尔斯·皮埃尔·特雷莫(Charles Pierre Tremaux)对深度优先搜索Depth-first search (DFS)的一个版本进行了研究，认为这是一种解决迷宫的策略。BFS( Breadth-first search )和它在寻找图形的连接部分的应用是由Michael Burke和Konrad Zuse在1945年发明的.Edsger Dijkstra在1959年在ARMAC计算机上写出了Dijkstra算法，它来搜索最短路径的算法。

在1968年，人工智能研究员尼尔斯·尼尔森(Nils Nilsson)试图改进机器人Shakey所做的路径规划，这个机器人原型可以通过在一个包含障碍物的房间进行导航。这种寻路算法，Nilsson称之为A1，是当时最著名的Hans Berliner于1979算法的更快版本，用于在图中找到最短路径。Bertram Raphael建议对这个算法进行一些重要的改进，并调用了修改后的A2。然后Peter E. Hart引入了一个论证，建立了A2，只有微小的变化，才能成为寻找最短路径的最佳算法。

B*(发音为“B星”)是一种最佳的图形搜索算法，它从给定的初始节点到任何目标节点(在一个或多个可能的目标中)找到最小成本路径。由Hans Berliner于1979年首次出版。

1985 Richard Korf Iterative deepening A* (IDA*)是一种图遍历和路径搜索算法，它可以在一个加权图中找到指定的起始节点和一组目标节点的任何成员之间的最短路径。它是迭代深化深度优先搜索的一个变体，它借用了一个启发函数来评估剩余的成本，以从a *搜索算法获得目标。由于它是深度优先的搜索算法，它的内存使用率低于A*，但与普通的迭代深化搜索不同，它专注于探索最有希望的节点，因此不会访问。与A*不同，IDA*不使用动态编程，因此经常会多次访问相同的节点。

Russell, S. (1992)SMA*Simplified Memory Bounded A*或简化内存有界A*是基于A*算法的最短路径算法。SMA的主要优点是它使用有界内存，而a *算法可能需要指数内存。SMA的所有其他特征都是从一个A*继承的。2002年，Intanagonwiwat, C对贪婪数进行多路径剪枝。

另一类包括各种树搜索算法，它将元素视为树的顶点，并以某种特殊的顺序遍历该树。后者的例子包括详尽的方法，如深度优先搜索和广度优先搜索，以及各种基于启发式的搜索树剪枝方法，例如回溯和branch and bound.。不像一般的metaheuristics，在最好的情况下，它只是在概率意义上，许多这些树搜索方法保证找到精确的或最优的解决方案，如果有足够的时间。这就是所谓的“完整性”。

另一个重要的子类包括用于探索多玩家游戏的博弈树的算法，如国际象棋或西洋双陆棋，其节点包括所有可能由当前情况导致的游戏情况。在这些问题中，我们的目标是找到一个能提供最好的获胜机会的策略，同时考虑到对手的所有可能的策略。类似的问题发生在人类或机器必须做出连续的决策时，这些决策的结果并不完全在一个人的控制之下，例如在机器人指导或市场营销、财务或军事战略规划中。这类问题——组合搜索——在人工智能的背景下得到了广泛的研究。这类算法的例子有minimax算法，alpha-beta剪枝，*信息搜索算法和A*算法。

主要事件

发展分析

瓶颈

有时我们不想剪枝。实际上需要多个解决方案(包括非最佳解决方案)，但是多路径剪枝只能给予我们一个最佳解决方案。

多路径剪枝不适合IDA*，因为存储探索集所需的空间通常大于A*所需的空间，因此违背了迭代深化的目的。loop prunning可以使用IDA*。

未来发展方向

多路径剪枝对于宽度优先的方法来说，比循环检测是首选的，因为该算法几乎所有的节点都必须被存储。然而，对于深度优先搜索策略，该算法不需要存储已经考虑过的所有节点。存储它们使方法在空间中呈指数级。因此，对于深度优先的方法，循环检查优于多路径检查。尽管搜索算法已经有很长的历史，但是依然是一个棘手的问题，如何又快，又消耗少内存，并能获得最优解或者近似最优解一直是大家所关注的热点问题。

Contributor: Ruining Cai