两条边相连的最小生成树
Minimum spanning tree with two edges tied
我想解决更难的最小生成树问题。
有N个顶点。还有 2M 条边，编号为 1, 2, .., 2M。该图是连通的、无向的和加权的。我想选择一些边缘使图形仍然连接并使总成本尽可能小。有一个限制：编号为2k的边和编号为2k-1的边是并列，所以两者都应该被选择，或者都不应被选择。所以，如果我要选择边3，我也必须选择边4。
那么，使图连通的最小总成本是多少？
我的想法：
- 我们称两条边
2k和2k+1为边集.
- 如果边合并了两个不同的组件，我们称它为 有效。
如果两条边都有效，我们称边集为好。
首先准确添加 m 个边集，这些边集按成本递增的顺序排列。然后按成本递增的顺序迭代所有边集，如果至少有一条边有效，则添加该集。 m应该从0迭代到M.
运行 具有一些变化的 kruskal 算法：边的成本 e 变化。
- 如果包含
e的边集是好，成本是：（边集的成本）/ 2.
- 否则代价为：(边集的代价).
- 即使成本发生变化，我也无法证明kruskal算法是否正确
抱歉英语不好，但我想解决这个问题。是NP-hard还是什么的，还是有什么好的解决办法？ :D 在此先感谢您！
我不确定这是否是最佳解决方案，但我的第一种方法是使用回溯进行搜索：
- 在所有边对中，标记那些可以在不断开图形连接的情况下删除的边对。
- 删除这些集合中的一个并为剩余的图找到最优解。
- 将这对放回去，然后取下另一对，找到最佳解决方案。
这可行，但速度慢且不优雅。通过一些避免不必要的分支的调整，也许可以挽救这种方法。
首先，仍然可以删除的边对是一组只有在深入时才会缩小的集合。因此，在下一次递归中，您只需要检查前一组可能可移动的边对中的那些。此外，由于删除边对的顺序无关紧要，因此您不应考虑之前已经考虑过的任何边对。
然后，检查两个节点是否连接是昂贵的。如果缓存一条边的替代路由，则可以相对快速地检查该路由是否仍然存在。如果没有，您必须 运行 昂贵的支票，因为即使那条路线不复存在，可能还有其他路线。
然后，再对树进行一些 p运行ing：您的一组可移动边对给出了最优解具有的权重的下限。此外，任何现有解决方案都会给出最优解决方案的上限。如果一组可移动边缘甚至没有机会找到比您之前最好的解决方案更好的解决方案，您可以停在那里并回溯。
最后，要贪心。使用常规的贪心算法不会为您提供最佳解决方案，但它会迅速提高任何解决方案的门槛，使 p运行ing 更有效。因此，尝试按照权重损失的顺序删除边对。
正如我之前推测的那样，这个问题是 NP-hard 问题。我不确定不可近似性；有一个非常简单的 2 近似值（将每对分成两半，保留两半的全部成本，以及 运行 你最喜欢的香草 MST 算法）。
给出这个问题的算法，我们可以解决 NP-hard 汉密尔顿循环问题，如下所示。
令 G = (V, E) 为哈密顿循环的实例。克隆所有其他顶点，用 vi' 表示 vi 的克隆。我们复制每条边 e = {vi, vj}（制作多重图；我们可以用简单的图来减少清晰度），并且让 v0 为任意原始顶点，我们将一个副本与 {v0, vi '}，另一个是 {v0, vj'}。
没有 MST 可以使用少于 n 对，一对连接每个克隆的顶点到 v0。有趣的是，像这样具有 n 对的候选对的另一半可以解释为 G 的定向子图，其中每个顶点的出度为 1（使用克隆位中的索引作为尾部）。此图连接原始顶点当且仅当它们是汉密尔顿循环时。
有多种应用整数规划的方法。这是一个简单的和一个更复杂的。首先，如果选择边对 2i-1, 2i，我们为每个 i 制定一个二进制变量 x_i，即 1。问题模板看起来像
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 库具有允许这样做的功能。然而，分数问题具有分数连通性，这意味着找到最小切割来检查可行性。我希望这种方法更快，但我必须道歉，因为我没有精力详细描述它。
我想解决更难的最小生成树问题。
有N个顶点。还有 2M 条边，编号为 1, 2, .., 2M。该图是连通的、无向的和加权的。我想选择一些边缘使图形仍然连接并使总成本尽可能小。有一个限制：编号为2k的边和编号为2k-1的边是并列，所以两者都应该被选择，或者都不应被选择。所以，如果我要选择边3，我也必须选择边4。
那么，使图连通的最小总成本是多少？
我的想法：
- 我们称两条边
2k和2k+1为边集. - 如果边合并了两个不同的组件，我们称它为 有效。
如果两条边都有效，我们称边集为好。
首先准确添加
m个边集，这些边集按成本递增的顺序排列。然后按成本递增的顺序迭代所有边集，如果至少有一条边有效，则添加该集。m应该从0迭代到M.运行 具有一些变化的 kruskal 算法：边的成本
e变化。- 如果包含
e的边集是好，成本是：（边集的成本）/ 2. - 否则代价为：(边集的代价).
- 即使成本发生变化，我也无法证明kruskal算法是否正确
- 如果包含
抱歉英语不好，但我想解决这个问题。是NP-hard还是什么的，还是有什么好的解决办法？ :D 在此先感谢您！
我不确定这是否是最佳解决方案，但我的第一种方法是使用回溯进行搜索：
- 在所有边对中，标记那些可以在不断开图形连接的情况下删除的边对。
- 删除这些集合中的一个并为剩余的图找到最优解。
- 将这对放回去，然后取下另一对，找到最佳解决方案。
这可行，但速度慢且不优雅。通过一些避免不必要的分支的调整，也许可以挽救这种方法。
首先，仍然可以删除的边对是一组只有在深入时才会缩小的集合。因此，在下一次递归中，您只需要检查前一组可能可移动的边对中的那些。此外，由于删除边对的顺序无关紧要，因此您不应考虑之前已经考虑过的任何边对。
然后，检查两个节点是否连接是昂贵的。如果缓存一条边的替代路由，则可以相对快速地检查该路由是否仍然存在。如果没有，您必须 运行 昂贵的支票，因为即使那条路线不复存在，可能还有其他路线。
然后，再对树进行一些 p运行ing：您的一组可移动边对给出了最优解具有的权重的下限。此外，任何现有解决方案都会给出最优解决方案的上限。如果一组可移动边缘甚至没有机会找到比您之前最好的解决方案更好的解决方案，您可以停在那里并回溯。
最后，要贪心。使用常规的贪心算法不会为您提供最佳解决方案，但它会迅速提高任何解决方案的门槛，使 p运行ing 更有效。因此，尝试按照权重损失的顺序删除边对。
正如我之前推测的那样，这个问题是 NP-hard 问题。我不确定不可近似性；有一个非常简单的 2 近似值（将每对分成两半，保留两半的全部成本，以及 运行 你最喜欢的香草 MST 算法）。
给出这个问题的算法，我们可以解决 NP-hard 汉密尔顿循环问题，如下所示。
令 G = (V, E) 为哈密顿循环的实例。克隆所有其他顶点，用 vi' 表示 vi 的克隆。我们复制每条边 e = {vi, vj}（制作多重图；我们可以用简单的图来减少清晰度），并且让 v0 为任意原始顶点，我们将一个副本与 {v0, vi '}，另一个是 {v0, vj'}。
没有 MST 可以使用少于 n 对，一对连接每个克隆的顶点到 v0。有趣的是，像这样具有 n 对的候选对的另一半可以解释为 G 的定向子图，其中每个顶点的出度为 1（使用克隆位中的索引作为尾部）。此图连接原始顶点当且仅当它们是汉密尔顿循环时。
有多种应用整数规划的方法。这是一个简单的和一个更复杂的。首先，如果选择边对 2i-1, 2i，我们为每个 i 制定一个二进制变量 x_i，即 1。问题模板看起来像
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 库具有允许这样做的功能。然而，分数问题具有分数连通性，这意味着找到最小切割来检查可行性。我希望这种方法更快，但我必须道歉，因为我没有精力详细描述它。