graph-algorithm - 旅行推销员变种

Question

他们是旅行商问题的变体还是关于以下问题的其他算法：

假设 G 是一个不完全的无向加权图。V 是 G 的顶点的子集。

如何沿着 V（可能还有 G 的其他一些顶点）找到一个简单的闭合回路，它在 V 的每两个顶点之间具有最小的权重。

谢谢

- - - - - - - - - - - 编辑 - - - - - - - - - - - -

这个问题是否有名称或已发表的文件或相关研究论文？

Answer 1

首先，因为 V（如您所说，它是 G 的顶点的子集）本身就是一个加权图 - 首先计算 V 的边，这样您就可以忽略 G。

例如 G 的这个输入：

G1 (Va) -- 5 meter --> G2 (no V) -- 10 meter --> G3 (Vb)

可以简化为 V 的这个输入：

Va -- 15 meter --> Vb

当输入在 V 顶点之间有多个路径（中间没有其他 V 顶点）时，乐趣就开始了：

G1 (Va) -- 5 meter --> G2 (no V) -- 10 meter --> G3 (Vb)
G1 (Va) -- 7 meter --> G4 (no V) -- 7 meter --> G3 (Vb)

那么简化形式是（它采取第二条路线）：

Va -- 14 meter --> Vb

在简化过程中使用 Dijkstra 算法。

其次，在 V 上应用一个好的 TSP 算法。它是 NP 完全的，所以没有完美的算法。根据您的编程语言（java、C/C++、...），有许多可用的框架。