algorithm - 曼哈顿距离泛化

Question

对于我正在进行的一项研究，我试图找到一个基于曼哈顿距离的令人满意的启发式方法，它可以处理任何问题和领域作为输入。这也称为域独立启发式。现在，我知道如何将曼哈顿距离应用于基于网格的问题。有人可以给出提示如何将其概括为适用于每个领域和问题，而不仅仅是基于网格的问题吗？

Answer 1

曼哈顿距离的概括很简单。它是一个度量，将两个多维点之间的距离定义为沿每个维度的距离之和：

md(A, B) = dist(a1, b1) + dist(a2, b2) + . . .

假设沿每个维度的距离很容易计算。对于数字，距离是值之间差异的绝对值。

这也可以扩展到其他领域。例如，两个字符串之间的距离可以被视为 Levenshtein 距离——这将被证明是一个与其他维度相结合的有趣度量。

Answer 2

曼哈顿距离启发式尝试测量找到到达目标状态的路径所需的最小步数。越接近实际步数，在搜索过程中必须扩展的节点就越少，在完美启发式的极端情况下，您只扩展保证在目标路径上的节点。

对于推广这个想法的更学术的方法，您需要四处搜索与领域无关的启发式方法；在 1990 年代末和 2000 年代初，对此进行了大量研究，尽管即使在今天，少量的领域知识通常可以为您带来更好的结果。话虽如此，有一些好的地方可以开始：

• 删除放松：扩展功能可能包含一些限制，删除一个或多个这些限制，您最终会遇到一个更简单的问题，一个可能可以实时解决的问题，您将使用由此产生的值放松问题作为启发式值。例如，在滑动瓷砖拼图中，删除一个棋子不能在其他棋子之上移动的约束，最终得到曼哈顿距离，放宽棋子只能移动到相邻方格的约束，最终得到汉明距离启发式。

• 抽象：将实际搜索中的每个状态映射到可以完全评估的较小抽象状态空间。模式数据库是该领域非常流行的工具。

• 关键路径：当您知道必须通过特定状态（在真实状态空间或抽象状态空间中）时，您可以仅在关键点之间执行多次搜索，以大大减少您必须在全状态空间

• 地标：以通常高计算时间为代价的非常准确的启发式方法。地标是特定位置，您可以在其中预先计算到每个可能的其他状态的距离（通常根据图形大小使用 5-25 个地标），然后在评估每个节点时使用这些预先计算的值计算下限可能距离。

还有一些其他类别的域独立启发式，但这些是经典规划应用程序中最流行和广泛使用的。