RANDIN

RANDIN

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 Travelling Salesman Problem (TSP).

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

Siehe auch


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Randin — ist der Familienname folgender Personen: Alexander Randin (* 1991), norwegischer Straßenradrennfahrer Michael Randin (* 1985), Schweizer Radrennfahrer Diese Seite ist eine Begriffsklärung zur Unterscheidung mehrerer mit dems …   Deutsch Wikipedia

  • RANDIN-Algorithmus — 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 Travelling Salesman Problem (TSP). Der Algorithmus fügt in jedem Schritt eine mit einem… …   Deutsch Wikipedia

  • Calvos de Randín — Saltar a navegación, búsqueda Calvos de Randín Bandera …   Wikipedia Español

  • Calvos de Randín — Drapeau Blason …   Wikipédia en Français

  • Michaël Randin — Michael Randin Michael Randin …   Wikipédia en Français

  • Michael Randin — (* 29. Januar 1985) ist ein Schweizer Radrennfahrer. Michael Randin wurde 2003 in Gansingen Schweizer Nationalmeister im Strassenrennen der Juniorenklasse. Seit 2006 fährt er für das Schweizer Continental Team Hadimec Nazionale Elettronica. In… …   Deutsch Wikipedia

  • Michael Randin — Michael Randin …   Wikipédia en Français

  • Alexander Randin — (* 19. August 1991) ist ein norwegischer Straßenradrennfahrer. Alexander Randin gewann 2008 in der Juniorenklasse eine Etappe und die Gesamtwertung beim Eidsvollrittet, sowie zwei Teilstück und die Gesamtwertung beim Hero Petit Prix. Im nächsten… …   Deutsch Wikipedia

  • Hugues Randin — (1628 – c. 1680) was a French engineer in the employ of Governor Louis de Buade de Frontenac. He was also a cartographer and, in the practice of the day, an architect on at least one project.The first we know of Hugues Randin is his arrival in… …   Wikipedia

  • Calvos de Randín — Calvos de Randím is a municipality in Ourense in the Galicia region of the north west Iberian Peninsula. It is located to the very south of the province …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”