使用任意顺序的航路点寻路

Question

• 我在2d区域中有一个航路点列表（2d点列表）。

• 我希望最短的路径至少一次访问任何路标。

• 访问顺序没关系

我必须蛮力吗？

• 计算所有点之间的距离
• 遍历any路径。
• 返回最短的时间

Answer 1

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

这些问题是NP-Complete，但是如果“航路点”的数量相对较少，则可以在完成一些预处理后以蛮力方式解决它。

首先，创建一个新图：

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) 

您可以使用全部到最短路径算法（例如Floyd-Warshall创建w'。这是在O(|V|^3)中完成的。

[拥有后，使用蛮力（O(n!)，其中n是航点的数量）或动态编程（O(2^n*n)），以解决您遇到的旅行商问题。