这个算法有什么缺陷？

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

你的算法是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，但如果地雷数量很多，这可能会变得棘手

Answer 2

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

这也可以使用混合整数规划模型轻松建模。给定数据 c(i,j)（将所有黄金从 i 移动到 j 的成本）和 k（合并点数）我们可以写：

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

这个算法有什么缺陷？

What is the flaw in this algorithm?

c#

algorithm

performance

optimization

greedy