避免重复状态

3.5 避免重复状态

到现在为止，除了一种最重要的复杂情况外我们已经讨论了搜索过程中的其它情况：这种情况就是由于扩展已经遇到并扩展过的状态而可能造成的时间浪费。对于某些问题来说，这种可能性永远不会出现：状态空间是一棵树，并且到达每个状态只有一条路径。八皇后问题的有效形式化（每个新的皇后只能放在最左侧的空列）之所以是有效的在很大程度上就是因为每个状态只能通过唯一的路径到达。如果我们在形式化八皇后问题的时候允许新的皇后放在任何一列，那么每个有n个皇后的状态都可以经由n!条路径到达。

对于一些问题，重复的状态是不可避免的。这包括了所有行动可逆的问题，例如寻径问题和滑块问题。这些问题所对应的搜索树都是无限的，但是如果我们对它的一些重复状态进行剪枝，那么通过只生成能够覆盖状态空间图的那部分搜索树，我们可以把搜索树修剪到有限大小。考虑有固定深度的搜索树，容易发现去除重复状态能使搜索代价成指数级减少的情况。在极端情况下，一个大小为d+1的状态空间（图 3.18（a））会生成一棵有 2d个叶节点的树（图 3.18（b））。一个更实际的例子是如图3.18（c）所示的矩形网格。在一个网格上，每个状态有四个后继，所以包括重复状态的搜索树有 4d个叶节点；然而对于任何给定的状态在d步以内只有2d2个不同的状态。当d = 20的时候，这意味着上万亿个节点中只包含800个不同的状态。

图3.18 生成指数增长的搜索树的状态空间。（a）在这个状态空间中从状态A到B有两种可能的行动，从状态B到C有两种可能的行动，依此类推。状态空间包含d+1个状态，这里d是最大深度。（b）对应的搜索树，它有2d个分支，对应于状态空间中的2d条路径。（c）一个矩形网格空间。由初始状态(A)出发的两步之内达到的状态用灰色的点表示

而如果算法不检测重复状态的话，它们还可能使一个本来可解的问题变成不可解。检测通常意味着把要扩展的节点与已经扩展过的节点相比较；如果找到匹配的节点，那么这个算法发现了两条到达同一状态的路径，可以抛弃其中的一条。

对于深度优先搜索，内存中的节点仅仅包括从根节点到达当前节点的路径上的所有节点。比较当前节点和路径上的那些节点，使得算法能够检测出可以立刻删除的循环路径。这对保证有限的状态空间不会因为循环而变成无限的搜索树是有好处的；但不幸的是，这并不能避免如图3.18所示的问题中不循环路径的指数级增殖。避免这些情况的唯一途径是在内存中保留更多节点。在空间和时间之间有一个基本的折中。遗忘历史的算法注定要重复历史。

如果一个算法记住它访问过的每个状态，那么相当于它直接探索状态空间图。我们可以对一般的TREE-SEARCH算法进行修改，增加一个数据结构称为closed表，用它存储每个扩展过的节点。（存储未扩展的边缘的表有时被称为open表。）如果当前的节点与closed表中的某个节点相匹配的话，那么它将被放弃而不是被扩展。这个新的算法称为GRAPH-SEARCH（图3.19）。在含有很多重复状态的问题中，GRAPH-SEARCH要比TREE-SEARCH有效得多。它在最坏情况下的时间和空间需求和状态空间的大小成正比。这可能比O(bd)要小得多。

图搜索的最优性是一个棘手的问题。我们之前已经说过当一个重复的状态被删除的时候，算法就找到了能达到同一状态的两条路径。图3.19所示的算法GRAPH-SEARCH总是放弃新发现的路径；显然，如果新找到的路径比原来的路径短，GRAPH-SEARCH会错过最优解。幸运的是，我们可以证明（习题3.12）在使用单步耗散是常数的代价一致搜索或者广度优先搜索时这种情况是不会发生的；因此，这两种最优的树搜索策略同样也是最优的图搜索策略。另一方面，迭代深入搜索使用深度优先扩展，而且容易在找到最优解之前就找到到达一个节点的非最优路径。因此，迭代深入图搜索需要检查到达一个节点的新发现的路径是否比原来的路径好，如果是的话，就需要修正该节点的后代的深度和路径耗散。

注意，使用 closed 表意味着深度优先搜索和迭代深入搜索不再具有线性的空间需求。因为GRAPH-SEARCH算法在内存中保留每个节点，有些搜索由于内存的限制是不可行的。

图3.19 一般的图搜索算法。closed集可以用一个哈希表来实现，以便有效地检查重复状态。这个算法假设到达状态s的第一条路径是耗散最少的