Random Insertion Algorithmus
# 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.

## 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:
* 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.

## Bewertung

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

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