状态空间搜索的启发式

事实证明，没有一个好的启发式函数，无论前向还是后向搜索都不是高效的。回顾一下第四章中的一个估计从状态到目标的距离的启发式函数；在STRIPS规划中，每个行动的耗散是1，所以距离是行动的数目。基本的想法是考虑行动的效果和必须达到的目标，从而猜测达到所有的目标需要多少个行动。找到一个确切的数目是 NP 难题，但是在大部分时候不需要太多的计算就找一个合理的估计是可能的。我们也可能得到一个可采纳启发式——一个没有过高估计的启发式。这可以和 A*搜索一起使用，找到最优解。

我们可以尝试两种方法。第一种方法是从给定问题的详细描述中得到一个松弛问题，如第四章中描述的那样。松弛问题的最优解耗散——我们希望能够很容易求解——为原始问题提供了一个可采纳启发式。第二个方法是假装一个纯分治算法可行。这被称为子目标独立性假设：求解子目标合取式的耗散可以近似为独立地求解每个子问题的耗散的总和。子目标独立假设可能是乐观的，也可能是悲观的。当每个子目标的子规划间存在负相互作用时，它是乐观的——例如，当一个子规划的行动删除了另一个子规划取得的一个目标时。当子规划包含冗余行动时，它是悲观的，因此也是不可采纳的——例如，在合并的规划中，两个行动可以被一个单一行动所替代。

让我们考虑一下如何得到松弛规划问题。既然能够得到前提和效果的清晰表示，通过修改这些表示得到的处理过程是可行的。（将这个方法与搜索问题相比较，搜索问题中后继函数是一个黑盒子。）最简单的想法是通过从行动删除所有前提来使问题得到松弛。那么每个行动都总是可用的，并且任何文字都可以一步获得（如果有可用的行动——否则，目标是不可能的）。这几乎意味着求解一个目标合取式所需的步骤数就是未满足目标数——几乎但不是完全，因为（1）可能有两个行动，其中的每一个删除另一个获得的目标文字；（2）一些行动可能达到多个目标。假如我们把松弛问题和子目标独立性假设结合起来，这两个问题都随着假设而消失，产生的启发式恰好是未满足目标数。

在许多情况下，至少通过考虑达到多个目标的行动引起的正相互作用，能够得到更精确的启发式。首先，我们通过删除负效果进一步松弛问题（参见习题11.6）。接着，我们计算所需行动的最小数目，而这些行动的正效果的并集能够满足目标。例如，考虑

Goal(A∧B∧C)

Action(x,EFFECT:A∧P)

Action(y,EFFECT:B∧C∧Q)

Action(z,EFFECT:B∧P∧Q)

覆盖目标{A，B，C}的最小集合由行动{X, Y}给出，所以覆盖集启发式返回的耗散值是2。这是子目标独立性假设上的一个改进，原来给出的启发值是3。有一个次要的恼人问题：覆盖集问题是NP难题。一个简单的贪婪覆盖集算法保证返回一个处于真正最小值的log n倍范围内的值，其中n是目标中的文字个数，通常在实际应用中比这个要好。不幸的是，贪婪算法不能保证启发式的可采纳性。

也可以通过只删除负效果而不删除前提来生成松弛问题。也就是说，在原始问题中，如果行动的效果是A∧¬B，那么效果A将仍在松弛问题中。这意味着我们不用再担心子规划间的负相互作用，因为没有行动能够删除别的行动得到的文字。产生的松弛问题得到的解耗散带来的启发式被称为清空删除表启发式。这个启发式是相当精确的，但是计算它涉及到实际运行一个（简单的）规划算法。在实际应用中，松弛问题的搜索通常很快，这个代价是值得的。

这里定义的启发式在前进和回归方向上都能使用。在编写时，使用清空删除表启发式的前向规划器保持领先。随着新的启发式和新的搜索技术被探索，这很可能会发生变化。既然规划问题是指数级难度的[5]，没有算法会对所有问题都有效，但是许多实际问题可以通过本章中提到的启发式方法求解——远比几年前可求解的多。