Angenommen, wir haben einen DIRECTED , GEWICHTET und CYCLIC .
Angenommen, wir interessieren uns nur für Pfade mit einem Gesamtgewicht von weniger als MAX_WEIGHT
Was ist der am besten geeignete (oder ein beliebiger) Algorithmus, um die Anzahl von verschiedenen Pfaden zwischen zwei Knoten A und B zu finden, die ein Gesamtgewicht von weniger als MAX_WEIGHT haben?
PS: Es ist nicht meine Hausaufgabe. Nur persönliches, nicht-kommerzielles Projekt.
Wenn die Anzahl der Knoten und MAX_WEIGHT nicht zu groß ist (und alle Gewichtungen sind ganze Zahlen), können Sie die dynamische Programmierung verwenden
initialisiere auf 0, außer num_of_paths[0][start] = 1; .
Lösung ist die Summe von num_of_paths[w][target], 0 <= w <= MAX_WEIGHT .
Einfache Rekursion. Sie haben es in exponentieller Zeit. Offensichtlich sind keine Null-Gewichts-Zyklen erlaubt.
Funktion noe (Knoten N, Grenzgewicht W)
nein. von Pfad ist Null, wenn alle ausgehenden Kanten Gewicht & gt; W
sonst nicht. des Pfades ist die Summe der Pfadnummern, die durch die Summe (noe (C1, W-W1), noe (C2, W-W2), ... noe (Cn, W-Wn)) erhalten werden, wobei C1 ... Cn die Knoten, die mit N verbunden sind, für die W-Wi nicht negativ ist, wobei Wi das Gewicht der Verbindungskante ist, in Ihrer bevorzugten Sprache geschrieben.
Es sollte eine effizientere Lösung nach dem Dijkstra-Algorithmus geben, aber ich denke, das reicht für Hausaufgaben.
Ihr Problem ist ein allgemeinerer Fall von K-Disjoint Pfad In gerichteten planaren Graphen , mit nicht feste K.
K disjunkte Pfade Problem für gerichtete planare Graphen ist wie folgt:
gegeben : ein gerichteter planarer Graph G = (V; E) und k Paare (r1; s1); ....; (r k = k k) von Eckpunkten von G:
finde : k paarweise vertex-disjunkte gerichtete Pfade P 1 ; ...; P k in G, wobei P i von r i nach s i (i = 1; ...) verläuft. ..; k).
Im k-disjoint-Pfad können Sie einen Bogen von allen s i zu B zeichnen, und auch von A zu allen r i . So erstellen Sie den Graphen G ' von G.
Wenn Sie nun Ihr Problem in G 'in P lösen können, können Sie den k-disjunkten Pfad in G lösen, also P = NP.
Aber wenn Sie das verlinkte Papier lesen, gibt es eine Idee für ein allgemeines Diagramm (Lösen des k-disjunkten Pfads mit festem k) und Sie können es verwenden, um eine gute Annäherung zu erreichen.
Es gibt auch einen komplizierteren Algorithmus, der dieses Problem in P (für festes k) in allgemeinen Graphen löst. aber in allem ist es nicht einfach (es ist von Seymour).
Ihre beste Wahl ist derzeit Brute-Force-Algorithmen.
Bearbeiten: Da MAXWEIGHT unabhängig von Ihrer Eingabegröße (Ihrer Diagrammgröße) ist, hat sie keine Auswirkungen auf dieses Problem. Auch weil NP-Hard für ungerichtete ungewichtete Grafiken gilt, können Sie dennoch einfach schließen es ist NP-schwer.
Tags und Links algorithm graph-algorithm graph path-finding