84.190.2.99: Fehlendes Satzzeichen

2016-07-31T18:19:27Z

Fehlendes Satzzeichen

Neue Seite

{{Belege fehlen|2=Dieser Artikel|1=Spezialwissen, nicht-trivial und nur mit Rechercheaufwand zu bestätigen [[WP:Q|=> Belege erforderlich]].}}
[[Bild:Nearest_Selection_Heuristik.png|miniatur|rechts|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 Handlungsreisenden|Problems des Handlungsreisenden]]; Ziel ist es also, eine möglichst kurze Rundreise durch alle Knoten des Graphen zu finden.

Der Algorithmus wählt in jedem Schritt einen Knoten aus mit der geringsten Entfernung zu einem Knoten der schon konstruierten Teilroute. Dieser wird so in die vorhandene Teilroute eingebaut, dass die geringste Verlängerung der bisherigen Teilroute entsteht.

Der NEARIN-Algorithmus besteht also genaugenommen aus den zwei Teilen:
* '''near'''est selection: für die Auswahl des nächsten Knotens
* cheapest '''in'''sertion: für das Einfügen in den bestehenden [[Kreis (Geometrie)|Kreis]]

Die dabei entstehende Struktur entspricht immer einer [[Transitive Hülle (Relation)|transitiven Hülle]]. Dieses Verfahren wird bis zum n-ten Knoten fortgesetzt und entspricht der Komplexitätsklasse <math>O(n^2)</math>.

Als Varianten dieser treten die [[FARIN|Farthest-Insertion-Heuristik]], die ''Cheapest-Selection-Heuristik'' und die [[RANDIN|Random-Insertion-Heuristik]] auf.

Das Ergebnis des NEARIN-Algorithmus ist in der Regel nicht optimal. Bei Vorliegen der [[Dreiecksungleichung]] kann die Länge der gefundenen Rundreise aber nicht schlechter als das Doppelte der Länge einer optimalen Rundreise sein. Die Kurzsichtigkeit des NEARIN-Algorithmus (es wird beim Aufbau der Rundreise nur in der nächsten Nachbarschaft nach weiteren einzufügenden Knoten gesucht) kann sogar zu Rundreisen mit Überkreuzungen führen, die schon deshalb nicht optimal sein können. In der Praxis werden derartige Algorithmen daher mit nach-optimierenden Algorithmen wie etwa einer [[2-opt]]-[[Heuristik]] kombiniert.

== Siehe auch ==
* [[Algorithmus von Floyd und Warshall]]

[[Kategorie:Algorithmus (Graphentheorie)]]

Nearest-Insertion-Heuristik - Versionsgeschichte

84.190.2.99: Fehlendes Satzzeichen