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.^[1]

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:^[2]

• 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.^[2][3]

Die Laufzeit des Algorithmus ist quadratisch in der Anzahl der Städte.^[4] Die Heuristik liefert in der Praxis sehr gute Ergebnisse. Allerdings kann man Eingabeinstanzen mit ${\displaystyle n}$ Städten konstruieren, bei der die gefundene Tour um einen Faktor ${\displaystyle \Omega (\log \log n/\log \log \log n)}$ länger ist als die kürzeste Tour.^[5] Als obere Grenze für die Abweichung der gefundenen Tour von der optimalen ist der Faktor ${\displaystyle (\lceil \log _{2}n\rceil +1)}$ bekannt, der für alle Einfüge-Heuristiken gilt.^[6]

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“).

1. ↑ Roland Schmitz. Theoretische Informatik für Dummies. Wiley, 2019. Vorschau in Google Books
2. ↑ ^{a b} 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
3. ↑ Robert L. Karg and Gerald L. Thompson (1964) A heuristic approach to solving traveling salesman problems. Mgmt Sci. 10, 225–248. Kurzzusammenfassung: [1]
4. ↑ https://stemlounge.com/animated-algorithms-for-the-traveling-salesman-problem/
5. ↑ Yosi Azar: Lower Bounds for Insertion Methods for TSP. In: Combinatorics, Probability and Computing. Band 3, Nr. 3, 1994, S. 285–292, doi:10.1017/S096354830000119X (englisch, tau.ac.il [PDF; 127 kB]). 
6. ↑ Daniel J. Rosenkrantz: An Analysis of Several Heuristics for the Traveling Salesman Problem. In: SIAM Journal on Computing. Band 6, Nr. 3, 1977, S. 563–581, doi:10.1137/0206041 (englisch, albany.edu [PDF; 1,9 MB]).