用networkx求解一个修正的旅行商问题（TSP）

Question

我试图解决TSP的一个修改版本。在我的版本中，允许对一个城市进行多次访问，只要路径最短，而且只有一部分城市必须访问，如中所示，如果路径较短，您可以通过其他城市访问所有子集城市，但如果路径较短，则可以忽略其他城市。NetworkX使用dwave_networkx.algorithms.tsp.traveling_salesperson为传统TSP提供了近似的解决方案，但我在解决这个问题时遇到了困难。一种简单的方法是找到子集城市的所有可能组合，并检查哪一个具有最短的总路径长度，但该解决方案在尝试每个组合时的复杂度为n^2，再加上为每两个城市寻找最短路径的复杂度。那么，我应该如何使用NetworkX来解决这个问题呢

Answer 1

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