8-拼图的复合启发式

Question

在阅读“人工智能”(一种现代方法)时，我遇到了从给定问题的子问题的解决成本中得出启发式的概念。

例如，下面的谜题显示了8-益智实例的一个子问题，其中的目标是将瓷砖1、2、3、4放置到正确的位置。

Start State = [ * 2 4 ]    Goal State = [   1 2 ]                      
              [ *   * ]                 [ 3 4 * ]
              [ * 3 1 ]                 [ * * * ]  

然后，作者扩展了这个概念，认为从子问题中得到的这些启发式方法可以通过取最大值来组合。

h(n)= max{ h1(n), . . , hm(n) }

此外，与简单的启发式方法(如曼哈顿距离 )相比，这种方法的性能有了很大的提高。

我一直试图把我的头脑集中在复合启发式算法和推理上。假设我们有两个启发式算法，它们来自以下子问题的解决成本：

h1234(n) = [   1 2 ]     h5678(n) = [   * * ]                    
           [ 3 4 * ]                [ * * 5 ]
           [ * * * ]                [ 6 7 8 ]

复合启发式算法会像：

h1...8(n)= max{ h1234(n), h5678(n) }

1. 真的在寻找一个完整的8难题的解决方案吗？

在我看来，使用诸如H1.8(N)这样的启发式方法，我们最终会在启发式h1234(n)和h5678(n)之间交替，这反过来可能导致一个启发式混淆了另一个启发式的工作，却永远无法找到一个解决方案。

1. 或者启发式方法会帮助对方找到完整的解决方案吗？

老实说，我看不出这是怎么回事。

Answer 1

首先，我将简要概述启发背后的想法，以及为什么解决一个子问题(也称为轻松问题)有助于找到解决方案。然后，我将对8字谜问题提出以下一般性考虑，从而回答您的具体问题。要获得更详细的信息，你可以像你已经做过的那样，仔细阅读斯图尔特和罗素的“人工智能:一种现代方法”第三章；如果你想深化关于最佳搜索策略和启发式的主题，你可以从德克特和珍珠，1984年，ACM的一篇开创性论文开始，看看引用的论文和引用的文章。

启发式和知情搜索综述

使用启发式算法的思想是引导搜索通过搜索空间(通常是指数大小)并仔细选择要扩展的节点(这种类型的搜索算法也称为知情搜索算法)。如果启发式是好的(即，接近目标的实际成本，从初始状态开始)，那么在搜索过程中扩展的节点数量就会大大减少，而且这个数目实际上是最优的--也就是说，没有其他搜索算法能够扩展更少的节点，从而保证解决方案的最优性。记住，启发式应该是可接受的--它的给定节点的值不应该超过目标的实际成本。如果使用打开的列表，这是唯一需要的属性，即不消除重复状态。如果消除了重复状态，那么启发式也应该是一致的--也就是说，给定节点的启发式应该小于或等于到达后续节点的成本之和，以及该后续节点中的启发式。

通常，可以在较短的计算时间内找到一个轻松问题的解决方案。可以从该解决方案中提取启发式，并且通常比仅从整个问题的估计中得出的启发式更能提供信息，因为该解决方案提供了应该执行的实际操作。请注意，在定义子问题时，必须检查从子问题的解中得到的启发式是否仍然适用于一般问题，这样才能得到最优解。

8-难题

在8-益智的具体情况下，从子问题中得到的启发式算法在直觉上仍然适用于原问题。具体而言，原问题的最优解也是松弛问题的一个解，并且满足所有的松弛约束。因此，求解成本最多与匹配，是最初的最优解。第二，放松问题的约束较少。因此，该搜索算法可以找到更便宜的解，并提供一个较低的代价，从而可接受、轻松的解。

给出这个分析并回答你的问题，使用你提到的启发式方法可以找到一个完整的8字谜问题的解决方案。采用max可以使估计值更接近解决方案的实际成本(并且是可接受的)，从而帮助扩展节点数量。