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:

1. Finde das kleinste Element in der Kostenmatrix (bei Gleichheit wähle irgendeines), kreise es ein, und füge die Verbindung in die Tour ein.
2. 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).
3. 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.
4. Ist diese Tour nicht möglich, entferne die letzte Verbindung und ersetze ihre Kosten mit einer sehr großen Zahl.
5. 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