如何检查一个点是否位于（最小）曼哈顿距离线上？

Question

我有一个 8x10 矩阵，里面有一些方块：

no = [(2,4),(3,4),(6,4),(7,4),(2,5),(3,5),(6,5),(7,5)]

我需要弄清楚两点之间的最短（曼哈顿）路径是否作为嵌套元组（如 ((0,5),(6,2)) 提供给此函数）包含任何块，并围绕它重新路由.

现在要做到这一点，我试图以应用为欧氏距离的作品，要看到，如果逻辑Ç是之间的界限一和乙通过增加从距离一到Ç从距离Ç到乙，看它是否等于A到B，但我不相信数学...

def manhattan_dist(move): #order doesn't matter

    a = move[0][0]

    b = move[0][1]

    c = move[1][0]

    d = move[1][1]

    mandist = abs(a-c)+abs(b-d)

    if (any (abs(a-box[0])+abs(b-box[1])) == (mandist-(abs(c-box[0])+abs(d-box[1]))) for box in no):

        print("blocked")

        #calculate go-around logic

    return mandist

它打印 "blocked" for manhattan_dist(((0,1),(0,7)))，所以我知道我在 python 中也做错了。

Answer 1

由于缺乏代表而回答而不是评论（......我是新来的）。在我看来有点不明确。曼哈顿距离没有一条最短路径……事实上，根据定义，它有许多最短路径。所以也许试着澄清你的意思？顺便说一句，如果您想知道曼哈顿的任何路径是否被阻塞，那么这仅意味着您有一个带有min([a,&nbsp;c])&nbsp;<&nbsp;box[0]&nbsp;<&nbsp;max([a,&nbsp;c])&nbsp;and&nbsp;min([b,&nbsp;d])&nbsp;<&nbsp;box[1]&nbsp;<&nbsp;max([b,&nbsp;d])由于评论中的讨论而进行编辑：首先，总是有精确的abs(a-c) + abs(b-d)&nbsp;选择&nbsp;abs(a-c)具有最小曼哈顿距离的路径。（对于错误的符号表示抱歉；只是遵循问题参数，不幸的是缺乏乳胶支持）。如果你正确地通过几何体，所有被阻挡的最小路径都非常棘手，不会很快。我没有立即看到避免循环遍历所有路径的方法，通过将路径分类为分层树并在方块被阻塞时删除完整分支来获得一些优化......

Answer 2

现在要做到这一点，我试图应用适用于欧几里德距离的逻辑，通过将 A 到 C 的距离添加到 C 到 B 的距离并查看它是否等于从 A 到 B您在此处使用的数学概念称为“度量”。这只是您已经熟悉的欧几里得距离的概括。有关详细信息，请参阅维基百科文章。曼哈顿距离满足度量的所有要求。这意味着，你可以放心，如果d(A, B) + d(B, C) = d(A, C)在B一些最短路径上的谎言之间A和C。与欧几里德距离不同，从A到到的路径可能有许多C相同的距离，其中许多路径可能经过B。