python tsp 旅行商无向图

Question

在其他帖子中，Networkx 被建议为“我的 friend ”。但是对于 TSP 问题的特定解决方案，似乎没有现成的可用函数。即 Creating undirected graphs in Python

我有一个无向图，建议的解决方案都与有向图有关，我想知道一个简短的游览，以使用可用边访问所有节点。

(另外，我在 networkx 的文档中找不到带有有向图的 tsp)

有没有人对无向图做过这样的事情，或者我应该修改有向图的解决方案，使未连接的节点具有无限成本？

编辑:我正在学习:实际上，由于图是未加权的(或“所有权重”都相同)，并且并非每个节点都连接到所有其他节点，我只需要在图中找到一个包含所有节点的循环节点。当该循环不存在时，节点可能会重复(因此，它不再是循环......)。没有孤立的组(从每个节点到另一个节点都有一条路径)。我认为这不是推销员问题？!

感谢您到目前为止的反馈(当毫秒开始变得重要时，我将安装一个 photofinish :) )

Answer 1

如果您已经有了有向图的代码，我会转换您的无向图。用两条有向边替换每条无向边，每个方向一条边，保留边权重。