Rundreise durch Sachsen

Stell dir vor, du planst eine Rundreise durch die größten Städte Sachsens. Dabei willst du jede Stadt nur einmal besuchen und es soll ein möglichst kurzer Rundweg zurücklegt werden. Das Exponat „Rundreise durch Sachsen“ ermöglicht dir dabei, deine Reise so effizient wie möglich zu planen.

Und nun … die Mathematik dazu:

Man nennt ein solches Problem auch Problem des Handlungsreisenden („Traveling Salesmen Problem“ (TSP)). Dieses kann mithilfe von Graphen modelliert werden. Ein (ungerichteter) Graph ist ein Gebilde, das aus Ecken und Kanten besteht. Jede Kante verbindet dabei zwei Ecken (siehe [1]). Zum Beispiel ist das „Haus des Nikolaus“ ein Graph, der aus 5 Ecken und 8 Kanten besteht (siehe auch das Exponat „Eulers Linien“).

In der Mathematik schreiben wir das folgendermaßen: Ein Graph $(V,E)$ besteht aus

einer endlichen Menge $V$ von Ecken,
einer Menge $E \subseteq \{ \{i,j\} \colon i,j \in V \}$ von Kanten.

Zusätzlich ordnen wir jeder Kante $\{i,j\} \in E$ eine quantitative Größe $c_{ij} \geq 0$ zu, das sogenannte Kantengewicht. Dieses lässt sich z.B. als geografische Länge, als benötigte Zeit von $i$ nach $j$ oder als Fahrtkosten für einen Weg interpretieren.

In Abbildung 3 ist ein Graph dargestellt, dessen Eckenmenge aus den Ecken $A,B,C,D,E$ besteht und der die Kantenmenge

$E = \{ \{A,B\}, \{A,D\}, \{C,A\}, \{B,E\}, \{B,D\}, \{B,C\}, \{C,D\}, \{C,E\}, \{D,E\}, \{E,A\} \}$

besitzt. Hierbei unterscheiden wir z.B. die Kanten $\{A,B\}$ und $\{B,A\}$ im Speziellen nicht, da $c_{AB} = 4 = c_{BA}$ gilt. Man spricht auch von einem ungerichteten Graphen. Insbesondere erfüllen die Kantengewichte die Dreiecksungleichung, d.h. dass z.B. die Entfernung zweier Ecken $i$ und $j$ kleiner ist, als wenn man erst von $i$ nach $k$ und dann von $k$ nach $j$ geht. Allgemein schreibt man dies für beliebige Ecken $i,j,k \in V$ wie folgt

$c_{ij} \leq c_{ik} + c_{kj}.$

Das Ziel eines TSP ist es nun, die kürzeste Tour (oder auch Hamiltonkreis genannt) in dem zugrundeliegenden Graphen zu finden, also eine Rundtour, in der wir jede Stadt nur einmal besuchen und die wir in der Stadt beenden, in der wir unsere Reise begonnen haben. Eine Tour nennt man auch Kreis im Graphen, obwohl er nicht kreisrund zu sein hat. In Abbildung 2 bilden z.B. die rot eingefärbten Kanten eine Tour in diesem Graphen. Dessen Länge ergibt sich dann durch Addition der Kantengewichte, sprich die Länge dieser Tour ist

$c_{AB} + c_{BC} + c_{CD} + c_{DE} + c_{EA} = 18.$

Jedoch gibt es eine Tour, die noch kürzer ist. Kannst du sie finden?

Modellierung des Exponats als Graph

Der Graph, welcher unser Exponat modelliert, besitzt die Eckenmenge

$\begin{align*}V = \ &\{\text{Dresden, Leipzig, Chemnitz, Schkeuditz, Eilenburg, Wurzen, Torgau, Döbeln, Plauen}, \\ &\text{Zwickau, Aue, Annaberg-Buchholz, Freiberg, Freital, Pirna, Meissen, Bautzen, Kamenz,} \\ &\text{Hoyerswerda, Görlitz, Zittau} \}.\end{align*}$

Sie besteht also aus insgesamt 21 verschiedenen Städten, die jeweils eine Ecken in unserem Graphen repräsentiert. Die Kantenmenge ergibt sich bei der Wahl der Route durch die Städte Sachsens. Falls wir unsere Reise zum Beispiel in Dresden beginnen und von dort als erstes nach Leipzig reisen wollen, dann entspräche dieser Weg der Kante

$u \coloneqq \{ \text{Dresden, Leipzig} \} \in E.$

Das Kantengewicht $c_{Dresden, Leipzig}$ ergibt sich dabei als geografischer Abstand zwischen Dresden und Leipzig („Luftlinie“).

Vielleicht konntest du die kürzeste Tour in dem Graphen aus Abbildung 2 schnell bestimmen. Wie du jedoch ziemlich schnell feststellen wirst, ist diese Aufgabe bei diesem Exponat gar nicht so einfach. Das liegt daran, dass dir dafür insgesamt

$\frac{20!}{2} = 1 \, 216 \, 451 \, 004 \, 088 \, 320 \, 000$

(also über eine Trillion!) verschiedene Touren zur Verfügung stehen. Übrigens liegt die Anzahl der möglichen Routen in dem Graphen von Abbildung 2 bei $12$ . Wie du siehst, kann diese Anzahl bei einer großen Eckenanzahl sehr stark ansteigen. Woran dies liegt, wollen wir im nächsten Abschnitt erläutern.

