Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenSamstag, 15. August 2020 

Problem des Handlungsreisenden


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Das Problem des Handlungsreisenden ist sicher ein Problem das viele aus dem Alltag kennen. Es modelliert die wie man möglichst schnell oder billig mehrere hintereinander besuchen kann und wieder zum Ausgangsort In der Praxis wird man dabei auch Orte mehrmals zu besuchen wenn die Reise günstiger wird. Die für ein allgemeines PdH Einschränkung jeden Ort genau einmal zu besuchen also eher künstlich. Indem man gestattet Orte zu besuchen kann man das Problem immer metrisches PdH modellieren (man bildet einfach den Distanzgraphen und ersetzt in einer Lösung die des Distanzgraphen durch die Pfade des Originalgraphen). unten dargestellt ist dies vorteilhaft bei der Lösung des Problems.

Praktisch einsetzbare Lösungsverfahren für das Problem Handlungsreisenden werden innerhalb des Gebietes Operations-Research und als Approximationsalgorithmen erarbeitet.

Graphentheoretische Beschreibung

In vollständigen Graphen mit Kantengewichten bezeichnet man einen Hamiltonkreis als Traveling-Salesman-Tour . Das Problem zu einem solchen Graphen entscheiden ob eine Traveling-Salesman-Tour der Länge höchstens k existiert wobei k eine beliebige reelle Zahl ist bezeichnet als Problem des Handlungsreisenden ( PdH ) bzw. engl. Traveling-Salesman-Problem inzwischen politisch korrekt traveling salesperson problem kurz TSP . Neben diesem Entscheidungsproblem gibt es noch das Optimierungsproblem das kleinste k zu bestimmen für das eine Traveling-Salesman-Tour Länge k existiert und das Suchproblem eine kürzeste Traveling-Salesman-Tour zu finden.

In der Praxis betrachtet man häufig Graphen in denen die Kantengewichtsfunktion f die Dreiecksungleichung erfüllt d.h. für drei beliebige verschiedene x y z aus V gilt f ({ x y })+ f ({ y z })≥ f ({ x z }). Solche Graphen nennt man auch metrisch . Beschränkt man sich auf Graphen in diese Bedingung erfüllt ist so spricht man metrischen Problem des Handlungsreisenden bzw. metrischen Traveling-Salesman-Problem . Zwei Speziallfälle sind das euklidische Problem des Handlungsreisenden bzw. euklidische Travelings-Salesman-Problem und das rektilineare Problem des Handlungsreisenden bzw. rectilineare Traveling-Salesman-Problem . Diese Fälle liegen vor wenn es Funktion gibt die den Knoten des Graphen Punkt in der euklidischen Ebene zuordnet so die Kantengewichte gerade dem Abstand der zugeordneten in der Ebene nach 2-Norm (für euklidisches PdH) bzw. 1-Norm (für rektilineares PdH) entsprechen.

Graphen mit Mehrfachkanten werden hier nicht betrachtet da es nicht auf die Vielfachheit der Kanten ankommt.

Graphentheoretische Probleme und ihre algorithmische Komplexität

Das Problem des Handlungsreisenden ist in seinen Varianten (Entscheidungs- Optimierungs- und Suchproblem) NP-schwer . Es bleibt selbst dann NP-schwer wenn sich auf metrisches PdH oder sogar noch auf euklidisches oder rektilineares PdH beschränkt. Es aber verschiedene polynomielle Algorithmen ( Heuristiken ) für das Problem.

Die einfachste Heuristik ist die so Nächster-Nachbar-Heuristik (manchmal auch Nearest-Neighbor-Heuristik ) die bei einem beliebigen Knoten beginnend jeweils am nähesten noch nicht besuchten Nachbarn und so eine Traveling-Salesman-Tour generiert. Die Güte so erzeugten Tour kann aber beliebig schlecht Für metrisches PdH gibt es zwei bessere Die Minimum-Spanning-Tree-Heuristik kurz auch MST-Heuristik genannt liefert Approximationsgüte mit dem Faktor 2 d. h. gefundene Traveling-Salesman-Tour ist höchstens doppelt so lang die kürzeste. Dazu berechnet sie zunächst einen minimal spannenden Baum und erzeugt dann einen Umlauf um (Verdopplung der Kanten finden einer Eulertour in dem entstandenen eulerschen Graphen und ersetzen benachbarter Kanten falls ihr Nachbar in der Eulertour mehr als einmal wird). Noch besser ist die Cristofides-Heuristik mit 1 5. Hierbei wird statt der Verdopplung Kanten zusätzlich zur MST-Heuristik eine kleinste perfekte Paarung auf den Knoten ungeraden Grades im spannenden Baum berechnet um einen eulerschen Graphen erzeugen.



Bücher zum Thema Problem des Handlungsreisenden

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Traveling-Salesman-Problem.html">Problem des Handlungsreisenden </a>