1

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

例如，以下拼图显示了 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. 还是启发式方法会相互帮助以实现完整的解决方案？

老实说，我不明白这怎么可能……

4

1 回答 1

1

首先，我将简要概述启发式算法背后的想法，以及为什么解决子问题（也称为轻松问题）有助于找到解决方案。然后，我将对 8-puzzle 问题提出以下一般性考虑，从而回答您的具体问题。如需更详细的信息，您可以像之前一样开始仔细阅读Stuart 和 Russell 所著的《人工智能：现代方法》第 3 章；如果您想深入了解有关最佳优先搜索策略和启发式的主题，可以从Dechter 和 Pearl，1984，ACM的一篇开创性论文开始，查看被引用的论文和引用它的人。

启发式和知情搜索概述

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

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

8 谜题

在 8-puzzle 的特定情况下，来自子问题的启发式仍然直观地适用于原始问题。具体来说，原问题的最优解也是松弛问题的解，并且满足所有松弛约束。因此，解决方案成本最多匹配原始最优解决方案。其次，松弛问题的约束较少。因此，搜索算法可以找到成本更低的解决方案，并提供成本更低、因此是可接受的、宽松的解决方案。

鉴于此分析并回答了您的问题，使用您提到的启发式方法可以找到完整的 8 谜题问题的解决方案。采用max允许的估计值更接近（并且可以接受）解决方案的实际成本，从而有助于扩展更少的节点。

于 2016-03-20T06:13:40.937 回答