P-NP Probleme

Nehmen wir an, wir wollen $n$ ( $n > 2$ ) Städte besuchen, wobei wir uns bereits in einer dieser Städte befinden. Von unserem Startpunkt aus, stehen uns genau $n - 1$ andere Städte als nächstes Ziel zur Auswahl. Nach Wahl des zweiten Ziels, stehen uns nun für die dritte Stadt genau $n - 2$ andere Städte zur Auswahl, und so weiter. Kombinatorisch könnte man sagen, dass wir ein Urnenmodell ohne Zurücklegen haben, wobei wir auf die Reihenfolge Wert legen. Falls wir so fortfahren, haben wir irgendwann alle $n$ Städte besucht. Es bleibt genau eine weitere Station übrig, nämlich zu unserer Ausgangsstadt zurückzukehren. Es ergibt sich also ein $n + 1$ stufiges Baumdiagramm.

In Abbildung 4 ist ein solches für den Fall $n = 4$ dargestellt. Hier kann man auch erkennen, dass alle Strecken doppelt auftreten, je nachdem in welcher Richtung man die Tour durchläuft (im Uhrzeigersinn oder gegen den Uhrzeigersinn). So ist z.B. die Tour $1 - 2 - 3 - 4 - 1$ dieselbe wie $1 - 4 - 3 - 2 - 1$ . Insgesamt stehen uns demnach

(1) $\frac{1}{2} \cdot (n - 1) \cdot (n - 2) \cdots 1 = \frac{(n - 1)!}{2}$

mögliche verschiedene Touren zur Verfügung, wobei wir mit $\frac{1}{2}$ multiplizieren, da, wie eben angemerkt, jede Tour doppelt auftritt. Übrigens erhält man die Anzahl auch durch Zählen und halbieren der Anzahl aller Pfade im Baumdiagramm.

Möchte man nun mit einem Computer die kürzeste Tour bestimmen, müsste dieser jede einzelne Tour berechnen und aus all diesen Touren die kürzeste aussuchen. Für große $n$ ist dies nicht mehr „effizient“ und würde zu lange dauern (sicherlich länger als ein Menschenleben). Nach (1) wächst die Anzahl der dafür benötigten Rechenschritte sogar stärker als exponentiell mit der Anzahl der Städte an. Jedoch lässt sich immer schnell entscheiden, ob eine gewählte Kantenmenge auch eine Tour in dem Graphen ist, denn ein Computer müsste nur überprüfen, ob wir unsere Reise auch dort beendet haben, wo wir sie begonnen haben, und ob jede andere Stadt nur einmal besucht wurde. Diese Aufgabe kann also „effizient“ bzw. in „polynomieller Zeit“ von einem Computer entschieden werden, sprich die Anzahl der Rechenschritte zur Überprüfung der Richtigkeit einer Route hängt höchstens polynomiell von der Anzahl der Ecken ab. Eine mögliche, aber nicht optimale Tour, ist in Abbildung 5 zu sehen. Am Exponat ist auch eine Skala angebracht, die dir anzeigt, wie kurz deine Tour im Vergleich zur optimalen Tour ist.

Man sagt auch, dass das Problem des Handlungsreisenden in der Komplexitätsklasse $NP$ (nicht-deterministisch polynomiell) und das Entscheidungsproblem, welches bestimmt, ob eine gewählte Kantenmenge eine Tour ist, in der Komplexitätsklasse $P$ (polynomiell) liegt. Ein bis heute ungeklärtes Problem ist, ob $NP = P$ gilt, das heißt, ob die Klasse $P$ aller Probleme, die in polynomieller Zeit lösbar sind, der Klasse $NP$ aller Probleme, bei denen man eine vorgeschlagene Lösung in polynomieller Zeit auf Richtigkeit überprüfen kann, gleicht. Dieses Problem ist eines der sieben Millennium-Probleme, von denen bis jetzt lediglich die Poincaré-Vermutung von Grigori Perelmann im Jahre 2002 bewiesen wurde. Um das $P-NP$ -Problem lösen zu können, müsste man einen Algorithmus finden, der ein Problem aus der Komplexitätsklasse $NP$ in polynomieller Zeit lösen kann. Da dies bis jetzt noch niemanden gelang, geht die Mehrheit der Wissenschaftler:innen davon aus, dass $P \neq NP$ . Konkret würde ein Beweis des $P-NP$ -Problems bedeuten, dass ein Computer „effizient“ in kurzer Zeit, z.B. die kürzeste Tour in einem TSP berechnen kann. Jedoch könnte ein Beweis auch negative Konsequenzen haben, wie z.B. in der Verschlüsselungstechnologie. Falls $P = NP$ gelten würde, bestünde die Möglichkeit, dass Verschlüsselungssysteme in kürzester Zeit zu knacken wären. Folglich könnten unter anderem die Sicherheitssysteme von Banken leicht überwunden werden und unsere Bankdaten wären nicht mehr sicher.

Literatur

[1] Nitzsche, Manfred: Graphen für Einsteiger. Springer, 2005

[2] https://www.spektrum.de/news/loesung-fuer-p-np-problem/1494941

[3] https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden

[4] https://de.wikipedia.org/wiki/P-NP-Problem