这个算法有什么缺陷？

我试图找出问题是什么与实施我的算法，以合并N黄金矿井K尽可能最小的成本，其中从一个矿到另一个金合并成本等于距离在他们之间乘以源矿中黄金的重量。我的算法这个算法有什么缺陷？

例子：

比方说，我们有以下N=3矿山

A = { Distance = 10, Gold = 2 } 
B = { Distance = 12, Gold = 1 } 
C = { Distance = 15, Gold = 1 }

，我们希望金合并为K=1地雷。第一次合并黄金的成本如下。

Cost(B,A) = |12 - 10| * 1 = 2 
Cost(B,C) = |12 - 15| * 1 = 3 
Cost(C,B) = |15 - 12| * 1 = 3 
Cost(A,B) = |10 - 12| * 2 = 4 
Cost(C,A) = |15 - 10| * 1 = 5 
Cost(A,C) = |10 - 15| * 2 = 10

因此，让我们第一次盘整是黄金摆脱B到A。

我们的总成本是2，我们的矿山看起来像

A = { Distance = 10, Gold = 3 } 
C = { Distance = 15, Gold = 1 }

我们为了成本

Cost(C,A) = |15 - 10| * 1 = 5 
Cost(A,C) = |10 - 15| * 3 = 15

（注意我们是如何从我们的任何费用，涉及B列表中删除，因为它现在已经不存在了。）

我们的下一个合并也是有序成本列表中的第一个元素。

作出整固，折叠移动从C到A后，我们的总成本目前是2 + 5 = 7，我们的矿山

A = { Distance = 10, Gold = 4 }

由于该组的大小为K=1的，我们就大功告成了。

泛化伪代码：

Mines = list of mines, 
K = desired number mines, 
sum = 0 
while(Mines.Count != K) 
{ 
    Find m1,m2 in Mines such that Cost(m1,m2) is minimized 

    sum += Cost(m1,m2) 

    m2.Gold += m1.Gold 

    Mines.Remove(m1) 

}

有人能告诉我为什么不行？

来源

2016-08-03 user6048670

相关（后续？）：http://stackoverflow.com/questions/38711479/where-is-the-flaw-in-my-algorithm-for-consolidating-gold-mines – Thilo

这必须从：https://www.hackerrank.com/challenges/mining。

这也可以使用混合整数编程模型轻松建模。鉴于数据c(i,j)（从我移动所有的黄金j的成本）和k（数量的集合点），我们可以这样写：

这里x(i,j)是1，如果我们从我搬东西到j（0除此以外）。 y(j)=1如果我们选择矿井j作为合并点（否则为0）。这个模型可以用任何MIP解算器解决。

来源

2016-08-03 06:23:28

你的算法是一个greedy algorithm。制定本地最佳选择并不总是最好的。

在这里你的算法没有找到最佳的解决方案

A = { Distance = 10, Gold = 1 } 
B = { Distance = 0, Gold = 10 } 
C = { Distance = 15, Gold = 2 }

在正确的解决方案的一个直观的可能是将移动A和C到B的情况下，作为B有大量的黄金，其将很难移动。但是，您的算法首先将本地最优移动到A到C。然后，它必须C遵循B为5 + 45 = 50

更好的解决方案总成本是移动A到B然后C到B，为10 + 30 = 40

解决这类问题的成本并不容易，一种方法是执行brute-force search，但是如果地雷的数量很大，这可能会变得棘手。

来源

2016-08-03 04:14:50

这个算法有什么缺陷？

回答

相关问题