algorithm - 以任何顺序使用航点进行寻路

Question

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

• 我想要至少一次访问任何航点的最短路径。

• 访问顺序无关紧要

我必须暴力破解吗？

• 计算所有点之间的距离
• 走过任何一条路。
• 返回最短的

标签： algorithmpath-finding

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)），以解决您遇到的旅行商问题。