algorithm - 曼哈顿距离泛化

Question

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

Answer 1

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

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

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

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