
Das Verfahren nach der Methode Nearest Neighbor ist ein Verfahren
zum Lösen des TSP. Der Vorteil dieses Verfahrens liegt, darin, daß
man es schnell und einfach mit Papier und Bleistift durchführen kann,
allerdings nur für eine geringe Anzahl von Knoten.
Der Nachteile sind Unübersichtlichkeit und daß die Lösung für gewönlich
weiter vom Optimum entfernt ist, als bei anderen Verfahren.
Der Lösungsalgorithmus lautet wie folgt:
- Finde das kleinste Element in der Kostenmatrix (bei Gleichheit
wähle irgendeines), kreise es ein, und füge die Verbindung in die
Tour ein.
- Ist c(p,q) das eingekreiste Element, ersetze alle Elemente
der p-ten Zeile und der q-ten Spalte, sowie
c(q,p) durch eine sehr große Zahl (z.B. 1000).
- Finde das kleinste, nicht eingekreiste Element in der verbleibenden
Kostenmatrix. Füge diese Verbindung vorläufig in die Tour ein. Wenn
die resultierende Tour möglich ist, kreise die Kosten ein und mache
weiter mit Schritt 5.
- Ist diese Tour nicht möglich, entferne die letzte Verbindung und
ersetze ihre Kosten mit einer sehr großen Zahl.
- Ist die Tour fertig? Wenn ja, dann ist sie fast optimal, wenn nicht,
dann mache wieder weiter mit Schritt 2.
Hier gibt es diemal keine Übungsaufgabe. Diese folgt dafür auf der
nächsten Seite.
Copyright 1996 by Matthias Hoffmann (TFH Berlin)
letzte Änderung: 1-11-1996