Der nächste Nachbaralgorithmus war einer der ersten Algorithmen, die verwendet sind, um eine Lösung des Handlungsreisender-Problems zu bestimmen. Darin, die Verkäufer-Anfänge an einer zufälligen Stadt und besucht wiederholt die nächste Stadt, bis alle besucht worden sind. Es gibt schnell eine kurze Tour, aber gewöhnlich nicht die optimale nach.

Unten ist die Anwendung des nächsten Nachbaralgorithmus auf TSP

Das sind die Schritte des Algorithmus:

1. Standplatz auf einem willkürlichen Scheitelpunkt als aktueller Scheitelpunkt.
2. finden Sie den leichtesten Rand heraus, der aktuellen Scheitelpunkt und einen verlassenen Scheitelpunkt V verbindet.
3. Satz-Strom-Scheitelpunkt zu V.
4. V Zeichen, wie besucht.
5. wenn alle Scheitelpunkte im Gebiet besucht werden, dann enden.
6. Gehen Sie zum Schritt 2.

Die Folge der besuchten Scheitelpunkte ist die Produktion des Algorithmus.

Der nächste Nachbaralgorithmus ist leicht durchzuführen und führt schnell durch, aber er kann manchmal kürzere Wege verpassen, die mit der menschlichen Scharfsinnigkeit wegen seiner "gierigen" Natur leicht bemerkt werden. Als ein allgemeiner Führer, wenn die letzten paar Stufen der Tour in der Länge mit den ersten Stufen vergleichbar sind, dann ist die Tour angemessen; wenn sie viel größer sind, dann ist es wahrscheinlich, dass es viel bessere Touren gibt. Eine andere Kontrolle soll einen Algorithmus wie der tiefer bestimmte Algorithmus verwenden, um zu schätzen, ob diese Tour gut genug ist.

Im Grenzfall läuft der Algorithmus auf eine Tour hinaus, die viel länger ist als die optimale Tour. Um für jeden unveränderlichen r genau zu sein, gibt es ein Beispiel des solchen Handelsreisender-Problems, dass die Länge der durch den nächsten Nachbaralgorithmus geschätzten Tour-Länge größer ist als r Zeiten die Länge der optimalen Tour. Außerdem für jede Zahl von Städten gibt es eine Anweisung von Entfernungen zwischen den Städten, für die der nächste heuristische Nachbar die einzigartige schlechtestmögliche Tour erzeugt.

Der nächste Nachbaralgorithmus kann keine ausführbare Tour überhaupt finden, selbst wenn man besteht.

Referenzen

Siehe auch

• K-nearest grenzen an Algorithmus

G. Gutin, A. Yeo und A. Zverovich, sollte Handelsreisender nicht gierig sein: Überlegenheitsanalyse von

Heuristik des gierigen Typs für den TSP. Getrennte Angewandte Mathematik 117 (2002), 81-86.

J. Bang-Jensen, G. Gutin und A. Yeo, Wenn der gierige

Algorithmus scheitert. Getrennte Optimierung 1 (2004), 121-127.

G. Bendall und F. Margot, gieriger Typ-Widerstand von

Kombinatorische Probleme, Getrennte Optimierung 3 (2006), 288-298.