| |
|
In der Praxis betrachtet man häufig nur Graphen, in denen die Kantengewichtsfunktion f die Dreiecksungleichung erfüllt, d.h. für drei beliebige verschiedene Knoten 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 denen diese Bedingung erfüllt ist, so spricht man vom 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 eine Funktion gibt, die den Knoten des Graphen einen Punkt in der euklidischen Ebene zuordnet, so dass die Kantengewichte gerade dem Abstand der zugeordneten Punkte 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 offensichtlich nicht auf die Vielfachheit der Kanten ankommt.
Die einfachste Heuristik ist die so genannte Nächster-Nachbar-Heuristik (manchmal auch Nearest-Neighbor-Heuristik), die bei einem beliebigen Knoten beginnend den jeweils am nähesten noch nicht besuchten Nachbarn aufsucht und so eine Traveling-Salesman-Tour generiert. Die Güte der so erzeugten Tour kann aber beliebig schlecht werden. Für metrisches PdH gibt es zwei bessere Heuristiken. Die Minimum-Spanning-Tree-Heuristik kurz auch MST-Heuristik genannt, liefert eine Approximationsgüte mit dem Faktor 2, d. h. die gefundene Traveling-Salesman-Tour ist höchstens doppelt so lang wie die kürzeste. Dazu berechnet sie zunächst einen minimal spannenden Baum und erzeugt dann einen Umlauf um diesen (Verdopplung der Kanten, finden einer Eulertour in dem entstandenen eulerschen Graphen und ersetzen benachbarter Kanten, falls ihr gemeinsamer Nachbar in der Eulertour mehr als einmal besucht wird). Noch besser ist die Cristofides-Heuristik mit Approximationsgüte 1,5. Hierbei wird statt der Verdopplung der Kanten zusätzlich zur MST-Heuristik eine kleinste perfekte Paarung auf den Knoten ungeraden Grades im minimal spannenden Baum berechnet, um einen eulerschen Graphen zu erzeugen.
Anschauung
Das Problem des Handlungsreisenden ist sicher ein Problem, das viele Personen aus dem Alltag kennen. Es modelliert die Frage, wie man möglichst schnell oder billig mehrere Orte hintereinander besuchen kann und wieder zum Ausgangsort zurückkehrt. In der Praxis wird man dabei auch zulassen, Orte mehrmals zu besuchen, wenn die Reise dadurch günstiger wird. Die für ein allgemeines PdH gegebene Einschränkung, jeden Ort genau einmal zu besuchen, ist also eher künstlich. Indem man gestattet Orte mehrmals zu besuchen, kann man das Problem immer als metrisches PdH modellieren (man bildet einfach den Distanzgraphen und ersetzt in einer Lösung die Kanten des Distanzgraphen durch die Pfade des Originalgraphen). Wie unten dargestellt, ist dies vorteilhaft bei der algorithmischen Lösung des Problems.Graphentheoretische Probleme und ihre algorithmische Komplexität
Das Problem des Handlungsreisenden ist in all seinen Varianten (Entscheidungs-, Optimierungs- und Suchproblem) NP-schwer. Es bleibt selbst dann NP-schwer, wenn man sich auf metrisches PdH oder sogar noch spezieller auf euklidisches oder rektilineares PdH beschränkt. Es gibt aber verschiedene polynomielle Algorithmen (Heuristiken) für das Problem.