Travelling-Salesman-Problem

Faktor-2-Annäherungsverfahren

 aufwärts

Das metrische Travelling-Salesman-Problem ist ein Spezialfall des Travelling-Salesman-Problems. Für diesen Fall gibt es ein Annäherungs­verfahren, das in poly­nomieller Zeit eine Rundreise findet, die höchstens doppelt so lang ist wie die optimale Rundreise.

Metrisches Travelling-Salesman-Problem

Definition:  Sei G = (V, E) ein vollständig verbundener ungerichteter Graph und w : E Pfeil nach rechts reelle Zahlen eine Kanten­gewichtung. Dann ist die Kanten­gewichtung w metrisch, wenn sie die folgende Eigen­schaften einer Metrik hat:

w(i, j) = 0 genau dann wenn  i = j

w(i, j) = w(j, i)

w(i, j) + w(j, k)größer gleichw(i, k)

Aus den drei Bedingungen folgt, dass alle Kanten­gewichte nichtnegativ sind. Die zweite Bedingung ist von sich aus erfüllt, da der Graph ungerichtet ist. Entscheidend ist die Gültigkeit der letzten Bedingung, der Dreiecks­ungleichung. Sie besagt, dass der direkte Weg zwischen zwei Knoten nie länger ist als ein Umweg über einen anderen Knoten.

Das Travelling-Salesman-Problem in einem Graphen mit metrischer Kanten­gewichtung heißt metrisches Travelling-Salesman-Problem.

Das metrische Travelling-Salesman-Problem kommt in der Praxis wahr­scheinlich am häufigsten vor, da meistens Situationen modelliert werden, in denen die Kanten­gewichte tatsächliche Entfernungen sind, d.h. Abstände in einem metrischen Raum.

Verfahren

Das folgende Verfahren berechnet eine Rundreise, die höchstens doppelt so lang ist wie die optimale Rundreise. Grundlage ist das Verfahren zur Berechnung eines minimalen Spannbaums, das eine Zeit­komplexität von O(n2) hat.

 

Ausgangs­punkt ist ein vollständig verbundener ungerichteter Graph G mit einer metrischen Kanten­gewichtung w.

 

G:
Ausgangsgraph G

Sei K die (unbekannte) kürzeste Rundreise. In diesem Beispiel ist die Länge der kürzesten Rundreise

w(K) = 12.

 

K:
(Unbekannte) kürzeste Rundreise K

Wird eine Kante aus K entfernt, so entsteht ein Spannbaum S von G. Weil die Kante fehlt, gilt offenbar

w(Skleiner gleich w(K).

In diesem Beispiel ist w(S) = 9.

 

S:
Spannbaum S

Mit dem Verfahren zur Berechnung eines minimalen Spannbaums wird ein minimaler Spannbaum M des Graphen G konstruiert. Da M minimal ist, gilt

w(Mkleiner gleich w(Skleiner gleich w(K).

In diesem Beispiel ist w(M) = 8.

 

M:
Minimaler Spannbaum M

Sei nun D ein voller Durchlauf durch den minimalen Spannbaum M, d.h. ein Pfad, der bei einer Tiefensuche durch den Baum zustande kommt. Da jede Kante zweimal durchlaufen wird, gilt

w(D)  =  2w(Mkleiner gleich 2w(Skleiner gleich 2w(K).

In diesem Beispiel ist w(D) = 16.

 

D:
Voller Durchlauf D durch M

Der volle Durchlauf D besucht manche Knoten mehrmals; in einer Rundreise soll aber jeder Knoten nur genau einmal besucht werden. Daher wird der volle Durchlauf D abgekürzt: Knoten, die schon besucht worden sind, werden übersprungen. Ausgenommen ist natürlich der Startknoten, dort endet der abgekürzte Durchlauf.

Das Ergebnis ist die gesuchte Rundreise R. Wegen der Dreiecks­ungleichung ist der abgekürzte Durchlauf R nicht länger als der volle Durchlauf D, d.h. es gilt

w(Rkleiner gleich w(D)  =  2w(Mkleiner gleich 2w(Skleiner gleich 2w(K).

Die Rundreise R ist also höchstens zweimal so lang wie die (unbekannte) kürzeste Rundreise K. In diesem Beispiel ist

w(R) = 15 kleiner gleich 2 · 12.

 

R:
Abgekürzter Durchlauf R

Aufgaben

Aufgabe 1:  Gegeben seien n Punkte in der Ebene. Offenbar lässt sich hieraus ein metrisches Travelling-Salesman-Problem bilden, indem der euklidische Abstand zwischen den Punkten als Kanten­gewichtung genommen wird.

Zeigen Sie: Die kürzeste Rundreise ist planar. Oder anders ausgedrückt: Enthält eine Rundreise zwei sich über­kreuzende Kanten, so kann sie nicht die kürzeste Rundreise sein.

Aufgabe 2:  Geben Sie ein metrisches Travelling-Salesman-Problem mit 4 Knoten an, bei dem die Greedy-StrategieErklärung (gehe immer zum nächst­gelegenen Knoten) nicht die optimale Lösung liefert.

 

Weiter:  [Heuristische Verfahren]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 12.10.2005   Updated: 21.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik