Farthest-Insertion-Heuristik
- 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, bei dem der kürzeste (billigste) Hamiltonkreis auf einem vollständigen Graphen gesucht wird.
Der Algorithmus startet mit einer Teilroute, die aus einem einzigen, zufällig gewählten Knoten besteht. Anschließend werden iterativ die verbleibenden Knoten hinzugefügt bis die Tour alle Knoten des Graphen enthält. In jedem Schritt wählt der Algorithmus den von der bereits berechneten Teilroute am weitesten entfernten Knoten aus. Dieser Knoten wird an der Stelle in die vorhandene Teilroute eingebaut, so dass die geringste Verlängerung der bisherigen Teilroute entsteht.
Der FARIN-Algorithmus besteht also genau genommen aus den zwei Teilen:
- Auswahl des „teuersten“ Knoten (farthest selection)
- Einfügen an der „billigsten“ Stelle (cheapest insertion)
Alternativen
Alternative Einfüge-Heuristiken fügen z. B. jeweils den nächsten (billigsten) Knoten (Nearest-Insertion-Heuristik, NEARIN) oder einen mit einem gleichverteilenden Zufallszahlengenerator gewählten Knoten (RANDIN; von „random insertion“) ein.
Siehe auch
Weblinks
Wikimedia Foundation.
Schlagen Sie auch in anderen Wörterbüchern nach:
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… … 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
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
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
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
Handlungsreisendenproblem — 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
