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 Problems 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.