以最低代价遍历无向带权图的k个节点(并返回原​​点)的算法

Question

我正在寻找一种算法来执行以下操作:

In an undirected, weighted graph with cycles

-find a path that visits exactly k nodes
-minimize the total cost(weight)
-each node can be visited only once
-return to the origin

edit: The start (and end) vertex is set in advance.

如果我想访问所有 节点，Travelling Salesman 算法(及其所有变体)将起作用。但就我而言，“推销员”需要在访问 k 个节点后回家。

在这种情况下，近似算法和精确算法都可以。

Answer 1

由于您的问题包括 k=n 的 TSP 作为一种特殊情况，通常它将是 NP 完全问题。对于较小的 k，您可以采用 Bellmann (1962) 的动态规划解决方案来及时解决它 O(2^k n^3)。

令 T(u,S) 为从顶点 u 开始且已访问 S 中的顶点的最短路线的长度。然后你想要最小的 T(u0,{u0}) 在所有起始顶点 u0 上。 T满足递归

T(u,S) = min { d(u,v)+T(v,S+{v}) | v in V\S }     if |S|<k
T(u,S) = d(u,u0)                                  if |S|=k

对于距离 d(u,v)。 DP 表有 2^kn 个条目，每个条目需要 O(n) 时间来计算，你必须为每个起始顶点计算它 n 次。