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, .) }
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)
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)
--> 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)
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)
--> 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.
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:
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
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)
(mit d_a die Distanz vom Elternelement)
b.
Für alle t(a,r)
\in T(a):
(heißt für alle Kinder wiederholen)
(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.
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.
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
