Nearest-Neighbour-Heuristik
- Nearest-Neighbour-Heuristik
-
Nearest-Neighbor-Heuristik
Die Nearest-Neighbor-Heuristik ist ein heuristisches Eröffnungsverfahren aus der Graphentheorie und wird 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 O(n2).
Siehe auch
Wikimedia Foundation.
Schlagen Sie auch in anderen Wörterbüchern nach:
Nearest-Neighbor-Heuristik — 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 … Deutsch Wikipedia
Heuristik des nächsten Nachbarn — Nearest Neighbor Heuristik Die Nearest Neighbor Heuristik ist ein heuristisches Eröffnungsverfahren aus der Graphentheorie und wird zur Approximation einer Lösung des Problem des Handlungsreisenden verwendet. Von einem Knoten als Startpunkt… … Deutsch Wikipedia
Nächster-Nachbar-Heuristik — Nearest Neighbor Heuristik Die Nearest Neighbor Heuristik ist ein heuristisches Eröffnungsverfahren aus der Graphentheorie und wird zur Approximation einer Lösung des Problem des Handlungsreisenden verwendet. Von einem Knoten als Startpunkt… … Deutsch Wikipedia
NN — steht für: Nachnahme, eine Versand und Zahlungsart Nachname, den Familiennamen einer Person Narodne novine, das amtliche Gesetzblatt der Republik Kroatien Nearest Neighbour, ein mathematischer Lösungsalgorithmus, siehe Nearest Neighbor Heuristik… … Deutsch Wikipedia
