8 拼图的复合启发式
Composite heuristic for the 8-puzzle
在阅读人工智能现代方法时，我遇到了从给定问题的子问题的解决成本中推导出启发式的概念。
例如，以下拼图显示了 8 拼图实例的子问题，其目标是将方块 1、2、3、4 放置到正确的位置。
Start State = [ * 2 4 ] Goal State = [ 1 2 ]
[ * * ] [ 3 4 * ]
[ * 3 1 ] [ * * * ]
然后，作者扩展了这个概念，说这些从子问题导出的启发式可以通过取最大值来组合。
h(n)= max{ h1(n), . . , hm(n) }
此外，通过使用这种方法，与 Manhattan distance.
这样的简单启发式方法相比，性能得到了极大的提高。
我一直在努力思考复合启发式方法及其背后的推理。假设我们从以下子问题的解决方案成本中得出两个启发式：
h1234(n) = [ 1 2 ] h5678(n) = [ * * ]
[ 3 4 * ] [ * * 5 ]
[ * * * ] [ 6 7 8 ]
像这样的复合启发式：
h1...8(n)= max{ h1234(n), h5678(n) }
- 真的在寻找完整的 8 拼图问题的解决方案吗？
在我看来，使用像 h1...8(n) 这样的启发式方法，我们最终会在启发式方法 h1234(n) 和 h5678(n) 这反过来可能会导致一个启发式搞乱另一个的工作并且永远无法找到解决方案。
- 或者这些启发式算法会互相帮助以获得完整的解决方案吗？
老实说，我不知道这是怎么回事...
首先，我将简要概述 启发式 背后的思想，以及为什么要解决子问题，也称为 松弛问题 ，有助于找到解决方案。然后，我将对 8 拼图问题进行以下一般考虑，从而回答您的具体问题。更详细的信息，你可以像你已经做的那样，仔细阅读Artificial Intelligence: a Modern Approach, by Stuart and Russell; if you want to deepen the topic about best-first search strategies and heuristics, you can start from one of the seminal papers by Dechter and Pearl, 1984, ACM的第3章，并查看被引用的论文和引用它的人。
启发式和知情搜索概述
使用启发式的思想是通过搜索space（通常是指数大小）来引导搜索，并仔细选择要扩展的节点（这种搜索算法也称为知情搜索 算法）。如果启发式很好（即接近目标的实际成本，从初始状态开始），则搜索过程中扩展的节点数量会大大减少，实际上这个数量是最优的——即没有其他搜索算法可以扩展更少的节点，保证解决方案的最优性。请记住，启发式应该是 admissible——给定节点的值不应超过目标的实际成本。如果使用开放列表，这是唯一需要的 属性，即不消除重复状态。如果重复状态被消除，启发式也应该是一致的——即，给定节点的启发式应该小于或等于到达后继节点的成本之和，并且该后继节点中的启发式。
通常，可以在更短的计算时间内找到一个轻松问题的解决方案。可以从该解决方案中提取启发式方法，并且通常比仅来自对整个问题的估计的启发式方法提供更多信息，因为该解决方案提供了应该执行的实际操作。请注意，在定义子问题时，重要的是要检查从子问题的解决方案中得出的启发式是否仍然适用于一般问题，以便获得最佳解决方案。
8 题
在 8-puzzle 的特定情况下，来自子问题的启发式对于原始问题仍然是直观可接受的。具体来说，原问题的最优解也是松弛问题的解，并且还满足所有的松弛问题
约束。因此，解决方案成本最多 与原始方案相匹配
最优解。其次，松弛问题的约束较少。因此，搜索算法可以找到成本较低的解决方案并提供 较低 成本，因此是可接受的、宽松的解决方案。
鉴于此分析和对您问题的回答，使用您提到的启发式方法可以找到完整的 8 拼图问题的解决方案。采用 max 可以使估计值更接近（并且可接受）解决方案的实际成本，从而有助于扩展更少的节点数。
在阅读人工智能现代方法时，我遇到了从给定问题的子问题的解决成本中推导出启发式的概念。
例如，以下拼图显示了 8 拼图实例的子问题，其目标是将方块 1、2、3、4 放置到正确的位置。
Start State = [ * 2 4 ] Goal State = [ 1 2 ]
[ * * ] [ 3 4 * ]
[ * 3 1 ] [ * * * ]
然后，作者扩展了这个概念，说这些从子问题导出的启发式可以通过取最大值来组合。
h(n)= max{ h1(n), . . , hm(n) }
此外，通过使用这种方法，与 Manhattan distance.
这样的简单启发式方法相比，性能得到了极大的提高。我一直在努力思考复合启发式方法及其背后的推理。假设我们从以下子问题的解决方案成本中得出两个启发式：
h1234(n) = [ 1 2 ] h5678(n) = [ * * ]
[ 3 4 * ] [ * * 5 ]
[ * * * ] [ 6 7 8 ]
像这样的复合启发式：
h1...8(n)= max{ h1234(n), h5678(n) }
- 真的在寻找完整的 8 拼图问题的解决方案吗？
在我看来，使用像 h1...8(n) 这样的启发式方法，我们最终会在启发式方法 h1234(n) 和 h5678(n) 这反过来可能会导致一个启发式搞乱另一个的工作并且永远无法找到解决方案。
- 或者这些启发式算法会互相帮助以获得完整的解决方案吗？
老实说，我不知道这是怎么回事...
首先，我将简要概述 启发式 背后的思想，以及为什么要解决子问题，也称为 松弛问题 ，有助于找到解决方案。然后，我将对 8 拼图问题进行以下一般考虑，从而回答您的具体问题。更详细的信息，你可以像你已经做的那样，仔细阅读Artificial Intelligence: a Modern Approach, by Stuart and Russell; if you want to deepen the topic about best-first search strategies and heuristics, you can start from one of the seminal papers by Dechter and Pearl, 1984, ACM的第3章，并查看被引用的论文和引用它的人。
启发式和知情搜索概述
使用启发式的思想是通过搜索space（通常是指数大小）来引导搜索，并仔细选择要扩展的节点（这种搜索算法也称为知情搜索 算法）。如果启发式很好（即接近目标的实际成本，从初始状态开始），则搜索过程中扩展的节点数量会大大减少，实际上这个数量是最优的——即没有其他搜索算法可以扩展更少的节点，保证解决方案的最优性。请记住，启发式应该是 admissible——给定节点的值不应超过目标的实际成本。如果使用开放列表，这是唯一需要的 属性，即不消除重复状态。如果重复状态被消除，启发式也应该是一致的——即，给定节点的启发式应该小于或等于到达后继节点的成本之和，并且该后继节点中的启发式。
通常，可以在更短的计算时间内找到一个轻松问题的解决方案。可以从该解决方案中提取启发式方法，并且通常比仅来自对整个问题的估计的启发式方法提供更多信息，因为该解决方案提供了应该执行的实际操作。请注意，在定义子问题时，重要的是要检查从子问题的解决方案中得出的启发式是否仍然适用于一般问题，以便获得最佳解决方案。
8 题
在 8-puzzle 的特定情况下，来自子问题的启发式对于原始问题仍然是直观可接受的。具体来说，原问题的最优解也是松弛问题的解，并且还满足所有的松弛问题 约束。因此，解决方案成本最多 与原始方案相匹配 最优解。其次，松弛问题的约束较少。因此，搜索算法可以找到成本较低的解决方案并提供 较低 成本，因此是可接受的、宽松的解决方案。
鉴于此分析和对您问题的回答，使用您提到的启发式方法可以找到完整的 8 拼图问题的解决方案。采用 max 可以使估计值更接近（并且可接受）解决方案的实际成本，从而有助于扩展更少的节点数。