曼哈顿距离泛化

Question

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

Answer 1

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

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

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

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

Answer 2

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

要获得更学术化的方法来概括这个想法，您想四处搜索与领域无关的启发式方法；在 1990 年代后期和 2000 年代初期，对此进行了大量研究，尽管即使在今天，少量的领域知识通常也能为您带来更好的结果。话虽这么说，但还是有一些不错的起点：

• delete relaxation: expand 函数可能包含一些限制，删除其中一个或多个限制，你最终会遇到一个更容易的问题，一个可能可以实时解决的问题，您将使用该轻松问题生成的值作为启发式值。例如在滑动拼图中，删除一块不能移动到其他块之上的约束，你最终得到曼哈顿距离，放宽一块只能移动到相邻的方块，你最终得到汉明距离启发式。

• 抽象：将真实搜索中的每个状态映射到一个更小的抽象状态space，你可以充分评估。模式数据库是该领域非常流行的工具。

• 关键路径：当你知道你必须通过特定状态时（在真实状态space或抽象状态space) 您可以仅在关键点之间执行多次搜索，以大大减少在完整状态下必须搜索的节点数 space

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

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