Wie kann ich die Elemente {a_0, .., a_N} in K-Gruppen zusammenfassen, sodass der Konsolidierungsprozess am kostengünstigsten ist?

Question

Lassen Sie mich Ihnen ein Beispiel geben, was ich meine. Nehmen wir an, ich habe N=3 Artikel { A, B, C } und möchte sie in K Gruppen konsolidieren (0 < K < N). Zum Beispiel könnten sie in K=2 Gruppen Konsolidierung produzieren das Ergebnis

{ {A, B}, {C} } 

Ich habe eine Funktion Cost(X, Y) >= 0, die die Kosten zurück von Artikel Konsolidierung X in Artikel Y. Zum Beispiel, wenn Cost(A, B) = 10 und Cost(B, C) = 15 dann produzieren

{ {A, B}, {C} } 

Kosten 10 und Herstellung

{ {A}, {B, C} } 

Kosten 15.

Die Kostenfunktion ist nicht kommutativ (Es ist nicht immer wahr, dass Cost(X, Y) = Cost(Y, X)).

Was ich tun möchte, ist einen Algorithmus für die kostengünstigste Konsolidierung in K Gruppen zu finden.

Zum Beispiel, sagen wir, die Kosten sind

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

und ich möchte in K=1 Gruppen konsolidieren. Die billigste wäre

B -> C 
A -> C 

zu einem Preis von 8.

Ich versuche eine Verallgemeinerung herauszufinden, wie das zu bestimmen ist.

Wie ich denke, es anfangen sollte, ist, alle Kosten zu bestellen:

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

Der Artikel in der obigen Liste wird immer eine Eins der Bewegungen im Konsolidierungsprozess:

Nun, was ich vermute muss passieren iterieren durch den Rest der Liste und sehen, ob jede Konsolidierung.

Das nächste Element in der Liste ist B -> A. Da ich bereits B zu C verschoben habe, überspringen Sie diese.

Der nächste Artikel ist A -> C. Da A noch nicht zu einer Gruppe konsolidiert wurde, ist dies eine gültige Konsolidierung.

Jetzt sind wir fertig, da wir K=1 Gruppen haben, { {A, B, C} }.

Ich frage mich, wie man diesen Algorithmus schreibt.

konkreter werden, hier ist ein C# Setup:

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 

    } 
} 

FYI, das ist kein Problem, Hausaufgaben oder irgendetwas ist. Ich mache es zum Spaß.

Answer 1

Sie können ein Diagramm (einen Baum) von Möglichkeiten erstellen, wobei jede Kante eine Anwendung der Konsolidierungsfunktion über einen Satz von Elementen darstellt und jeder Knoten die zu konsolidierenden Elemente speichert.

Zum Beispiel haben Sie {A, B, C} und Kosten (A, B) = 10, Kosten (C) = 15, Kosten (A, B, C) = 30.

Sie können bauen einen Baum wie folgt aus:

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

wenn Sie den Baum bauen, können Sie einfach die leeren Knoten als Blätter davon betrachten und dann können Sie eine Vorbestellung Quer machen, auf jeder Ebene die Kosten der Berechnung und wenn Wenn Sie zu einem Terminal kommen, sehen Sie, ob es eine bessere Option ist als das, was Sie vorher gesehen haben (initialisieren Sie einfach eine globale Variable "best" mit einem sehr hohen Wert vor dem Transversal, und wenn Sie an einem Terminal ankommen, tun Sie am besten = min (am besten, kosten))

Answer 2

Ich poste dies als eine Antwort, weil es technisch eine Antwort ist, aber es ist weniger beabsichtigt, als etwas zu implementieren und mehr als eine Warnung, nicht zu versuchen, NP-Härte zu beweisen.

Interpretieren Sie die Konsolidierungskosten als eine gewichtete vollständige gerichtete Grafik. Wir suchen nach der leichtesten Menge von N-K-Bögen, so dass (i) jeder Scheitelpunkt der Schwanz von höchstens einem Bogen ist, der zu der Menge gehört, (ii) die Richtung ignorierend, enthält die Menge keinen Zyklus. Bedingung (i) definiert ein Matroid, und Bedingung (ii) definiert ein Matroid. Wir erhalten neue Matroide durch Deklaration der Mengen mit mehr als N - K Elementen, um abhängig zu sein (Trunkierung), dann wenden wir einen Polynomialzeitalgorithmus für die matroid intersection problem an.