存储限制的启发式搜索

4.1.3 存储限制的启发式搜索

A*算法减少存储需求的最简单办法就是将迭代深入的思想用在启发式搜索上，形成迭代深入 A*（IDA*）算法。IDA*和典型的迭代深入算法最主要的区别就是所用的截断值是f耗散值（g+h）而不是搜索深度；每次迭代，截断值是超过上一次迭代截断值的节点中最小的f耗散值。IDA*算法对很多单位耗散的问题都是实用的，而且可以避免与有序节点的队列相联系的实际系统开销。不幸的是，它也会在实数耗散值的情况下遇到与习题3.11中描述的迭代的代价一致搜索相同的困难。本节中将简要考察两种新近的存储限制搜索算法，称为RBFS和MA*。

递归最佳优先搜索（RBFS）是一个模仿标准的最佳优先搜索的递归算法，但是它只使用线性的存储空间。算法如图 4.5 所示。它的结构和递归深度优先搜索类似，但是它不沿着当前的不确定路径继续下去，而是记录从当前节点的祖先可得到的最佳可替换路径的f值。如果当前节点超过了这个限制，递归将转回到替换的路径上。当递归回溯时，对回溯前的当前路径上的每个节点，RBFS 用其子节点的最佳f值替换其f值。这样，RBFS能记住被它遗忘的子树中的最佳叶节点的f值，并因此能够在以后某个时刻决定是否值得重新扩展该子树。图4.6显示了RBFS是怎样到达Bucharest的。

图4.5 递归最佳优先搜索算法

图4.6 使用RBFS搜索，寻找到Bucharest的最短路径的几个阶段。每次递归调用的f限制值在每个当前节点的上方标注。（a）沿着经过Rimnicu Vilcea的路径，直到当前最佳叶节点（Pitesti）的值差于最佳替代路径（Fagaras）。（b）递归回溯，把被遗忘子树的最佳叶节点值（417）备份到Rimnicu Vilcea；然后扩展Fagaras，显示最佳叶节点值是450。（c）递归回溯，把被遗忘子树的最佳叶节点值（450）备份到Fagaras；再扩展Rimnicu Vilcea。这次，因为最佳替代路径（经过Timisoara）的耗散至少是447，继续扩展到Bucharest

RBFS算法比IDA*算法效率更高，但是它还是需要重复生成大量节点。在图4.6所示的例子中， RBFS首先沿着经过Rimnicu Vilcea的路径，然后“改变主意”去尝试Fagaras，然后又“回心转意”了。发生这些主意的改变是因为每次扩展当前的最优路径时，很可能会使它的f值增加——对于靠近目标的节点，h 通常不那么优化。这时，尤其是在大的搜索空间中，第二好的路径可能会成为最佳路径，所以搜索将会回溯然后沿着它前进。每次主意的改变都对应于 IDA*中的一次迭代，并且可能需要重新扩展已经遗忘的节点来重建最佳路径，然后再扩展下一个节点。

像 A*算法一样，如果启发函数 h(n)是可采纳的，那么 RBFS 算法是最优的。它的空间复杂度是O(bd)，但是它的时间复杂度比较难刻画：既取决于它的启发函数的准确性，又取决于当扩展节点时改变最佳路径的频度。IDA*与RBFS都服从和图搜索联系在一起的潜在的指数增长复杂度，因为它们无法检测除了当前路径上的状态之外的重复状态。因此，它们可能反复对一个状态探索多次。

IDA*和RBFS的问题在于利用的内存过于小了。在两次迭代之间，IDA*只保留一个数字：当前的f耗散值限制。RBFS在内存中保留的信息多一些，但是它只用到复杂度为O(bd)的内存：即便有更多可用的内存，RBFS也没有办法利用。

因此，充分利用可用内存的看来是更明智的。有两个这样做的算法，MA*（存储限制A*）和SMA*（简化 MA*）。我们将描述 SMA*算法，自然，它更简单一些。SMA*算法像 A*算法一样，扩展最佳叶节点直到内存放满为止。到了这个程度，不丢弃一个旧节点它就无法在搜索树上加入一个新节点。SMA*总是丢弃最差的一个叶节点——即f值最高的一个。像RBFS一样，然后SMA*把被遗忘节点的值备份到父节点。这样，被遗忘子树的祖先节点可以了解那棵子树中最佳路径的质量。只有当所有其它路径看来比被遗忘路径要差的时候，SMA*才会利用这个信息重新生成该子树。换个方式来说，如果节点 n 的所有子孙节点都被遗忘了，我们将不知道从n该走哪条路，但是我们知道从n去别处是否值得。

完整的算法在这里复现太复杂了[11]，但是有一个细节值得注意。我们说过SMA*扩展最佳叶节点并且删除最差叶节点。如果所有的叶节点都有相同的 f 值会怎样？那么算法可能会选择同一个节点进行删除和扩展。SMA*是这样解决这个问题的：它扩展最新的最佳叶节点，删除最老的最差叶节点。仅在只有一个叶节点的情况下这两个才可能是同一个节点；在那种情况下，当前的搜索树必然是充满内存的一条从根节点到叶节点的单一路径。如果叶节点不是目标节点，那么即使它在最优解的路径上，这个解在可用的内存上也是不可达到的。因此，该节点应该被丢弃，就如同它没有后继一样。

如果有可达到的解——也就是说，如果最浅的目标节点的深度d小于内存大小（由节点数来表示），那么SMA*算法是完备的。如果任何最优解是可达到的，那么这个算法也是最优的；否则算法会返回可达到的最佳解。从实用的角度，SMA*算法是最好的寻找最优解的通用算法，尤其当状态空间是一个图，单步耗散不一致，并且与维护open表和closed表的附加系统开销相比生成节点的开销更大的时候。

然而在一些非常困难的问题中，通常的情况是SMA*算法将会在候选解路径集里的路径之间换来换去，只有一个很小的子集可以放到内存中。（这很像硬盘页面调度系统遇到的内存反复调入调出问题。）那么重复生成相同节点需要的额外时间意味着一个在有无限的内存的条件下能被A*算法实际解决的问题，对于SMA*算法会成为不可操作的。就是说，内存限制从计算时间的角度能使一个问题成为不可操作的。虽然没有理论能阐明时间和内存之间的折中，看来这是一个不可逃避的问题。唯一出路就是放弃最优化的要求。