c# - 这个算法有什么缺陷？

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 , 但如果地雷数量很大，这可能会变得棘手