Random Insertion Algorithmus

Der Random Insertion Algorithmus (von Englisch random insertion, dt. „zufälliges Einfügen“) gehört zur Klasse der Einfüge-Heuristiken zur Lösung des Problems des Handlungsreisenden.<ref>Roland Schmitz. Theoretische Informatik für Dummies. Wiley, 2019. Vorschau in Google Books</ref>

Algorithmus

Der Algorithmus fügt in jedem Schritt eine mit einem gleichverteilenden Zufallsgenerator gewählte Stadt in die vorhandene Teilroute ein. Danach wird die gewählte Stadt dort eingefügt, wo sie die geringste (kleinste) Verlängerung der bisherigen Teilroute verursacht. Der auch RANDIN bezeichnete Algorithmus besteht also genaugenommen aus den zwei Teilen:<ref name=jstor>The Solution of Travelling Salesman Problems Based on Industrial Data Buddhadev Roychoudhury, John F. Muth. The Journal of the Operational Research Society, Vol. 46, No. 3 (Mar., 1995), pp. 347–353</ref>

• Zufällige Auswahl der nächsten Stadt – „RANDom selection“
• Optimales Einfügen der Stadt in die bestehende Teilroute – „cheapest INsertion“

Das Verfahren wurde ursprünglich von Karg und Thompson vorgeschlagen.<ref name=jstor/><ref>Robert L. Karg and Gerald L. Thompson (1964) A heuristic approach to solving traveling salesman problems. Mgmt Sci. 10, 225–248. Kurzzusammenfassung: [1]</ref>

Bewertung

Die Laufzeit des Algorithmus ist quadratisch in der Anzahl der Städte.<ref>https://stemlounge.com/animated-algorithms-for-the-traveling-salesman-problem/</ref> Die Heuristik liefert in der Praxis sehr gute Ergebnisse. Allerdings kann man Eingabeinstanzen mit <math>n</math> Städten konstruieren, bei der die gefundene Tour um einen Faktor <math>\Omega(\log \log n/\log \log \log n)</math> länger ist als die kürzeste Tour.<ref></ref> Als obere Grenze für die Abweichung der gefundenen Tour von der optimalen ist der Faktor <math>(\lceil\log_2n\rceil +1)</math> bekannt, der für alle Einfüge-Heuristiken gilt.<ref></ref>

Alternativen

Alternative Heuristiken benutzen zum Einfügen z. B. jeweils die weitentfernteste Stadt (FARIN; von „farthest insertion“) oder die nächstentfernteste Stadt (NEARIN; von „nearest insertion“).

Fußnoten

<references />