Nearest-Insertion-Heuristik
- Nearest-Insertion-Heuristik
-
Nearest-
Insertion-
Heuristik
Die Nearest-Insertion-Heuristik (NEARIN), ist eine Einfüge-Heuristik und damit ein heuristisches Eröffnungsverfahren aus der Graphentheorie. Es dient zur Approximation einer guten Lösung des Problem des Handlungsreisenden; Ziel ist es also, eine möglichst kurze Rundreise durch alle Knoten des Graphen zu finden
Der Algorithmus wählt in jedem Schritt den von der zuletzt eingefügten Stadt am nächsten gelegenen Knoten aus. Dieser wird so in die vorhandene Teilroute eingebaut, dass die geringste Verlängerung der bisherigen Teilroute entsteht.
Der NEARIN-Algorithmus besteht also genaugenommen aus den zwei Teilen:
- nearest selection: für die Auswahl des nächsten Knotens
- cheapest insertion: für das Einfügen in den bestehenden Kreis
Die dabei entstehende Struktur entspricht immer einer transitiven Hülle. Dieses Verfahren wird bis zum n-ten Knoten fortgesetzt und entspricht der Komplexitätsklasse O(n2).
Als Varianten dieser treten die Farthest-Insertion-Heuristik, die Cheapest-Selection-Heuristik und die Random-Insertion-Heuristik auf.
Das Ergebnis des NEARIN-Algorithmus ist in der Regel nicht optimal. Bei Vorliegen der Dreiecksungleichung kann die Länge der gefundenen Rundreise aber nicht schlechter als das Doppelte der Länge einer optimalen Rundreise sein. Die Kurzsichtigkeit des NEARIN-Algorithmus (es wird beim Aufbau der Rundreise nur in der nächsten Nachbarschaft nach weiteren einzufügenden Knoten gesucht) kann sogar zu Rundreisen mit Überkreuzungen führen, die schon deshalb nicht optimal sein können. In der Praxis werden derartige Algorithmen daher mit nach-optimierenden Algorithmen wie etwa einer 2-opt-Heuristik kombiniert.
Siehe auch
Wikimedia Foundation.
Schlagen Sie auch in anderen Wörterbüchern nach:
Nearest-Selection-Heuristik — Nearest Insertion Heuristik Die Nearest Insertion Heuristik (NEARIN), ist eine Einfüge Heuristik und damit ein heuristisches Eröffnungsverfahren aus der Graphentheorie. Es dient zur Approximation einer guten Lösung des Problem des… … Deutsch Wikipedia
Nearest-Selection Heuristik — Nearest Insertion Heuristik Die Nearest Insertion Heuristik (NEARIN), ist eine Einfüge Heuristik und damit ein heuristisches Eröffnungsverfahren aus der Graphentheorie. Es dient zur Approximation einer guten Lösung des Problem des… … Deutsch Wikipedia
Nearest Insertion Heuristic — Nearest Insertion Heuristik Die Nearest Insertion Heuristik (NEARIN), ist eine Einfüge Heuristik und damit ein heuristisches Eröffnungsverfahren aus der Graphentheorie. Es dient zur Approximation einer guten Lösung des Problem des… … Deutsch Wikipedia
Farthest-Insertion-Heuristik — Die Farthest Insertion Heuristik (entfernteste Einfügung, FARIN) ist eine Einfüge Heuristik und damit ein heuristisches Eröffnungsverfahren aus der Graphentheorie. Es dient zur Approximation einer guten Lösung des Problem des Handlungsreisenden,… … Deutsch Wikipedia
Heuristik der nächsten Einfügung — Nearest Insertion Heuristik Die Nearest Insertion Heuristik (NEARIN), ist eine Einfüge Heuristik und damit ein heuristisches Eröffnungsverfahren aus der Graphentheorie. Es dient zur Approximation einer guten Lösung des Problem des… … Deutsch Wikipedia
K-Opt-Heuristik — K Opt Heuristiken sind eine Klasse von Algorithmen zum näherungsweisen Lösen des Problems des Handlungsreisenden (PdH). Die k Opt Heuristiken gehören zu den Post Optimization Algorithmen (engl.: Nach Optimierung), die sich dadurch auszeichnen,… … Deutsch Wikipedia
k-Opt-Heuristik — K Opt Heuristiken sind eine Klasse von Algorithmen zum näherungsweisen Lösen des Problems des Handlungsreisenden (PdH). Die k Opt Heuristiken gehören zu den Post Optimization Algorithmen (engl.: Nach Optimierung), die sich dadurch auszeichnen,… … Deutsch Wikipedia
NEARIN — Nearest Insertion Heuristik Die Nearest Insertion Heuristik (NEARIN), ist eine Einfüge Heuristik und damit ein heuristisches Eröffnungsverfahren aus der Graphentheorie. Es dient zur Approximation einer guten Lösung des Problem des… … Deutsch Wikipedia
Botenproblem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein… … Deutsch Wikipedia
Euklidisches Traveling-Salesman-Problem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein… … Deutsch Wikipedia