Nearest-Neighbor-Heuristik
 |
Dieser Artikel ist nicht hinreichend mit Belegen (bspw. Einzelnachweisen) ausgestattet. Die fraglichen Angaben werden daher möglicherweise demnächst entfernt. Hilf bitte der Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst. Näheres ist eventuell auf der Diskussionsseite oder in der Versionsgeschichte angegeben. Bitte entferne zuletzt diese Warnmarkierung. |
Die Nearest-Neighbor-Heuristik ist ein heuristisches Eröffnungsverfahren aus der Graphentheorie und wird unter Anderem zur Approximation einer Lösung des Problem des Handlungsreisenden verwendet.
Von einem Knoten als Startpunkt ausgehend wird die minimalgewichtete benachbarte Kante zum nächsten Knoten gewählt. Dieses wird sukzessive fortgesetzt, bis alle Knoten zu einem Hamiltonschen Kreis zusammengefasst wurden. Im Allgemeinen liefert dieser Greedy-Algorithmus nicht die beste Lösung. Dies liegt hauptsächlich daran, dass der Startknoten und der Endknoten zu keinem Zeitpunkt berücksichtigt werden und anstatt dessen eine mögliche große Distanz zwischen ihnen in Kauf genommen wird.
Indem iterativ jeder einzelne Knoten des Graphen jeweils einmal als Startknoten zur Ermittlung der Gewichtung des jeweilig entstehenden Pfades gewählt wird und diese abschließend miteinander verglichen werden, wird das Verfahren besser.
Jedoch entspricht diese All Nearest-Neighbor-Heuristik bereits der Komplexitätsklasse 
.
