寻找最短的线路在访问至少一次x个节点图 [英] Finding shortest circuit in a graph that visits X nodes at least once

问题描述

虽然我还是个初学者，我喜欢解决图形相关的问题（最短路径，搜索等）。最近，我面临的一个问题是这样的：

Even though I'm still a beginner, I love solving graph related problems (shortest path, searches, etc). Recently I faced a problem like this :

给定的非定向，加权（无负值）图与N个节点和E边缘（最多两个节点之间1边缘，边缘只能被放置在两个不同的节点之间）和X节点的列表即你必须访问，发现从节点0开始的最短路径，访问所有的X节点，并返回到节点0。总有至少一条路径连接任何两个节点。

Given a non-directed, weighted (no negative values) graph with N nodes and E edges (a maximum of 1 edge between two nodes, an edge can only be placed between two different nodes) and a list of X nodes that you must visit, find the shortest path that starts from node 0, visits all X nodes and returns to node 0. There's always at least one path connecting any two nodes.

限制为1＆LT; = N＆LT; = 40 0​​00/1＆LT; = X＆LT; = 15/1＆LT; = E＆LT; = 50 000

Limits are 1 <= N <= 40 000 / 1 <= X <= 15 / 1 <= E <= 50 000

下面是一个例子：

红色节点（0）应的路径的起点和终点。你必须访问所有的蓝色节点（1,2,3,4），并返回。这里的最短路径将是：

The red node ( 0 ) should be the start and finish of the path. You must visit all blue nodes (1,2,3,4) and return. The shortest path here would be :

0 - > 3 - > 4 - > 3 - > 2 - > 1 - > 0为30，总成本

0 -> 3 -> 4 -> 3 -> 2 -> 1 -> 0 with a total cost of 30

我想过使用Dijkstra算法来找到所有的X（蓝色）的节点，然后只是贪婪挑选最接近未访问过X（蓝色）节点之间的最短路径，但它不工作（自带了32，而不是30纸上谈兵）。此外，我后来发现，只是找出所有对x个节点之间的最短路径，将需要O（X * N ^ 2）时间是太大了这么多的节点。

I thought about using Dijkstra to find the shortest path between all X (blue) nodes and then just greedy picking the closest unvisited X (blue) node, but it doesn't work (comes up with 32 instead of 30 on paper). Also I later noticed that just finding the shortest path between all pairs of X nodes will take O(X*N^2) time which is too big with so much nodes.

我唯一能找到的电路是欧拉电路，只允许访问每个节点一次（我不需要这一点）。这是solveable与Dijkstra算法或是否有任何其他的算法，可以解决这个问题？

The only thing I could find for circuits was Eulerian circuit that only allows visiting each node once (and I don't need that). Is this solveable with Dijkstra or is there any other algorithm that could solve this?

推荐答案

下面是这可能是足够快的解决方案：
1）运行从每个蓝色的节点的最短路径搜索算法（这可以在O进行（X *（E日志N）））来计算成对距离。
2）建立零顶点和蓝色的顶点只（X + 1的顶点）新图。添加使用在第一步骤中计算的成对距离边缘。
3）新的图形是足够小，使用TSP动态规划解决方案（它有O（X ^ 2 * 2 ^ X）的时间复杂度）。

Here is a solution which likely to be fast enough:
1)Run shortest path search algorithm from every blue node(this can be done in O(X * (E log N))) to compute pairwise distances.
2)Build a new graph with zero vertex and blue vertices only(X + 1 vertices). Add edges using pairwise distances computed during the first step.
3)The new graph is small enough to use dynamic programming solution for TSP(it has O(X^2 * 2^X) time complexity).

这篇关于寻找最短的线路在访问至少一次x个节点图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！