这个算法的缺点是什么？

Question

我正在试图找出实现我的算法的问题所在，该算法以尽可能低的成本将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)

 }

有人能告诉我为什么不起作用吗？

Answer 1

这一定是来自：https://www.hackerrank.com/challenges/mining。

这也可以很容易地使用混合整数编程模型建模。给定数据c(i,j) (将所有黄金从i移动到j的成本)和k (整合点的数目)，我们可以写：

​

​

这里的x(i,j)是1，如果我们把东西从i移到j(否则是0)。如果我们选择y(j)=1 j作为合并点(否则为0)。该模型可以用任何MIP求解器求解。

Answer 2

您的算法是一个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，但是如果地雷的数量很大，就会变得很难解决。