无向图中覆盖指定顶点集且起止为非指定顶点的最小代价环求解

嘿，咱们先把问题捋清楚：不管是“寻找覆盖特定顶点、起止在普通顶点的最小代价环”，还是“给定子集S，找起止在V-S且覆盖所有S顶点的最小环”，本质都是同一个问题对吧？下面我给你拆解下具体的解决思路和步骤：

核心问题回顾 #

给定无向图G=(V,E)，S是V的子集（就是那些必须覆盖的特定顶点），我们要找的环得满足：

• 必须经过S里的每一个顶点；
• 环的起点和终点都得是非S的普通顶点（V-S里的节点，起点和终点可以是同一个）；
• 整个环的总代价最小。

分步解决思路 #

1. 先搞定所有顶点对的最短路径 #

首先，我们需要先算出图里任意两个顶点之间的最短路径代价。这一步是基础，因为后面我们把S顶点当作必须经过的关键点时，它们之间的最优路径直接用预计算好的最短路径就行：

• 如果图是稠密图，用Floyd-Warshall算法最方便，直接生成一个二维矩阵dist[u][v]，dist[u][v]就是u到v的最小代价；
• 如果是稀疏图，对每个顶点跑一遍Dijkstra算法效率更高，同样能得到所有顶点对的最短路径矩阵。

2. 转化为变种TSP问题 #

这个问题其实是旅行商问题（TSP）的变种——只不过我们的起点和终点被限制在了普通顶点集合V-S里，而必须遍历的“城市”是S里的所有顶点。
我们可以这样建模：

• 把S中的每个顶点看作TSP里必须访问的节点；
• 对于S里的任意两个节点u和v，它们之间的“旅行代价”就是预计算好的dist[u][v]；
• 对于普通顶点s∈V-S和S里的节点u，代价是dist[s][u]（从普通点到关键点的最短路径）；同理，S里的节点v到普通点t∈V-S的代价是dist[v][t]。

3. 计算最小环的总代价 #

接下来我们要找到满足条件的最小代价，这里分两种情况考虑：

• 情况1：起点和终点是同一个普通顶点：枚举每个普通顶点s，计算从s出发，遍历所有S顶点再回到s的总代价，也就是dist[s][u1] + 遍历S的最小路径代价 + dist[uk][s]，其中u1...uk是S顶点的最优遍历顺序；
• 情况2：起点和终点是不同的普通顶点：找到普通顶点到S的最小入代价（min{ dist[s][u] | s∈V-S, u∈S }）、S到普通顶点的最小出代价（min{ dist[v][t] | v∈S, t∈V-S }），再加上遍历所有S顶点的最小路径代价（也就是S集合的TSP路径，起点是任意S顶点，终点是任意S顶点）。

然后取这两种情况里的最小值，就是我们要找的最小代价环啦。

关键细节提醒 #

• 如果S的规模不大（比如|S|≤12），用动态规划解决S的TSP问题很高效：定义状态dp[mask][u]，其中mask是二进制位表示的S顶点访问状态，u是当前所在的S顶点，dp[mask][u]表示到达这个状态的最小代价；
• 如果图里有负权边，但没有负权环，Floyd-Warshall算法依然能用；但如果存在负权环，那这个问题可能没有有限解，得先检测负权环；
• 如果V-S是空集（也就是所有顶点都是特定顶点），那问题就简化成找覆盖所有顶点的最小环，直接用标准TSP的最优回路（起点终点相同）就行。

内容的提问来源于stack exchange，提问作者user3911393