このアルゴリズムの欠陥は何ですか？

Question

私は、Kに金のN鉱山を最小コストで統合するアルゴリズムを実装することで問題がどのようなものか把握しようとしています。金を1つの鉱山から他の鉱山へと金銭を交換するコストは距離彼らの間に源鉱山の金の重量を倍にする。私のアルゴリズムの

例：

のは、我々は以下の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 

それではAにBから金を移動するように私たちの最初の統合を作ってみよう。

当社の総コストは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あり、そのグループが大きK=1であるので、私たちの鉱山が

A = { Distance = 10, Gold = 4 } 

あり、我々は完了です。

汎化擬似コード：それが動作しない理由を

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（連結ポイント数）：私たちはJ（0に私から物事を移動した場合

ここx(i,j)が1でありますさもないと）。私はmine jを連結点として選択した場合は0、そうでない場合は0を選択します。このモデルは、任意のMIPソルバで解くことができます。

Answer 2

あなたのアルゴリズムはgreedy algorithmです。ローカル最適な選択肢を作ることは、必ずしも最良ではありません。金をたくさん持っているBとしてここ

は、あなたがアルゴリズム正解で直感的な推測が Bに Aと Cを移動するだろう

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

最善の解決策を見つけられない状況であります動かすのは難しいでしょう。しかし、あなたのアルゴリズムは、最初にをAののローカル最適化をCに移動させます。それは、その後、5 + 45 = 50

より良いソリューションの総コストのためBにCに従わなければならない、常にこの種の問題を解決する10 + 30 = 40

のコストのために、ABに続いCBに移動することは容易ではないです1つの方法はbrute-force searchを実行することですが、鉱山の数が多い場合は難しくなります