logo标签列表

最小化图中的损失成本

algorithmgraphmultiway-tree
8
我们有一个带有N个节点（编号从0到N-1）和恰好（N-1）条双向边的图G（V，E）。
图中每条边都有正成本C（u，v）（边权）。
整个图形是这样的，即任何一对节点之间都有唯一的路径。
我们还给出了放置炸弹的节点号列表L。
我们的目标是损坏/删除图中的边，使得在损坏/删除图中的边后，炸弹之间没有连接 -
也就是说，在损坏后，任何两个炸弹之间都没有路径。
破坏边（u，v）的成本=边权（u，v）。
因此，我们必须破坏那些边，使得总破坏成本最小。
示例：
Total Nodes=N=5 
Total Bomb=Size of List L=3

List L={2,4,0}//Thats is at node number 2,4 and 0 bomb is placed...

Total Edges =N-1=4 edges are::

u v Edge-Weight

2 1 8

1 0 5

2 4 5

1 3 4



In this case the answer is ::
Total Damaging cost =(Edge Weight (2,4) + Edge Weight(0,1))
           =5+5=10.

So when we remove the edge connecting node (2,4),
and the edge connecting node (0,1) ,there is no connection left 
between any pair of machines in List {2,4,0};

Note any other,combinations of edges(that  we damaged ) to achieve the
target goal ,needs more than 10 unit cost.

enter image description here

Constraints::
N(ie. Number of Nodes) <= 100,000
ListSize |L|(ie. Number of Bombs) <= N
1 <=Edge cost(u,v) <= 1000,000

我做了什么？

