Nächster Nachbar Algorithmus
Dies sind die Schritte des Algorithmus:
- Initialisieren Sie alle Eckpunkte als nicht besucht.
- Wähle einen beliebigen Scheitelpunkt aus, setze ihn als aktuellen Scheitelpunkt u. Markiere u als besucht.
- Ermitteln Sie die kürzeste Kante zwischen dem aktuellen Scheitelpunkt u und einem nicht besuchten Scheitelpunkt v.
- Setzen Sie v als aktuellen Scheitelpunkt u. Markieren Sie v wie besucht.
- Wenn alle Eckpunkte in der Domäne besucht werden, beenden Sie sie. Sonst gehe zu Schritt 3.
Die Reihenfolge der besuchten Eckpunkte ist die Ausgabe des Algorithmus.,
Der nächste Nachbaralgorithmus ist einfach zu implementieren und wird schnell ausgeführt, kann jedoch aufgrund seiner „gierigen“ Natur manchmal kürzere Routen übersehen, die mit menschlicher Einsicht leicht zu erkennen sind. Als allgemeiner Führer, wenn die letzten Etappen der Tour in der Länge mit den ersten Etappen vergleichbar sind, dann ist die Tour vernünftig; Wenn sie viel größer sind, dann ist es wahrscheinlich, dass es viel bessere Touren gibt. Eine weitere Überprüfung besteht darin, einen Algorithmus wie den Algorithmus mit der unteren Grenze zu verwenden, um abzuschätzen, ob diese Tour gut genug ist.,
Im schlimmsten Fall führt der Algorithmus zu einer Tour, die viel länger ist als die optimale Tour. Um genau zu sein, gibt es für jede Konstante r eine Instanz des Problems des reisenden Verkäufers, so dass die Länge der Tour, die vom Algorithmus des nächsten Nachbarn berechnet wird, größer ist als das r-fache der Länge der optimalen Tour. Darüber hinaus gibt es für jede Anzahl von Städten eine Zuordnung von Entfernungen zwischen den Städten, für die die Heuristik des nächsten Nachbarn die einzigartige schlechteste Tour erzeugt., (Wenn der Algorithmus auf jeden Scheitelpunkt als Startscheitelpunkt angewendet wird, ist der beste gefundene Pfad besser als mindestens N/2-1 andere Touren, wobei N die Anzahl der Scheitelpunkte ist.)
Der nächste Nachbar Algorithmus kann nicht eine machbare Tour überhaupt finden, auch wenn man existiert.