„Random Insertion Algorithmus“ – Versionsunterschied
| [gesichtete Version] | [gesichtete Version] |
Inhalt gelöscht Inhalt hinzugefügt
JamesP (Diskussion | Beiträge) K fixed typo |
+Belege fehlen |
||
| Zeile 1: | Zeile 1: | ||
{{Belege fehlen|2=Dieser Artikel|1=Spezialwissen, nicht-trivial und nur mit Rechercheaufwand zu bestätigen [[WP:Q|=> Belege erforderlich]].}} |
|||
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 '''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]]. |
||
Version vom 28. Januar 2016, 22:02 Uhr
Der RANDIN-Algorithmus (von „random insertion“ (Einfügen einer zufälligen Stadt)) gehört zur Klasse der Einfüge-Heuristiken und dient der Lösung des 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 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“).