在包含一组节点的图中搜索最小循环

Question

如果我有一个无向加权图 G = (V, e) 和一组节点 P，我如何找到包含 P 中所有节点的最小循环？

我有一个大图 G 和一组基于用户输入的节点 P。获得用户输入后，我想在 G 上找到包含 P 中所有节点的最短路径。

有一个常量 starting/ending 节点，它将始终位于 P[0]。

我认为这可能是旅行商问题的一些修改，它找到包括所有顶点的最短路径。

Answer 1

我想你指的是minimum spanning tree. It calculates the minimum total edge weight in order to connect every vertex in the graph. There are two main algorithms to implement a MST (minimum spanning tree. One is Prim's Algorithm, and one is Kruskal's algorithm。我建议您研究这两种解决方案，但是在您的问题中您提到您有一个初始起始顶点 P[0]，在这种情况下我建议您研究 Prim 的算法。

Answer 2

我能想到两个命题，一个是基于 可能 给你 a 路径的贪心算法，另一个 应该 给你最好的路径（如果存在的话）。

贪心解法

1. 设置起始节点p_start = P[0]
2. 使用节点 v 和边 e
设置图 G(v,e)
3. 从起始节点p_start，运行 Dijkstra's algorithm直到到达集合P中的所有节点
4. 保存从 p_start 到集合 p 中任何其他节点的所有可能路径中的最短路径。让我们记下最短路径是从 p_start 到节点 P[ii]
的路径
5. 从集合 P 中移除 P[ii] 并从 e
中移除边
6. Return 到第 3 步。直到集合 p 为空

解释

正如我所说，这个解决方案是贪心的，因为它保存了从起点到集合 P 中任何候选节点的最短路径。即使可能存在答案，此解决方案也可能不会返回答案，因为该解决方案在某些点可能需要更长的路径才能成功完成循环。

解决方案建议

现在我们奠定了基础，我们可以转向我建议的解决方案。这个问题可以看一个Self-avoiding walk problem. I have written an implementation for a solution to finding all possible paths in the self avoiding problem ，但是这个比较有问题。对于少量节点，您可以运行附件中的解决方案，即计算所有可能的路径，然后从经过P中所有节点的所有路径中选择最佳路径。然而，对于大图，我建议进行以下调整：

1. 设置起始节点p_start = P[0]，从集合中移除P[0]

2. 设置图G(v,e)节点v和边e

3. 将起始路径设置为空列表path = []

4. 将state_stack设置为空列表[]

5. 从p_start、运行 Dijkstra算法到集合中的其余节点'P'

6. 长度为ii('P'):

   6.1。注意 e_ii 是选择连接 p_start 到 P[ii]

   的边

   6.2。注意 P_ii 是没有 P[ii]

   的集合 P

   6.3。创建一个新的元组 (P[ii], G(v, e\e_ii), P_ii, path + e_ii) 并添加到 state_stack（新的起始状态，新的图表，新的必须通过的集合，到目前为止所采取的路径）

7. 从 state_line 弹出另一个状态：new_state = state_stack.pop()

8. 设置p_start = new_state[0]; G = new_state[1]; P = new_state[2]

9. 回到第5步，直到state_stack为空

10. 选择最好的累积路径

解释

此过程将使用 Dijkstra 计算最短路径。该路径将被保存，并且从每个目的地，将计算到所有剩余目的地等的新路径。该算法将按初始集 P 的大小阶乘增长，但 return 最好解决方案，如果存在这样的解决方案，因为它在选择最佳排列和 return 之前计算集合 P 中所有可能的访问排列。