一尘不染

在图中至少访问X个节点的图中找到最短路线

algorithm

即使我仍然是初学者,我还是喜欢解决与图有关的问题(最短路径,搜索等)。最近,我遇到了这样的问题:

给定一个具有N个节点和E个边(两个节点之间最多1个边,一个边只能放置在两个不同节点之间)的无向加权(无负值)图,并且必须访问X个节点列表,找到从节点0开始,访问所有X节点并返回到节点0的最短路径。始终存在至少一条连接任何两个节点的路径。

限制为1 <= N <= 40 000/1 <= X <= 15/1 <= E <= 50000

这是一个例子:

在此处输入图片说明

红色节点(0)应该是路径的起点和终点。您必须访问所有蓝色节点(1、2、3、4)并返回。最短的路径是:

0-> 3-> 4-> 3-> 2-> 1-> 0,总费用为30

我考虑过使用Dijkstra查找所有X(蓝色)节点之间的最短路径,然后贪婪地选择最接近的未访问X(蓝色)节点,但是它不起作用(在纸上用32代替30)。后来我还注意到,仅找到所有X对节点之间的最短路径将花费O(X * N ^ 2)的时间,这对于太多的节点来说太大了。

对于电路,我唯一能找到的就是欧拉电路,该电路只允许访问每个节点一次(我不需要)。Dijkstra是否可以解决此问题,或者还有其他算法可以解决此问题吗?


阅读 209

收藏
2020-07-28

共1个答案

一尘不染

这是一个可能足够快的解决方案:
1)从每个蓝色节点运行最短路径搜索算法(可以在O(X *(E log N)中完成))以计算成对距离。
2)建立一个仅包含零个顶点和蓝色顶点(X + 1个顶点)的新图形。使用第一步中计算的成对距离添加边。
3)新的图形足够小,可以使用针对TSP的动态编程解决方案(它具有O(X ^ 2 * 2 ^ X)时间复杂度)。

2020-07-28