RANDIN-Algorithmus

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 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 — 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

  • FARIN — Die Farthest Insertion Heuristik (entfernteste Einfügung, FARIN) ist eine Einfüge Heuristik und damit ein heuristisches Eröffnungsverfahren aus der Graphentheorie. Es dient zur Approximation einer guten Lösung des Problem des Handlungsreisenden,… …   Deutsch Wikipedia

  • Liste von Algorithmen — Dies ist eine Liste von Artikeln zu Algorithmen in der deutschsprachigen Wikipedia. Siehe auch unter Datenstruktur für eine Liste von Datenstrukturen. Inhaltsverzeichnis 1 Klassen von Algorithmen nach Komplexität 2 Klassen von Algorithmen nach… …   Deutsch Wikipedia

  • Farthest-Insertion-Heuristik — Die Farthest Insertion Heuristik (entfernteste Einfügung, FARIN) ist eine Einfüge Heuristik und damit ein heuristisches Eröffnungsverfahren aus der Graphentheorie. Es dient zur Approximation einer guten Lösung des Problem des Handlungsreisenden,… …   Deutsch Wikipedia

  • Heuristik der nächsten Einfügung — Nearest Insertion Heuristik Die Nearest Insertion Heuristik (NEARIN), ist eine Einfüge Heuristik und damit ein heuristisches Eröffnungsverfahren aus der Graphentheorie. Es dient zur Approximation einer guten Lösung des Problem des… …   Deutsch Wikipedia

  • NEARIN — Nearest Insertion Heuristik Die Nearest Insertion Heuristik (NEARIN), ist eine Einfüge Heuristik und damit ein heuristisches Eröffnungsverfahren aus der Graphentheorie. Es dient zur Approximation einer guten Lösung des Problem des… …   Deutsch Wikipedia

  • Nearest-Selection-Heuristik — Nearest Insertion Heuristik Die Nearest Insertion Heuristik (NEARIN), ist eine Einfüge Heuristik und damit ein heuristisches Eröffnungsverfahren aus der Graphentheorie. Es dient zur Approximation einer guten Lösung des Problem des… …   Deutsch Wikipedia

  • Nearest-Selection Heuristik — Nearest Insertion Heuristik Die Nearest Insertion Heuristik (NEARIN), ist eine Einfüge Heuristik und damit ein heuristisches Eröffnungsverfahren aus der Graphentheorie. Es dient zur Approximation einer guten Lösung des Problem des… …   Deutsch Wikipedia

  • Nearest Insertion Heuristic — Nearest Insertion Heuristik Die Nearest Insertion Heuristik (NEARIN), ist eine Einfüge Heuristik und damit ein heuristisches Eröffnungsverfahren aus der Graphentheorie. Es dient zur Approximation einer guten Lösung des Problem des… …   Deutsch Wikipedia

Share the article and excerpts

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