„Random Insertion Algorithmus“ – Versionsunterschied
| [gesichtete Version] | [gesichtete Version] |
Jocme (Diskussion | Beiträge) Journaltitel |
Es ist eine untere Schranke, das heißt, es gibt Instanzen, bei denen das so schlecht ist. Es heißt nicht, dass es nicht schlechter werden kann. |
||
| Zeile 13: | Zeile 13: | ||
*„cheapest INsertion“ ''für das Einfügen in die bestehende Teilroute'' |
*„cheapest INsertion“ ''für das Einfügen in die bestehende Teilroute'' |
||
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 |
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>Azar, Y. (1994). Lower Bounds for Insertion Methods for TSP. Combinatorics, Probability and Computing, 3(3), 285-292. https://doi.org/10.1017/S096354830000119X</ref> |
||
Azar, Y. (1994). Lower Bounds for Insertion Methods for TSP. Combinatorics, Probability and Computing, 3(3), 285-292. doi:10.1017/S096354830000119X https://doi.org/10.1017/S096354830000119X</ref> |
|||
Das Verfahren wurde ursprünglich von Karg und Thompson vorgeschlagen.<ref name=jstor/><ref>R. L. |
Das Verfahren wurde ursprünglich von Karg und Thompson vorgeschlagen.<ref name=jstor/><ref>R. L. Karg and G. L. Thompson (1964) A heuristic approach to solving traveling salesman problems. Mgmt Sci. 10, 225-248.</ref> |
||
== Alternativen == |
== 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“). |
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“). |
||
Version vom 7. Februar 2022, 11:06 Uhr
| Dieser Artikel wurde zur Löschung vorgeschlagen.
Falls du Autor des Artikels bist, lies dir bitte durch, was ein Löschantrag bedeutet, und entferne diesen Hinweis nicht. | |
| Begründung: Keine Quellen --Christian1985 (Disk) 16:33, 6. Feb. 2022 (CET) |
 |
Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen.
Bitte hilf mit, die Mängel dieses Artikels zu beseitigen, und beteilige dich bitte an der Diskussion! () |
Der Random Insertion Algorithmus (von „random insertion“ (Einfügen einer zufälligen Stadt)) 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]
- „RANDom selection“ für die Auswahl der nächsten Stadt
- „cheapest INsertion“ für das Einfügen in die bestehende Teilroute
Die Laufzeit des Algorithmus ist quadratisch in der Anzahl der Städte.[3] Die Heuristik liefert in der Praxis sehr gute Ergebnisse. Allerdings kann man Eingabeinstanzen mit Städten konstruieren, bei der die gefundene Tour um einen Faktor länger ist als die kürzeste Tour.[4]
Das Verfahren wurde ursprünglich von Karg und Thompson vorgeschlagen.[2][5]
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
- ↑ https://stemlounge.com/animated-algorithms-for-the-traveling-salesman-problem/
- ↑ Azar, Y. (1994). Lower Bounds for Insertion Methods for TSP. Combinatorics, Probability and Computing, 3(3), 285-292. https://doi.org/10.1017/S096354830000119X
- ↑ R. L. Karg and G. L. Thompson (1964) A heuristic approach to solving traveling salesman problems. Mgmt Sci. 10, 225-248.
