Basiswissen

Der kürzeste Weg durch viele Städte: das Travelling Salesman Problem geht davon aus, dass ein Handlungsreisender durch eine bestimmte Anzahl von Städten reisen will. Dabei will er jede Stadt genau einmal besuchen. Den dafür kürzesten Weg zu finden ist die Aufgabe.

Tischbeispiel

Ein einfaches Beispiel kann man selbst auf einem Stück Papier gut nachstellen. Zeichne ein Quadrat mit einer Seitenlänge von 10 Zentimetern. Jede der vier Seiten ist also 10 Zentimeter lang. Dann markiere jede der vier Ecken mit einem dicken Punkt. Zeichne dann noch einen dicken Punkt mitten in das Quadrat, dort also, wo sich auch die zwei Diagonalen des Quadrats kreuzen würden. Wir haben jetzt fünf Punkte, das sind unsere Städte:

A ist die Ecke unten links.

B ist die Ecke unten rechts.

C ist die Ecke oben rechts.

D ist die Ecke oben links.

E ist der Punkt in der Mitte.

Nun denken wir uns verschiedene Wege aus, wie man einaml jeden Punkt, also jede Stadt besucht und am Ende wieder am Anfangspunkt ist:

Variante 1: A -> B -> C -> D -> E -> A

Variante 2: A -> E -> B -> C -> D -> A

Variante 3: A -> E -> C -> B -> D -> A

Jetzt kann man die Länge der drei Routen messen oder berechnen. Messen kann man die Länge einfach mit einem Lineal. Die Streckenlänge der vier Seiten des Quadrates ist immer 10 Zentimeter. Die Länge von einer der Ecken in die Mitte kann man über den Satz des Pythagoras ausrechnen.^[1]

Variante 1: 10 + 10 + 10 + 7 + 7 = 44

Variante 2: 7 + 7 + 10 + 10 + 10 = 44

Variante 3: 7 + 7 + 10 + 14 + 10 = 48

Eine Deutschlandreise

Um beispielweise die kürzeste Variante zum Besuch der 15 größten Städte Deutschlands zu finden, müsste man 43.589.145.600 verschiedene Möglichkeiten durchprobieren. Da ein Durchrechnen aller Möglichkeiten (brute force Methode) meist zu aufwändig wäre, geht man heuristisch vor. Heuristisch heißt, dass man nicht alles durchprobiert, aber trotzdem ein möglichst gutes Ergebnis will. Lösungsstrategien fallen oft in das Gebiet der Graphentheorie ↗

Fußnoten

[1] Zur Länge der Strecke von einer Ecke in die Mitte nehmen wir als Beispiel die Strecke von A (links unten) nach E (die Mitte). Dazu brauchen wir noch den Punkt M, der auf Seite unten in der Mitte zwischen A und B liegt. Jetzt zeichnen wir ein rechtwinkliges Dreieck von A über M nach E und zurück nach A ein. Die beiden Strecken AM und ME sind die Katheten und sie sind beide 5 cm lang. Die Hypotenuse ist die Strecke von E nach A. Der Satz des Pythagoras lautet a²+b²=c² wobei a und b die bekannten Längen der zwei Katheten und c die Länge der gesuchten Hypotenuse ist. Damit ist c=√(a²+b²), hier also: c = EA = √(5²+5²) ≈ 7 cm. Siehe auch Hypotenuse über Pythagoras ↗