„Random Insertion Algorithmus“ – Versionsunterschied

Versionsgeschichte interaktiv durchsuchen

[gesichtete Version]

Inhalt gelöscht Inhalt hinzugefügt

Inline

Aktuelle Version vom 15. Februar 2022, 12:29 Uhr

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]

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

Bewertung

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 $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.^[5] 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.^[6]

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

↑ Roland Schmitz. Theoretische Informatik für Dummies. Wiley, 2019. Vorschau in Google Books
↑ ^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
↑ Robert L. Karg and Gerald L. Thompson (1964) A heuristic approach to solving traveling salesman problems. Mgmt Sci. 10, 225–248. Kurzzusammenfassung: [1]
↑ https://stemlounge.com/animated-algorithms-for-the-traveling-salesman-problem/
↑ 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]).
↑ 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]).

[1] Roland Schmitz. Theoretische Informatik für Dummies. Wiley, 2019. Vorschau in Google Books

[jstor-2] 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] ttps://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]).

[1]

[2]

[3]

[4]

[5]

[6]

@@ Zeile 1: / Zeile 1: @@
+Der '''Random Insertion Algorithmus''' (von Englisch ''random insertion'', dt. „zufälliges Einfügen“) gehört zur Klasse der Einfüge-[[Heuristik]]en zur Lösung des [[Problem des Handlungsreisenden|Problems des Handlungsreisenden]].<ref>Roland Schmitz. Theoretische Informatik für Dummies. Wiley, 2019. [https://www.google.de/books/edition/Theoretische_Informatik_f%C3%BCr_Dummies/MmKzDwAAQBAJ?hl=de&gbpv=1&dq=Random+insertion+TSP&pg=PT327&printsec=frontcover Vorschau in Google Books]</ref>
-{{Belege fehlen|2=Dieser Artikel|1=Spezialwissen, nicht-trivial und nur mit Rechercheaufwand zu bestätigen [[WP:Q|=> Belege erforderlich]].}}
+== Algorithmus ==
-Der '''RANDIN-Algorithmus''' (von „random insertion“ (Einfügen einer zufälligen Stadt)) gehört zur Klasse der Einfüge-[[Heuristik]]en und dient der Lösung des [[Problem des Handlungsreisenden|Problems des Handlungsreisenden]].
+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>[https://www.jstor.org/stable/2584328 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: [https://econpapers.repec.org/article/inmormnsc/v_3a10_3ay_3a1964_3ai_3a2_3ap_3a225-248.htm]</ref>
+== Bewertung ==
-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.
+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>{{Literatur |Autor=[[Yosi Azar]] |Titel=Lower Bounds for Insertion Methods for TSP |Sammelwerk=Combinatorics, Probability and Computing |Band=3 |Nummer=3 |Datum=1994 |Seiten=285–292 |DOI=10.1017/S096354830000119X |Sprache=en |Online=https://www.cs.tau.ac.il/~azar/tsp.pdf |KBytes=127}}</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>{{Literatur |Autor=[[Daniel J. Rosenkrantz]] |Titel=An Analysis of Several Heuristics for the Traveling Salesman Problem |Sammelwerk=SIAM Journal on Computing |Band=6 |Nummer=3 |Datum=1977 |DOI=10.1137/0206041 |Seiten=563–581 |Sprache=en |Online=http://www.cs.albany.edu/~res/tsp_sicomp_1977.pdf |KBytes=1900}}</ref>
-Der RANDIN-Algorithmus besteht also genaugenommen aus den zwei Teilen:
-*„RANDom selection“ ''für die Auswahl der nächsten Stadt''
-*„cheapest INsertion“ ''für das Einfügen in die bestehende Teilroute''
 == Alternativen ==
-Alternative Algorithmen benutzen zum Einfügen z.B. jeweils die weitentfernteste Stadt ([[FARIN]]; von „farthest insertion“) oder die nächstentfernteste Stadt ([[NEARIN]]; von „nearest insertion“).
+Alternative Heuristiken benutzen zum Einfügen z.&nbsp;B. jeweils die weitentfernteste Stadt ([[FARIN]]; von „farthest insertion“) oder die nächstentfernteste Stadt ([[NEARIN]]; von „nearest insertion“).
+== Fußnoten ==
+<references />
 {{DEFAULTSORT:Randin Algorithmus}}
 [[Kategorie:Algorithmus (Graphentheorie)]]
+[[Kategorie:Optimierungsalgorithmus]]