以任意顺序使用 waypoints 寻路

Question

我在二维区域中有一个 waypoints（二维点列表）的列表。
我想要最短路径至少访问任何一个航路点一次。
访问顺序无所谓

我必须暴力破解吗？

计算所有点之间的距离
走过任何路径。
return最短

Answer 1

您的问题是 Hamiltonian Path / Traveling Salesman Problem 的变体。

这些问题是NP-Complete的，但是如果"waypoints"的数量比较少，你可以在做一些预处理之后用暴力破解的方式解决它。

首先，创建一个新图表：

G'=(V',E', w') Where
V' = {v | v is a waypoint }
E' = { (u,v) for all u,v in V' }
w'(u,v) = D(u,v) (where D is a function for shortest path between waypoints in the original graph) (D:VxV->R)

您可以使用全对全最短路径算法创建w'，例如Floyd-Warshall。这是在 O(|V|^3).

中完成的

有了之后，运行一个暴力破解（O(n!)，其中n是waypoints的个数）或者动态规划（O(2^n*n) ), 来解决你遇到的旅行商问题。

以任意顺序使用 waypoints 寻路

Pathfinding with waypoints in any order

algorithm

path-finding