Wie finde ich die kürzesten Wegekosten unter Sonderbedingungen?

Question

Gegeben ein gewichteter gerichteter Graph G = (V, E), ein Quellknoten s, ein Zielknoten t und eine Teilmenge v ', wie findet man den kürzesten Nicht-Schleifenweg von s zum Knoten t im Graphen? Die Eckpunkte in der Teilmenge müssen im Pfad enthalten sein.

Answer 1

Dies ist eine Variante von Traveling Salesman Problem (TSP).

Sie können Ihr Problem auf eine exakte Instanz von TSP, indem Sie all-to-all kürzesten Weg in der Grafik (Floyd Warshall Algorithm), und erstellen Sie dann ein neues Diagramm verwandeln:

G'={V' U {s,t}, E'} 
V' - the "must go through" subset 
E' = { (s,v), (v,t), (u,v) | u,v in V'} (In words: all edges between two nodes in the new graphs) 

nun die Suche nach Der minimale Pfad, der alle Knoten (TSP) in G' durchläuft, ist auch der minimale Pfad, der die Kriterien erfüllt (nachdem jeder Pfad zwischen zwei Paaren zurückversetzt wurde).

Leider TSP ist NP-Complete Problem (es gibt keine bekannten Polynomialzeitalgorithmus es zu lösen, und die meisten glauben, man gar nicht existiert), und es sei denn, Ihr Satz von V' „durch die Knoten gehen müssen“ ist relativ klein (und Sie können sich eine exponentielle Laufzeit des Algorithmus leisten), Sie müssen sich auf einen "gut genug" Algorithmus festlegen, der nicht optimal ist.

---

Nebenbei bemerkt in Bezug auf „keine Loops“ - beachten Sie könnte es nicht machbar sein, zum Beispiel:

 --------- 
    |   | 
    v   | 
s -> a -> b -> c 
    | 
    | 
    t 

In diesem Beispiel ist der einzige Weg, die Kriterien zu erfüllen, ist s->a->b->c->t