這個算法有什麼缺陷？

我試圖找出問題是什麼與實施我的算法，以合併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

這個算法有什麼缺陷？

回答

相關問題