问如何找到有虫洞节点的最短路径？

EN

大多数路径查找算法都是用图来定义的，而不是用网格定义的。在图中，两个本来遥远的节点之间的连接并不是一个真正的问题。

然而，你必须注意你的启发式。对于虫洞，两个节点之间的最小距离不再是欧氏距离，距离不满足三角形不等式。这种启发式方法对于A*是不可接受的。因此你不能轻易地使用A*。

当然，不使用启发式的路径查找算法(如Dijkstra )仍然有效。这更像是一个广度优先搜索，并将选择你的虫洞，而不需要额外的努力。然而，Dijkstra将访问更多具有良好启发式的A*节点。(Dijkstra等价于带heuristic(x) = 0的A* )

我认为，如果你使用一种启发式方法，将所有传出的虫洞视为直接指向目标的虫洞，则A*将有效:启发式可能低估了距离，但绝不能高估它。例如，启发式办法是：

def wormhole_heuristic(x):
  return min(euclidean_distance(x, g) for g in [goal, wormholes...])

对于非常精确的启发式，您可以(递归地)将从虫洞端点到目标或下一个虫洞的距离相加。即，作为预计算，您可以在包含所有虫洞和目标的(完全连通)子图上执行路径查找，其中两个节点之间的距离是它们的欧几里德距离。如果虫洞的数量远远少于网格上可访问的单元格的数量，这可能是有益的。新的启发是：

def wormhole_heuristic(x):
  direct = euclidean_distance(x, goal)
  via_wormhole = min(euclidean_distance(x, w) + wormhole_path_distance(w, goal) for w in wormholes)
  return min(direct, via_wormhole)

正如@Caleth在评论中指出的，这一切都是可调的，我们可以改进第一个虫洞启发式，而无需通过虫洞网络进行完全路径查找，方法是增加最后虫洞出口与目标之间的距离。因为我们不知道最后会使用哪个虫洞出口，而且我们也不能高估，所以我们必须假设出口离目标最近：

def wormhole_heuristic(x):
  direct = euclidean_distance(x, goal)
  to_next_wormhole = min(euclidean_distance(x, w) for w in wormholes)
  from_last_wormhole = min(euclidean_distance(w.exit, goal) for w in wormholes)
  via_wormhole = to_next_wormhole + from_last_wormhole
  return min(direct, via_wormhole)

在一个具有协调点的网格上，有一个有6个顶点的图：

A ( 0,0)
B ( 4,7)
C ( 7,4)
D (10,4)
E (16,2)
F (16,0)

您可以在这些顶点上生成一个完整的图，并为每条边分配一个代价，其中标准边的成本为MAX( ABS( x1 - x2 ), ABS( y1 - y2 ) )，虫洞的成本为0。

这将给你成本(作为一个邻接矩阵)：

   A  B  C  D  E  F
- -- -- -- -- -- --
A  -  7  7 10 16 16
B  7  -  0  6 12 12
C  7  0  -  3  9  9
D 10  6  3  -  0  6
E 16 12  9  0  -  2
F 16 12  9  6  2  -

如果存在单向翘曲，则只在图(或邻接矩阵)中创建沿该方向而不是相反方向的边。

然后，您可以将迪克斯特拉算法与优先级队列一起使用。

从A开始并将每个相邻的边缘推入优先级队列：

格式：(路径:成本)

queue     = [ (A-B : 7), (A-C : 7), (A-D : 10), (A-E : 16), (A-F : 16) ]

当项目被推送到队列中时--跟踪每个顶点的最小成本，并且只有在成本低于现有最小成本的情况下，才将路径推到队列上。

min-costs = { A: 0, B: 7, C: 7, D: 10, E: 16, F: 16 }

从队列中删除第一项，如果其成本仍然与最小成本相匹配，则将该路径形成的所有复合路径及其相邻边缘推回优先级队列(如果复合路径的成本低于现有的最小值)：

删除：(A-B : 7)

• 尝试(A-B-A : 14) -拒绝作为更高的成本
• 尝试(A-B-C : 7) -拒绝相同的成本
• 尝试(A-B-D : 13) -拒绝作为更高的成本
• 尝试(A-B-E : 19) -拒绝作为更高的成本
• 尝试(A-B-F : 19) -拒绝作为更高的成本

删除(A-C : 7)

• 尝试(A-C-A : 14) -拒绝作为更高的成本
• 尝试(A-C-B : 7) -拒绝相同的成本
• 尝试(A-C-D : 10) -拒绝相同的成本
• 尝试(A-C-E : 16) -拒绝相同的成本
• 尝试(A-C-F : 16) -拒绝相同的成本

删除(A-D : 10)

• 尝试(A-D-A : 20) -拒绝作为更高的成本
• 尝试(A-D-B : 16) -拒绝作为更高的成本
• 尝试(A-D-C : 13) -拒绝作为更高的成本
• 尝试(A-D-E : 10) -插入队列
• 尝试(A-D-F : 16) -拒绝相同的成本

现在，队列看起来如下：

queue     = [ (A-D-E : 10), (A-E : 16), (A-F : 16) ]
min-costs = { A: 0, B: 7, C: 7, D: 10, E: 10, F: 16 }

删除(A-D-E : 10)

• 尝试(A-D-E-A : 26) -拒绝作为更高的成本
• 尝试(A-D-E-B : 22) -拒绝作为更高的成本
• 尝试(A-D-E-C : 19) -拒绝作为更高的成本
• 尝试(A-D-E-D : 10) -拒绝相同的成本
• 尝试(A-D-E-F : 12) -插入队列

然后排队的是：

queue     = [ (A-D-E-F : 12), (A-E : 16), (A-F : 16) ]
min-costs = { A: 0, B: 7, C: 7, D: 10, E: 10, F: 12 }

删除(A-D-E-F : 12)，发现您已经以12的成本到达了目标节点。

注意:路径(A-B-C-D-E-F)__、(A-C-D-E-F)和(A-D-E-F)都有相同的最小成本12。

建立一个包含所有顶点的矩阵，并使用算法或Bellman算法。两者都将产生一个矩阵，在所有点之间有尽可能最短的路径。然后，您可以遍历矩阵，找到连接两个点的最短路径。(您的问题与不对称的TSP相同)。