Das Pfadberechnung bei erzwungenen eindeutigen Knotenattributen - Welchen Algorithmus sollte ich verwenden?

Question

Aktualisierung 2011-12-28: Hier ist ein Blog-Beitrag mit einer weniger vagen Beschreibung des Problems, das ich lösen wollte, meiner Arbeit daran und meiner aktuellen Lösung: Beobachten, wie jedes MLB-Team ein Spiel spielt

---

Ich versuche, eine Art eigenartige Pfadfindungs-Herausforderung zu lösen. Ich habe einen azyklischen gerichteten Graphen, und jede Kante hat einen Distanzwert. Und ich möchte den kürzesten Weg finden. Einfach, oder? Nun, es gibt ein paar Gründe, warum ich nicht einfach Dijkstras oder A* verwenden kann.

1. Es ist mir überhaupt nicht wichtig, was der Startknoten meines Pfades ist, noch der Endknoten. Ich benötige einen Pfad, der genau 10 Knoten enthält. Aber:
2. Jeder Knoten hat ein Attribut, sagen wir mal, es ist die Farbe. Jeder Knoten hat eine von 20 verschiedenen möglichen Farben.
3. Der Pfad, den ich zu finden versuche, ist der kürzeste Pfad mit genau 10 Knoten, wobei jeder Knoten eine andere Farbe hat. Ich möchte nicht, dass irgendein Knoten in meinem Pfad die gleiche Farbe wie ein anderer Knoten hat.
4. Es wäre schön, meinen Pfad dazu zwingen zu können, einen Wert für eines der Attribute zu haben ("mindestens ein Knoten muss blau sein", zum Beispiel), aber das ist nicht wirklich notwendig.

Das hier ist ein vereinfachtes Beispiel. Mein vollständiger Datensatz hat tatsächlich drei verschiedene Attribute für jeden Knoten, die alle einzigartig sein müssen, und ich habe 2k+ Knoten, von denen jeder durchschnittlich 35 ausgehende Kanten hat. Da ein perfekter "kürzester Pfad" exponential oder faktoriell sein kann, ist eine erschöpfende Suche wirklich keine Option. Wonach ich wirklich suche, ist eine Approximation eines "guten Pfades", der das Kriterium unter #3 erfüllt.

Kann mir jemand einen Algorithmus nennen, den ich verwenden könnte (auch modifiziert)?

---

Einige Statistiken zu meinem vollständigen Datensatz:

• Gesamte Knoten: 2430
• Gesamte Kanten: 86524
• Knoten ohne eingehende Kanten: 19
• Knoten ohne ausgehende Kanten: 32
• Die meisten ausgehenden Kanten: 42
• Durchschnittliche Kanten pro Knoten: 35,6 (in beide Richtungen)
• Aufgrund der Natur der Daten weiß ich, dass der Graph azyklisch ist
• Und im vollständigen Datensatz suche ich nach einem Pfad der Länge 15, nicht 10

Answer 1

Das Problem kann durch dynamische Programmierung wie folgt gelöst werden. Beginnen wir mit der formalen Definition seiner Lösung.

Gegeben ein DAG G = (V, E), sei C die Menge der Farben der bisher besuchten Knoten und sei w[i, j] bzw. c[i] jeweils das Gewicht (Entfernung) der Kante (i, j) und die Farbe eines Knotens i. Beachten Sie, dass w[i, j] null ist, wenn die Kante (i, j) nicht zu E gehört. Definieren wir nun die Entfernung d für den Weg von Knoten i zu Knoten j unter Berücksichtigung von C als

d[i, j, C] = w[i, j], wenn i nicht gleich j ist und c[j] nicht zu C gehört

           = 0, wenn i = j

           = unendlich, wenn i nicht gleich j ist und c[j] zu C gehört

Wir sind jetzt bereit, unsere Teilprobleme wie folgt zu definieren:

A[i, j, k, C] = der kürzeste Weg von i nach j, der genau k Kanten nutzt und die Farben in C respektiert, so dass keine zwei Knoten im Pfad mit derselben Farbe (einer der Farben in C) gefärbt sind

Sei m die maximale Anzahl von Kanten im Pfad und nehmen wir an, dass die Knoten mit 1, 2, ..., n bezeichnet sind. Sei P[i,j,k] der Vorgängerknoten von j im kürzesten Pfad, der den Einschränkungen von i nach j genügt. Der folgende Algorithmus löst das Problem.

für k = 1 bis m
  für i = 1 bis n
    für j = 1 bis n
      A[i,j,k,C] = Minimum über x gehörend zu V {d[i,x,C] + A[x,j,k-1,C Vereinigung c[x]]}
      P[i,j,k] = der Knoten x, der A[i,j,k,C] in der vorhergehenden Aussage minimiert hat

Setzen Sie die Anfangsbedingungen wie folgt:

A[i,j,k,C] = 0 für k = 0
A[i,j,k,C] = 0, wenn i gleich j ist
A[i,j,k,C] = unendlich in allen anderen Fällen

Die gesamte Rechenkomplexität des Algorithmus beträgt O(m n^3); unter Berücksichtigung, dass in Ihrem speziellen Fall m = 14 ist (da Sie genau 15 Knoten wollen), folgt, dass m = O(1) ist, sodass die Komplexität tatsächlich O(n^3) beträgt. Verwenden Sie zur Darstellung der Menge C eine Hashtabelle, sodass das Einfügen und die Mitgliedschaftsprüfung durchschnittlich O(1) benötigen. Beachten Sie, dass in dem Algorithmus die Operation C Vereinigung c[x] tatsächlich eine Einfügeoperation ist, bei der Sie die Farbe des Knotens x in die Hashtabelle für C hinzufügen. Da Sie jedoch nur ein Element einfügen, führt die Mengenvereinigungsoperation zu genau demselben Ergebnis (wenn die Farbe nicht in der Menge enthalten ist, wird sie hinzugefügt; andernfalls wird sie einfach verworfen und die Menge ändert sich nicht). Verwenden Sie schließlich zur Darstellung des DAG die Adjazenzmatrix.

Wenn der Algorithmus abgeschlossen ist, finden Sie den kürzesten Pfad zwischen allen möglichen Knoten i und j, indem Sie einfach das Minimum der Werte A[i,j,m,C] finden. Beachten Sie, dass, wenn dieser Wert unendlich ist, kein gültiger kürzester Pfad existiert. Wenn ein gültiger kürzester Pfad existiert, können Sie ihn tatsächlich durch Verwendung der Werte P[i,j,k] und der Rückverfolgung der Vorgängerknoten bestimmen. Beginnend beispielsweise mit a = P[i,j,m] ist die letzte Kante auf dem kürzesten Pfad (a,j), die vorherige Kante wird durch b = P[i,a,m-1](b,a) und so weiter.