Traveling Salesman Variation Algorithmus

Question

Ich habe Probleme, ein widersprüchliches Beispiel für die nächste Variante des TSP-Problems zu finden.

Eingabe: G = (V, E) ungerichteter vollständiger Graph, der die Dreiecksungleichung, w: E-> R + Gewichtungsfunktion, und einen Quellknoten s enthält.

Ausgabe: Einfacher Hamilton-Zyklus, der bei s beginnt und endet, mit einem Mindestgewicht.

Algorithmus:

1. S=Empty-Set 
2. B=Sort E by weights. 
3. Initialized array M of size |V|, 
    where each cell in the array holds a counter (Initialized to 0) 
    and a list of pointers to all the edges of that vertex (In B).  

4. While |S|!=|V|-1 
    a. e(u,v)=removeHead(B). 
    b. If e does not close a cycle in S then  
      i. s=s union {e} 
     ii. Increase degree counter for u,v. 
     iii. If M[u].deg=2 then remove all e' from B s.t e'=(u,x). 
     iv. If M[v].deg=2 then remove all e' from B s.t e'=(v,x). 

5. S=S union removeHead(B). 

Dieses ähnlich geschehen wird dem Kruskal Algorithmus (Mit gewerkschafts finden DS).
Die Schritte 4.b.iii und 4.b.iv werden mit der Zeigerliste durchgeführt.

Ich bezweifle stark, dass dieser Algorithmus wahr ist, also habe ich sofort herausgefunden, warum es falsch ist. Jede Hilfe wäre willkommen.

Answer 1

Können sagen wir einen Graphen mit 4 Vertices (a, b, c, d) mit Kantengewichte wie folgt:

w_ab = 5 
w_bc = 6 
w_bd = 7 
w_ac = 8 
w_da = 11 
w_dc = 12 

      7 
     |--------------| 
    5 | 6  12 | 
a ---- b ---- c ----- d 
|______________|  | 
|  8    | 
|_____________________| 
     11 

die Dreiecksungleichung für jedes Dreieck in diesem Graphen hält.

Ihr Algorithmus wählt den Zyklus a-b-c-d-a (Kosten 34), wenn ein besserer Zyklus ist a-b-d-c-a (Kosten 32).

Answer 2

Ihr Verfahren wird möglicherweise nicht beendet. Betrachten Sie ein Diagramm mit den Knoten {1, 2, 3, 4} und den Kanten {(1,2), (1,3), (2,3), (2,4), (3,4)}. Der einzige Hamilton-Zyklus in diesem Graph ist {(1,2), (1,3), (2,4), (3,4)}. Angenommen, die niedrigste gewichtete Kante ist (2,3). Dann wird Ihre Prozedur wählen (2,3), wählen Sie eine von {(1,2), (1,3)} und beseitigen Sie die andere, wählen Sie eine von {(2,4), (3,4)} und eliminieren die andere, dann Schleife für immer.

Nuancen wie diese machen das Traveling-Salesman-Problem so schwierig.

Answer 3

Betrachten Sie den vollständigen Graphen auf 4 Ecken, wobei {a,b,c,d} die Knoten sind, vorgestellt als die im Uhrzeigersinn angeordneten Ecken eines Quadrats. Lassen Sie die Kantengewichte wie folgt aussehen.

w({a,b}) := 2, // "edges" 
w({b,c}) := 2, 
w({c,d}) := 2, 
w({d,a}) := 2, 
w({a,c}) := 1, // "diagnoals" 
w({b,d}) := M 

wo M eine ganze Zahl größer als 2 ist auf der einen Seite ist, die aus der Hamilton-Operator-Zyklus der „Ränder“ hat 8. Gewicht auf der anderen Seite der Hamilton-Operator Zyklus {a,c} enthält, die die leichteste Kante, muss {b,d} enthalten und hat Gesamtgewicht

1 + M + 2 + 2 = 5 + M > 8 

die größer als die geringstmögliche Gewicht. Insgesamt bedeutet dies, dass ein hal- monischer Minimalgewichtszyklus nicht notwendigerweise die hellste Kante enthält, die der Algorithmus in der ursprünglichen Frage gewählt hat. Ferner ist, wie M gegen unendlich geht, führt der Algorithmus willkürlich schlecht in Bezug auf die approximation ratio als

(5 + M)/8 

wächst beliebig groß.