Heuristik des nächsten Nachbarn
- 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 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:
Dijkstra-Algorithmus — Animation des Dijkstra Algorithmus Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) ist ein Algorithmus aus der Klasse der Greedy Algorithmen und löst das Problem der kürzesten Pfade für einen gegebenen Startknoten. Er… … Deutsch Wikipedia
D*-Algorithmus — Der D* Algorithmus ist eine Erweiterung des A* Algorithmus und somit ein direkter „Nachfahre“ des Dijkstra Algorithmus. Sowohl A* als auch der Dijkstra Algorithmus sind in ihrer Grundform unflexibel und können auf Veränderungen im Graphen während … Deutsch Wikipedia
Prolog (Programmiersprache) — Prolog Paradigmen: logisch, deklarativ, oft auch constraintbasiert Erscheinungsjahr: 1972 Designer: Alain Colmerauer Entwickler: Philippe Roussell … Deutsch Wikipedia
Simulated Annealing — Die simulierte Abkühlung (Englisch simulated annealing) ist ein heuristisches Optimierungsverfahren des Operations Research. Das Verfahren wird zum Auffinden einer approximativen Lösung von Optimierungsproblemen eingesetzt, die durch ihre hohe… … Deutsch Wikipedia
Simulated annealing — Die simulierte Abkühlung (Englisch simulated annealing) ist ein heuristisches Optimierungsverfahren des Operations Research. Das Verfahren wird zum Auffinden einer approximativen Lösung von Optimierungsproblemen eingesetzt, die durch ihre hohe… … Deutsch Wikipedia
Simuliertes Ausglühen — Die simulierte Abkühlung (Englisch simulated annealing) ist ein heuristisches Optimierungsverfahren des Operations Research. Das Verfahren wird zum Auffinden einer approximativen Lösung von Optimierungsproblemen eingesetzt, die durch ihre hohe… … Deutsch Wikipedia
Clusteranalyse — Dieser Artikel wurde aufgrund von inhaltlichen Mängeln auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf… … Deutsch Wikipedia
Hierarchische Clusteranalyse — Als Hierarchische Clusteranalyse bezeichnet man eine bestimmte Familie von distanzbasierten Verfahren zur Clusteranalyse (Strukturentdeckung in Datenbeständen). Cluster bestehen hierbei aus Objekten, die zueinander eine geringere Distanz (oder… … Deutsch Wikipedia
