两条边相连的最小生成树

Question

我想解决最小生成树问题的一个较难的版本。

还有N顶点。还有2M边编号为1,2，..，2M。该图连接，无向和加权。我想选择一些边缘来使图形保持连接并使总成本尽可能小。有一个限制：编号为2k的边缘和编号为2k-1的边缘是并列为，因此应该选择两者或者不应该选择两者。所以，如果我想选择边缘3，我也必须选择边缘4。

那么，连接图形的最低总成本是多少？

我的想法：

• 我们叫两个边2k和2k+1一个边缘设置。
• 如果合并两个不同的组件，我们称它为有效的。

• 如果两条边都是有效的，我们称之为边集好。

  1. 首先准确地加上m边缘集合，这些边集合在成本的增加顺序上是好的。然后以成本递增的顺序迭代所有边集，并且如果至少一个边有效，则添加集。应该从0到M迭代m。

  2. 运行一个克鲁斯卡尔算法，其中有一些变化：边缘e的成本各不相同。

     • 如果其中包含e边集是良好，成本：（边集的成本）/ 2。
     • 否则，费用是：（边集的成本）。
     • 即使成本发生变化，我也无法证明kruskal算法是否正确。

对不起，我英文不好，但我想解决这个问题。是NP-hard还是某种东西，还是有很好的解决方案？ ：D感谢你提前！

Answer 1

正如我前面推测的那样，这个问题是NP难的。我不确定不适应性;有一个非常简单的2-approximation（将每一对分成两半，保留两半的全部成本，并运行您最喜爱的香草MST算法）。

给出这个问题的算法，我们可以解决如下的NP难哈密尔顿循环问题。设G =（V，E）为Hamilton周期的实例。克隆所有其他顶点，用vi'表示vi的克隆。我们复制每一条边e = {vi，vj}（制作一个多图;我们可以用简单的图进行简化，代价是清晰度），并且假设v0是任意原始顶点，我们将一个副本与{v0，vi '}，另一个与{v0，vj'}。

没有MST可以使用少于n对，其中一个将每个克隆的顶点连接到v0。有趣的是，像这样n对的候选对的另一半可以被解释为G的定向子图，其中每个顶点具有超度1（使用克隆位中的索引作为尾部）。这个图连接了原始顶点，当且仅当它是一个汉密尔顿循环。

---

有多种方法可以应用整数编程。这是一个简单的和更复杂的。首先我们为每个i制定一个二进制变量x_i即1如果边缘对2i-1, 2i被选中。问题模板看起来像

minimize sum_i w_i x_i (drop the w_i if the problem is unweighted) 
subject to 
<connectivity> 
for all i, x_i in {0, 1}. 

当然，我已经遗漏了有趣的约束:)。实施连接的一种方法是首先解决这个没有限制的公式，然后检查解决方案。如果它连接起来，那么很好 - 我们完成了。否则，找到一组顶点S这样有S和其补间无毛边，并添加约束

sum_{i such that x_i connects S with its complement} x_i >= 1 

和重复。

另一种方法是在求解整数程序的线性松弛的求解程序中生成像这样的约束。通常MIP库有一个允许这个功能。分数问题具有分数连通性，但是，这意味着要查找最小分数来检查可行性。我希望这种方法更快，但我必须道歉，因为我没有精力来描述它的细节。

Answer 2

我不知道这是否是最好的解决办法，但我的第一个方法是搜索使用回溯：

1. 所有边缘对中，纪念那些可以无需断开图中移除。
2. 删除其中的一组并找出剩余图形的最佳解决方案。
3. 把这一对放回去，取而代之，找到最好的解决方案。

这个很有效，但是速度慢，不够好。尽管可以通过一些调整来避免不必要的分支，但也许可以挽救这种做法。

首先，仍然可以去除的边缘对是一个只有在深入时才会收缩的集合。因此，在下一次递归中，您只需检查上一组可能可移动的边对中的那些。此外，由于删除边缘对的顺序并不重要，因此您不应考虑之前已考虑过的任何边缘对。

然后，检查两个节点是否连接是昂贵的。如果缓存边缘的替代路由，则可以相对较快地检查该路由是否仍然存在。如果没有，则必须执行昂贵的支票，因为即使这条路线不存在，也可能还有其他路线。

然后，修剪一些树：可移动边缘对的集合给出了最优解的权重的下限。此外，任何现有的解决方案都给出了最佳解决方案的上限。如果一组可移动的边缘甚至没有机会找到比以前最好的解决方案更好的解决方案，那么您可以在此停止并回溯。

最后，要贪心。使用常规的贪婪算法不会给你一个最佳的解决方案，但它会迅速提高任何解决方案的标准，使修剪更有效。因此，试图按照它们的重量损失的顺序去除边缘对。