algorithm - 当没有节点坐标可用时的 A* 启发式

Question

场景:

Suppose I have a large pseudorandom graph complete with edge weights, but without any coordinate information associated with the nodes. In addition, there are N waypoints evenly distributed around the graph, containing precomputed shortest path information from each waypoint to every other node.

目标:

Find the shortest path between a random source and target node.

从我以前使用 A* 解决的问题以及我读过的关于该主题的论文来看，启发式算法似乎通常依赖于欧几里得度量来计算良好的距离近似值，例如一条直线。

因此我的问题是:是否有任何好的启发式可以帮助我解决上述情况，或者我是否被迫依赖纯 Dijkstra 算法(结合预先计算的路点节点)？

任何想法或意见将不胜感激。

编辑

感谢所有提供帮助的人，利用三角不等式成功了。最近的路点计算非常昂贵，因此与纯 Dijkstra 相比平均运行时间要高得多，但这在这个时间点上真的不重要。

以下是探索节点数量的概述(每种图形类型的随机源/目标):

第一种图类型(1)由大约200个节点和250条边组成，而最后一种图类型(40 ) 由大约8000 个节点 和10000 个边 组成(类型越高意味着图越大)。

Answer 1

对于从 A 到 B 的最短路径的长度，我们需要一个乐观的启发式方法。

找到离 A 最近的航路点。称之为 W。

那么 max { d(W,B) - d(W,A), 0 } 是从 A 到 B 的最短路径长度的下界。

Proof:

By the triangle inequality we have d(W,B) ≤ d(W,A) + d(A,B).

Thus d(A,B) ≥ d(W,B) - d(W,A).

您也可以对称地应用这个想法以获得更好的边界。也就是说，找到距离 A 最近的航路点 WA 和距离 B 最近的航路点 WB 然后你的下界是

max { d(WA,B) - d(WA,A), d(WB,A) - d(WB,B), 0 }

这种启发式算法的优点在于，它会随着航路点密度的增加而明显改善。