Travel-Salesman Problem - ein paar Algorithmen

Naive Version – Kürzeste Distanz in Hin und Rückrichtung

(Komplexität in average-c ase ermittelt)

1.       Für jeden Punkt bestimme Abstand zu n anderen Punkten = O(n^2)
Datenstruktur: HashMap P auf Punkte; Jeder Punkt a enthält Liste mit Tupeln T(a)
wobei gilt: t(a,b) = (b,d(a,b)), a,b \in P; T(a) = { t(a, .) }

2.       Setze Cursor p, s auf Startposition.

3.       Für einen  Punkte p in HashMap P:       (Hinrichtung)

a.       Wähle nächsten Nachbarn q \in T(p) aus
mit Bedingung: q \in P .
-->  O(k)  mit k=n..1 = |T(p)| = O(n)     (ref1)

b.      Füge Kante (p,q) zum Ergebnis erg hinzu

c.       Lösche q aus P, lösche alle t(q,x) \in T(x) mit x \in P
--> O( |P|*|T|) = O(n^2)      (ref2)

4.       Für einen  Punkte r \in P:         (Rückrichtung)

a.       Wähle nächsten Nachbarn s \in T(r)
Wenn q==s ist und P nicht leer, dann wähle nächstes naheliegendes s.
--> O(n)

b.      Füge Kante (r,s) zum Ergenis erg hinzu.

c.       Lösche s aus P, lösche alle t(s,x) \in T(x) mit x \in P
--> O(n^2)

5.       Setze p=q  und r=s und wiederhole ab 3.
Wenn p==r ist und P ist leer, dann haben wir den Weg gefunden.

Da wir (ref1) und (ref2) erst für n=|P| dann für n-1, n-2, … machen müssen ergibt sich O(n*(n+n^2)) im ersten Schritt und O((n-1)*(n+n^2)) im zweiten Schritt und so weiter.
Wir erhalten also O(n!).
Leider ist die Suche nicht optimal. Es kann zu Überkreuzungen kommen, und dieses wäre dann keine optimale Strecke. Siehe dazu folgende Abbildung: 

Abbildung 1 -  Weg mit Überkreuzung
schwarz,dünn=Hinrichtung und rot,dick=Rückrichtung

Der Fehler der Prozedur kann beliebig groß werden.

 

Naive Version – Aufspannen eines Suchbaums.

Komplexität dieses naiven Algorithmus ist O(n!) in Average-Case.

1.       Man wählt einen beliebigen Knotenpunkt a \in P als Wurzel und starte folgende rekursive Prozedur:

2.       Entferne a aus P

3.       Für alle b \in P:

a.       Füge t(a,b) = (b,d_a+d(a,b)) als Kind von a ein.
(mit d_a die Distanz vom Elternelement)

b.      Für alle t(a,r) \in T(a):
(heißt für alle Kinder wiederholen)

c.       Rufe rekursiv ab 2. auf, mit a = r                                                            --> O(n!)

4.       Durchlaufe den Baum und bestimme die Strecke (\sum_a,b{d(a,b)}).                          --> O(n!)
Speichere die Strecke als Blatt ab.
Merke dir dabei den kürzesten Weg.

Der Algorithmus hat keinen beliebig großen Fehler. Er liefert das Optimale Ergebnis. Hat aber in fast jedem Schritt O(n!).

Advanced Version – Algorithmus mit Ackermannfunktion

Komplexität dieses advanced Algorithmuses ist O(n). Es wird jedoch keine optimale Lösung gefunden. Ich schätze den Fehler auf O(Af); Af = Ackermannfunktion.

1.       Man wählt einen beliebigen Knoten a als Wurzelknoten aus und folgt folgender rekursiver Prozedur – mit l=1:

2.       Entferne a aus P

3.       Für alle b \in P:

a.       Berechne d für Af(l) Elemente x \in P: d=sum_x{d(x_i,x_i+1)} mit x_i+1 nächstes (geographisch) Element zu x_i.

b.      Speicher t(a,b) mit (b,d) (d.h. speichere die berechnete Distanz in ein Kindelement)

c.       Speichere außerdem eine Liste von Knoten, die den Weg für Af(n) Elemente beschreiben.

d.      l=l+1; Rufe rekursiv ab 2. auf mit a=b

4.       Suche über die Blätter die kleinste Distanz d. Die gespeicherten Wege beschreiben den „Round-Trip“.

Die Komplexität aus 3.a ergibt O(n) , da die nächstliegenden Af(l) Elemente berechnet werden.
Af(l) ist dabei die modifizierte Ackermannfunktion für Zweier-Potenzen. Dies ergibt Werte wie 2, 4, 8, 16, 65536.

D.h. wir spannen nur einen Baum der Größe der inversen Ackermannfunktion auf. Und die Inverse-Ackermannfunktion wird generell als maximal 5 gesehen.

Es ergibt sich also eine Komplexität von O(5*n) = O(n).

Die Suche nach dem kürzesten Weg ist dann O(n*(n-Af(1))*(n-Af(2))*(n-Af(3))*(n-Af(4))*(n-Af(5)) = O(n^5) .

Den Fehler kann man bei dieser geringen Komplexität gut einkreisen, indem man mehrmals den Algorithmus laufen lässt mit unterschiedlichen a am Start. Das löst gleichzeitig das Problem der Anfangskonfiguration bei heuristischen Verfahren.

Ich hoffe es war verständlich und hilfreich. Ich wünsche noch viel Spaß. Vielleicht gelingt es mir auch mal das Verfahren zu implementieren.

Viele Grüße, Sebastian