項目{a_0、..、a_N}をKグループに統合すると、どのようにして統合プロセスが最もコストがかかりませんか？

Question

私が言っていることの例を挙げておきましょう。 N=3アイテムが{ A, B, C }で、Kグループ（0 < K < N）に統合したいとします。例えば、K=2グループにそれらを統合することは、結果

{ {A, B}, {C} } 

私はアイテムYに項目Xを統合するコストを返す関数Cost(X, Y) >= 0を持っているが生じる可能性があります。例えば、Cost(A, B) = 10とCost(B, C) = 15ならば、

{ {A, B}, {C} } 

が 10コスト生産と生産

{ {A}, {B, C} } 

は15かかります。

コスト関数は可換ではありません（必ずしもCost(X, Y) = Cost(Y, X)であるとは限りません）。

私がしたいことは、Kグループへの最もコストのかからない統合アルゴリズムを見つけることです。

たとえば、のは、コストが

Cost(A, B) = 12 
Cost(B, A) = 4 
Cost(A, C) = 5 
Cost(C, A) = 11 
Cost(B, C) = 3 
Cost(C, B) = 20 

をしていると私は K=1のグループに統合したいとしましょう。最も安価なものは、 8のコストで

B -> C 
A -> C 

である。

私はこれを決定する方法の一般化を理解しようとしています。私はそれが出始めるべきだと思いますどのように

は、すべてのコスト注文することです：常に統合プロセスにおける移動の1

Cost(B, C) = 3 
Cost(B, A) = 4 
Cost(A, C) = 5 
Cost(C, A) = 11 
Cost(A, B) = 12 
Cost(C, B) = 20 

項目上記のリストの中に次のようになります。

B -> C 

ここで、私が起こる必要があるのは、リストの残りの部分を繰り返して、各連結を確認することです。

リストの次の項目はB -> Aです。 Bは既にCに移動していますので、これをスキップしてください。

次の項目はA -> Cです。 Aはまだグループに統合されていないため、これは有効な連結です。

K=1グループ{ {A, B, C} }があるので、これで完了です。

私はこのアルゴリズムを書く方法が不思議です。より具体的には

、ここではC＃のセットアップです：

FYI

using System; 
using System.Collections.Generic; 
using System.Linq; 

public class Widget 
{ 
    public int Distance { get; set; } 
    public int Weight { get; set; } 

    public static int Cost(Widget w1, Widget w2) 
    { 
     // returns the cost of consolidating w1 into w2 
     return Math.Abs(w1.Distance - w2.Distance) * w1.Weight; 
    } 
} 

public class Program 
{ 
    public static void Main() 
    { 
     var widgets = new List<Widget>() 
     { 

      new Widget() { Distance = 10, Weight = 1 }, 
      new Widget() { Distance = 20, Weight = 1 }, 
      new Widget() { Distance = 30, Weight = 1 }, 
     }; 

     var tuples = from x in widgets 
        from y in widgets 
        where !x.Equals(y) 
        select Tuple.Create(x,y); 

     var ordered = from t in tuples 
         orderby Widget.Cost(t.Item1, t.Item2) 
         select t; 

     int K = 2; 
     int sum = 0; 

     // ... What to do here??? 

     Console.WriteLine(sum); // should write 10 

    } 
} 

、これは宿題の問題か何かではありません。私は楽しみのためにやっています。

Answer 1

可能性のグラフ（ツリー）を構築することができます。各エッジは、一連の要素に対する集約関数の適用を表し、各ノードは統合される要素を格納します。例えば

、あなたが持っている{A、B、C}とコスト（A、B）= 10、コスト（C）= 15、原価（A、B、C）= 30

ことができますあなたがツリーを構築する場合

 {A,B,C} 
    10/ \ 30 
     {C} { } 
    15/  
    { } 

、あなたはそれの葉のように空のノードを検討することができ、その後、あなたは、各レベルでのコストを計算し、プリオーダーの横断を作ることができる、とする場合：次のようにツリーを構築あなたは端末に着いたときに、あなたが以前見たものよりも良い選択肢かどうかを知ることができます（グローバル変数 "best"をトランスバースルの前に非常に高い値で初期化し、端末に到達すると、最高、費用））

Answer 2

これは技術的な回答であるため、これを回答として掲示していますが、NP硬度を証明しようとしない警告として、実装するものとしてはあまり意味がありません。

連結コストを加重完全有向グラフとして解釈します。私たちは、（i）各頂点が集合に属する最大1つの弧の尾であり、（ii）方向を無視し、集合にはサイクルが含まれないように、最も軽いN-K弧の集合を探しています。条件（i）はマトロイドを定義し、条件（ii）はマトロイドを定義する。 N - K個以上の要素を持つ集合を従属（トランケーション）と宣言し、次にmatroid intersection problemの多項式時間アルゴリズムを適用することによって、新しいマロイドを得る。