到目前为止，我还没有找到任何有效的方法 :(。

此外，由于节点数为N，边数正好为N-1，整个图形是这样的，即任意一对节点之间都有唯一的路径，我得出结论这个图形是一棵树。

我尝试修改Kruskal算法，但也没有帮助我。

谢谢！

我认为在树中采用贪心算法（删除每条路径中的最低顶点）可能有机会，但我还不确定：\ 另外：您认为什么是高效的方法？ - amit
@amit，到目前为止，我还没有找到任何有效的方法来解决这个问题。约束条件是节点数=100,000，也就是说总边数=100,000-1。因此，O(n log n)算法将是方便和高效的。 - Ritesh Kumar Gupta
@所有人：将约束条件作为编辑添加。 - Ritesh Kumar Gupta
如果图是完全连接的，则它是一棵树，但否则它可能是普通图。 - Saeed Amiri
6个回答
4
我认为修改版的Kruskal算法适用于这里。
构造图G'=(V', E')，其中V'=V，E'={}。 按照边的代价从大到小排序。 对于每一条边，在其不连接两个都有炸弹的组件的情况下将其加入E'中。 结果是E-E'中代价之和。
编辑：
在你的例子上运行此算法。
一开始，我们的边集为空{}，并且按非升序排序[(1, 2), (0, 1), (2, 4), (1, 3)]。
因此，一开始，我们的图由5个不连通的组件组成。
(1, 2)的代价为8，只有连接一个有炸弹的组件，所以我们将其添加到E'中。E'={(1, 2)}，我们有4个组件。
下一个最高代价的边是(0, 1)，代价为5。但是两个组件都有炸弹，所以不添加此边。
接下来是(2, 4)。这也连接到有炸弹的组件，所以我们跳过它。
最后，最低代价的边是(1, 3)。由于它的一个组件（仅包含节点3）没有炸弹，所以我们将其添加到E'中。
这给我们E'={(1,2), (1, 3)}。
我的想法是我们尝试先添加代价更高的边，然后再添加代价更低的边-这确保在原始节点中带有炸弹的任何路径中，除了最低代价之外都会被添加。
MaK，你能否举个例子吗？我认为这种方法不起作用，因为“整个图都是这样的，任何一对节点之间都有唯一的路径”，所以总共只有一个连通组件。如果我错了，请纠正我，如果你能以示例输入为例说明你的方法，那将更容易理解。 - Ritesh Kumar Gupta
2
我认为这可以在线性时间内完成。
将树的根定在某个顶点上，然后从下往上遍历。
从一些叶子开始。如果没有炸弹，剪掉叶子并继续移动。 如果有炸弹，则必须在通往该叶子的路径上剪掉一条边。向上传递关于最便宜的边到达该叶子的信息。
然后当您在内部顶点时，有以下可能性： 如果顶点中有炸弹和下面有一些炸弹，请剪掉到所有炸弹的最便宜的路径。 如果没有炸弹，只有一个炸弹在下面，请传递有关最便宜路径的信息。 如果下面有更多的炸弹，请剪掉除具有最昂贵路径的炸弹之外的每一个炸弹。
我之前也有同样的想法，但一直无法得出最终算法，不过你提出记录等价于一个炸弹的子树的想法应该可以解决这个问题。 - unkulunkulu
1

这是我的假设：

图形G是一棵树。因此，任意两个节点之间只有一条路径。

假设有L个红色（炸弹）节点和V-L个白色（非炸弹）节点。解决方案需要将G分成L个子树的森林。这需要删除至少L-1条边。

每个被删除的边都必须在两个红色节点之间的路径上。

A. 修剪树G以删除所有未参与两个红色节点之间路径的边缘。

  1. 从考虑中删除白色叶节点（和相应的边缘）。
  2. 重复#1，直到修改后的图中没有白色叶节点为止。

B. 在（A）之后，图中剩余的所有边缘都是两个红色节点之间路径的边缘。

选择此树中最小权重的边缘。这将导致两个子树，每个子树都包含至少一个红色节点。

C. 如果B中包含多个红节点，则返回步骤A以处理每个子树。

这是O(V log V)（其中|E|=|V|-1）。

0
我认为以下建议应该有效：
  • 1) 从一个炸弹开始，例如你的例子中从0开始。
  • 2) 创建所有相邻节点之间的路径。因此，获取所有关系并以它们开始一条路径。在您的示例中，将启动一条路径：0 -> 1。
  • 3) 如果在路径上遇到另一个炸弹，则删除成本最低的边缘。在示例中，我们没有遇到炸弹，因此我们继续进行第2步。
  • 3A) 尚未在任何路径上发现炸弹。继续执行第2步，并使用新的相邻节点扩展路径。在您的情况下，将创建一个新路径：1 -> 3。现有路径将被扩展：0 -> 1 -> 2
  • 3B) 在路径上发现了炸弹。取出包含炸弹的路径，并删除成本最低的边缘。在您的示例中，路径0 -> 1 -> 2包含炸弹（2）。因此，我们删除成本为5的关系。从“待办事项”中删除该路径，并继续在最后到达的节点（2和3）上执行第2步。
最终，您应该恰好遍历每个节点一次。 如果我没错的话，复杂度应该是约为O(n log n)。
0

http://www.cs.ust.hk/mjg_lib/Classes/COMP572_Fall06/Notes/Tree_Multicut.ps

这里有一个算法的描述。

Google HTML版本的后续文件。

=========================================

http://dspace.mit.edu/bitstream/handle/1721.1/5394/OR-308-95.pdf?sequence=1

当ce = 1 Ve E E且G具有欧拉性时，Lovdsz [12]和Cherkasskij [3]表明多路切割问题并不仅限于k = 2是可以用多项式求解的。Erdos和Sz6kely [8]表明，当底层图G是树时，多路切割问题的推广也可以用多项式求解。Dalhaus等人[7]表明，对于平面图上固定k值，该问题也是可以用多项式求解的。 我昨晚编写了一个基于贪心算法的简单解决方案，其中包括删除不在两个红色（终端）节点之间路径上的节点，然后选择最小权重节点，然后在子树上重复此过程。但进一步阅读后我删除了这个方案，因为该问题是NP问题。但是这个参考资料表明还有一个多项式解决方案...
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接