设计可采纳的启发函数

4.2.2 设计可采纳的启发函数

我们已经看到h1（不在位的棋子数）和h2（曼哈顿距离）对于八数码游戏是相当好的启发式，并且h2更好。h2可能是如何被提出来的？计算机是否可能机械地设计这样的启发式？

h1和h2评估的是八数码游戏中剩余路径的长度，但是对于游戏的一个简化版本它们也是非常精确的路径长度。如果游戏的规则改变为每个棋子可以随便移动，而不是只能移动到与其相邻的空位上，那么h1将给出最短解的确切步数。类似地，如果一个棋子可以向任意方向移动一步，甚至移到一个已经被其它棋子占据的位置上，那么h2也将给出最短解的确切步数。降低了行动限制的问题称为松弛问题。一个松弛问题的最优解的耗散是原问题的一个可采纳的启发式。该启发式是可采纳的，因为根据定义原始问题的最优解也是该松弛问题的一个解，因此它的耗散不低于松弛问题的最优解。由于得到的启发式是松弛问题的确切耗散，它一定遵守三角不等式，因而是一致的（参见第4.1.2节）。

如果问题的定义是通过形式化语言描述的，那么自动地构造它的松弛问题是可能的[12]。例如，如果八数码游戏的行动描述如下：

一个棋子可以从方格A移动到方格B，如果

A与B水平或垂直相邻而且B是空的，

我们可以去掉其中一个或者两个条件，生成三个松弛问题：

（a）一个棋子可以从方格A移动到方格B，如果A和B相邻。

（b）一个棋子可以从方格A移动到方格B，如果B是空的。

（c）一个棋子可以从方格A移动到方格B。

由（a），我们可以得到 h2（曼哈顿距离）。原因是如果我们依次将每个棋子移入其目的地，那么 h2就是相应的步数。由（b）得到的启发式将在习题4.9中讨论。由（c）我们可以得到h1（不在位的棋子数），因为如果把不在位的棋子一步移到其目的地，h1就是相应的步数。注意至关重要的是：用这种技术生成的松弛问题本质上不用搜索就能求解，因为松弛规则使原问题分解成八个独立的子问题。如果松弛问题很难求解，使用对应的启发式就得不偿失了。[13]

一个称为ABSOLVER的程序可以从原始问题的定义出发，使用“松弛问题”方法和各种其它技术自动地生成启发式（Prieditis，1993）。ABSOLVER 能够为八数码游戏生成比以前已有的启发式都好的新启发式，并且为著名的魔方游戏找到了第一个有用的启发式。

生成新启发函数的一个问题是经常不能找到“无疑最好的”启发式。如果一个可采纳启发式的集合h1... hm对问题是可用的，并且其中没有哪个比其它的有优势，我们应该选择哪个？其实我们不用选择。我们可以得到其中最好的，通过定义：

h(n) = max{h1(n), … , hm(n)}。

这种合成的启发式使用的是对应于问题中节点的最精确的函数。因为它的每个成员启发式都是可采纳的，所以h也是可采纳的；也很容易证明h是一致的。此外，h也比所有成员启发式更有优势。

可采纳的启发式也可以从给定问题的子问题的解耗散得到。例如，图4.9显示了图4.7所示的八数码游戏实例的一个子问题。这个子问题涉及使棋子1、2、3、4移动到正确的位置。显然，这个子问题的最优解的耗散是完整问题的耗散下界。在某些情况下这实际上比曼哈顿距离更准确。

图4.9 图4.7所示的八数码游戏实例的一个子问题。它的目标是将棋子1、2、3和4移到正确的位置上，而不考虑其它棋子的情况

模式数据库的想法就是存储每个可能的子问题实例——在我们的例子中，就是四个棋子和一个空位组成的每个可能局面——的精确解耗散。（注意其它四个棋子的位置与解决这个子问题是无关的，但是移动那四个棋子的耗散也要算在总耗散里。）然后，我们对搜索中遇到的每个完全状态通过在数据库里查找出相应的子问题布局都能计算出一个可采纳的启发式hDB。该数据库本身的构造是通过从目标状态向后搜索并记录下每个新遇到模式的耗散完成的；这个搜索的开销分摊到许多子问题实例上。

1-2-3-4的选择是相当随意的；我们也可以构造5-6-7-8或者2-4-6-8的数据库，等等。每个数据库都能产生一个可采纳的启发式，这些启发式可以像前面所讲的那样取最大值的方式组合使用。这种组合的启发式比曼哈顿距离要精确得多；求解随机的15数码游戏时所生成的节点数要比用曼哈顿距离作为启发函数扩展的节点数少1000倍。

有人可能会想，1-2-3-4数据库和5-6-7-8数据库的子问题看起来没有重叠，从它们得到的启发式是否可以相加？相加得到的启发式是否还是可采纳的？答案是否定的，因为对于给定的状态 1-2-3-4子问题的解和5-6-7-8子问题的解几乎肯定有一些重复的移动——不移动5-6-7-8，1-2-3-4也不可能移入正确位置，反之亦然。不过如果我们不计这些移动又会怎样？就是说，我们记录的不是求解1-2-3-4子问题的总耗散值，而只是涉及1-2-3-4的移动次数。那么很容易看出来两个子问题的耗散之和仍然是求解整个问题的耗散的下界。这个想法就是无交集的模式数据库。用这样的数据库，我们可以在几毫秒内解决一个随机的15数码游戏——与使用曼哈顿距离相比生成的节点数减少了10 000倍。对于24数码游戏则可以加速百万倍。

无交集的模式数据库在滑动棋子问题上是可行的，因为问题可以如此划分，使得每次移动只影响其中的一个子问题——因为一次只移动一个棋子。对于诸如魔方这样的问题，这种划分是不可行的，因为每步移动都会影响到26个立方体中的8块或9块。当前，还不清楚对于这样的问题如何定义无交集的数据库。