python - 使用 networkx 解决修改后的旅行商问题 (TSP)

Question

我正在尝试解决 TSP 的修改版本。在我的版本中，允许多次访问一个城市，只要路径最短，并且只有部分城市是强制访问的，例如，您可以通过其他城市访问所有子城市，如果路径较短，但如果不是，其他城市可以忽略。NetworkX 有大约。使用 的传统 TSP 的解决方案dwave_networkx.algorithms.tsp.traveling_salesperson，但我无法解决这个问题。一种天真的方法可以是找到子集城市的所有可能组合并检查哪个具有最短的总路径长度，但是该解决方案将具有 ^2 尝试每个组合的复杂性，以及为每两个城市找到最短路径的复杂性。那么，我应该如何使用 NetworkX 来解决这个问题。

标签： pythonalgorithmgraphnetworkxtraveling-salesman

Answer 1

您可以随机选择一条路径并优化其路径。基本上，在两个节点之间随机分配一条路。比在节点上，尝试找到 n+2 个节点的最佳方式。A --> B --> C 如果有最短路径，则尝试 A--> D --> C---E 如果 D 和 E 之间的路径最短，则 D --> K --> E然后再次迭代 A--> D --> F --> E 对我来说听起来是个好主意。我现在没有证据，但它可以为您提供可能的最短路径。我希望这会有所帮助。祝你好运。