imported>HerrAdams: +

2018-12-03T15:16:09Z

Neue Seite

[[Bild:Nearest Neighbor Heuristik.svg|mini|Nearest-Neighbor-Heuristik]]
Die '''Nearest-Neighbor-Heuristik''' („Nächster-Nachbar-Heuristik“) ist ein [[Heuristik|heuristisches]] Eröffnungsverfahren aus der [[Graphentheorie]] und wird unter anderem zur [[Approximation]] einer Lösung des [[Problem des Handlungsreisenden|Problems des Handlungsreisenden]] verwendet.

Von einem [[Knoten (Graphentheorie)|Knoten]] als Startpunkt ausgehend wird die minimalgewichtete benachbarte [[Kante (Graphentheorie)|Kante]] zum nächsten Knoten gewählt. Dieses wird sukzessive fortgesetzt, bis alle Knoten zu einem [[Hamiltonkreis|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. In der Tat können Beispiele mit beliebig weit vom Optimum entfernten Lösungen konstruiert werden.<ref>Lawler, Lenstra, Rinnooy Kan, Shmoys (Hrsg.): ''The Traveling Salesman Problem. A Guided Tour of Combinatorial Optimization''. Wiley, Chichester 1985. ISBN 0-471-90413-9, Abschnitt 5.3.1: Nearest neighbor algorithm</ref>

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]] <math>O(n^3)</math>.

== Siehe auch ==
* [[Symmetric Nearest Neighbour]]
* [[Voronoi-Diagramm]]

== Einzelnachweise ==
<references />

[[Kategorie:Algorithmus (Graphentheorie)]]

Nearest-Neighbor-Heuristik - Versionsgeschichte

imported>HerrAdams: +