Grenzen des Rechnens

Beim Sortieren war der Unterschied zwischen den Verfahren groß, aber am Ende hat jedes funktioniert. Es gibt Aufgaben, bei denen das nicht mehr gilt — bei denen der beste bekannte Algorithmus auf dem schnellsten Rechner der Welt länger braucht, als das Universum alt ist.

Das Erstaunliche daran: Diese Aufgaben sehen harmlos aus. Manche kannst du in einer Minute mit dem Finger auf einer Landkarte lösen.

Der Ausflug

Eure Klasse plant eine Fahrt. Sieben Orte sollen besucht werden, und am Anfang wie am Ende steht eure Schule:

• eure Schule in Leipzig
• Deutscher Bundestag, Berlin
• Elbphilharmonie, Hamburg
• Deutsches Museum, München
• Flughafen Frankfurt am Main
• Deutsche UNESCO-Kommission, Bonn
• Kyffhäuserdenkmal
• Hauptbahnhof Weimar

Kartengrundlage: © OpenStreetMap-Mitwirkende, Daten unter ODbL

Die Frage ist simpel: In welcher Reihenfolge fährt man, damit die Strecke möglichst kurz wird?

Findet die kürzeste Rundreise

Nehmt ein Navigationsprogramm und tragt die acht Orte als Zwischenstopps ein. Verschiebt die Reihenfolge so lange, bis ihr die Gesamtstrecke nicht mehr kürzer bekommt.

Notiert eure beste Reihenfolge und die Kilometerzahl. Vergleicht danach in der Klasse.

Ihr werdet feststellen: Fast alle Gruppen landen bei derselben Reihenfolge, und das in wenigen Minuten. Merkt euch dieses Gefühl — wir kommen darauf zurück.

Die Karte wird zum Graphen

Ein Rechner sieht keine Karte. Damit er mit dem Problem etwas anfangen kann, wird daraus ein Graph: Jeder Ort ist ein Knoten, jede mögliche Fahrt eine Kante, und an jeder Kante steht, wie lang sie ist.

Kartengrundlage: © OpenStreetMap-Mitwirkende, Daten unter ODbL

Werden die Kanten mit den Entfernungen beschriftet, heißt der Graph gewichtet:

Kartengrundlage: © OpenStreetMap-Mitwirkende, Daten unter ODbL

Graph

Ein Graph besteht aus Knoten und aus Kanten, die je zwei Knoten verbinden. Tragen die Kanten Zahlen — Entfernungen, Kosten, Fahrzeiten —, nennt man den Graphen gewichtet. Sehr viele Probleme lassen sich so aufschreiben: Straßennetze, Freundschaften in sozialen Netzwerken, Abhängigkeiten zwischen Bauteilen.

Gesucht ist eine Rundreise, die jeden Knoten genau einmal berührt und am Startpunkt endet — und von allen solchen Rundreisen die kürzeste.

Problem des Handlungsreisenden

Das Problem des Handlungsreisenden (englisch Traveling Salesman Problem, TSP) fragt nach der kürzesten Rundreise durch eine gegebene Menge von Orten, bei der jeder Ort genau einmal besucht wird und die am Ausgangsort endet.

Alles durchprobieren

Der naheliegende Algorithmus: Probiere jede mögliche Reihenfolge aus, rechne ihre Länge aus, merk dir die kürzeste. Der ist garantiert richtig. Die einzige Frage ist, wie viele Reihenfolgen es gibt.

Der Startort ist egal, denn eine Rundreise hat keinen Anfang. Bleiben n − 1 Orte, die in beliebiger Reihenfolge kommen können: (n − 1)! Möglichkeiten. Und weil jede Tour vorwärts und rückwärts dieselbe ist, noch geteilt durch zwei. Zusammen sind das ½ · (n − 1)! mögliche Rundreisen — eine kurze Formel mit unangenehmen Folgen.

Aufgabe

Wie schnell diese Zahl wächst, zeigt die Tabelle. Die Rechenzeit darin nimmt an, dass ein Rechner für eine einzelne Tour rund eine Millisekunde braucht, also etwa tausend Touren in der Sekunde schafft.

Orte n	½ · (n − 1)!	mögliche Rundreisen	Rechenzeit
3	½ · 2!	1	1 ms
4	½ · 3!	3	3 ms
5	½ · 4!	12	12 ms
6	½ · 5!	60	60 ms
7	½ · 6!	360	360 ms
8	½ · 7!	2.520	2,5 s
9	½ · 8!	20.160	20 s
10	½ · 9!	181.440	3 min
11	½ · 10!	1.814.400	0,5 Stunden
12	½ · 11!	19.958.400	5,5 Stunden
13	½ · 12!	239.500.800	2,8 Tage
14	½ · 13!	3.113.510.400	36 Tage
15	½ · 14!	43.589.145.600	1,4 Jahre
16	½ · 15!	653.837.184.000	gut 20 Jahre

Für eure acht Orte sind es 2520 Touren — gut zwei Sekunden. Bei zwölf Orten sitzt derselbe Rechner schon fünfeinhalb Stunden daran, bei vierzehn Orten sechsunddreißig Tage, bei sechzehn Orten zwanzig Jahre.

Das ist der Unterschied zu allem, was du bisher gesehen hast. O(n²) ist unangenehm, aber beherrschbar: doppelt so viele Daten, viermal so viel Arbeit. Hier wird die Arbeit bei jedem einzelnen zusätzlichen Ort um ein Vielfaches größer. Man nennt so etwas exponentielles oder faktorielles Wachstum, und dagegen hilft kein schnellerer Rechner. Ein Rechner, der tausendmal schneller ist, schafft nicht 25, sondern 22 Orte.

NP-vollständig

Für manche Probleme ist kein Algorithmus bekannt, der sie in vertretbarer Zeit exakt löst — und man vermutet, dass es keinen gibt. Diese Probleme heißen NP-vollständig. Das Problem des Handlungsreisenden gehört dazu, ebenso die Stundenplanung und das Färben von Landkarten.

Und das Rucksackproblem — die Sporttasche, in die nicht alles passt, was mitsoll. Jedes Teil hat ein Gewicht und einen Wert, die Tasche eine Grenze. Welche Auswahl bringt am meisten, ohne dass die Tasche platzt? Sicher weißt du es erst, wenn du alle Auswahlen durchgerechnet hast — und deren Zahl verdoppelt sich mit jedem Teil, das zur Debatte steht.

Bemerkenswert: Eine vorgeschlagene Lösung nachzurechnen ist ganz leicht. Nur sie zu finden ist schwer.

Aufgabe

Warum ihr es trotzdem konntet

Ihr habt die Aufgabe oben in wenigen Minuten gelöst. Ihr habt dabei nicht 2520 Touren durchgerechnet — ihr habt auf die Karte geschaut und die Orte der Reihe nach im Kreis verbunden.

Das ist kein Trick, sondern zusätzliches Wissen: Ihr habt gesehen, dass die Orte in einer Ebene liegen, und ihr wusstet, dass eine gute Rundreise sich nicht selbst kreuzt. Der Rechner hat nur eine Tabelle mit Zahlen. Er weiß nicht einmal, dass es eine Karte gibt.

Und ihr habt etwas getan, was ein exakter Algorithmus nie tut: Ihr habt euch mit einer Lösung zufriedengegeben, ohne zu beweisen, dass es keine bessere gibt. Genau das ist der Ausweg.

Heuristik

Eine Heuristik ist ein Verfahren, das in vertretbarer Zeit eine brauchbare Lösung liefert, ohne zu garantieren, dass es die beste ist. Man tauscht Sicherheit gegen Geschwindigkeit — und in der Praxis ist dieser Tausch fast immer richtig.

Nächster Nachbar

Die einfachste Heuristik denkt nicht weiter als bis zum nächsten Schritt: Steh an einem Ort, schau, welcher noch nicht besuchte Ort am nächsten liegt, fahr dorthin. Wiederhole das, bis alle dran waren, und fahr zurück zum Start.

naechster = None
kuerzeste = 999999

for ort in offen:
    if abstand(aktuell, ort) < kuerzeste:
        kuerzeste = abstand(aktuell, ort)
        naechster = ort

Das ist wieder die Minimumsuche aus dem Listen-Kapitel. Ein Verfahren, das immer den im Moment besten Schritt nimmt, heißt gierig (englisch greedy).

Der Aufwand: n Orte, und für jeden schaust du alle übrigen an — das sind n · n Schritte, also O(n²). Aus 310 000 Jahren werden 625 Rechenschritte.

Der Preis: Das Ergebnis kann wie hier recht gut sein, ist aber meistens nicht optimal. Gierige Verfahren laufen sich fest — der letzte Ort, den man vergessen hat kann am anderen Ende der Republik liegen, und die Rückfahrt frisst alles auf, was man vorher gespart hat.

Kartengrundlage: © OpenStreetMap-Mitwirkende, Daten unter ODbL

Aufgabe

Im Programm fehlt genau eine Stelle: die Minimumsuche von oben. Solange sie fehlt, nimmt das Programm immer den erstbesten offenen Ort — es läuft also und gibt auch eine Tour aus, nur ist es nicht die des nächsten Nachbarn. Setz die Suche ein.

Stimmt sie, fährt die Tour von Leipzig zuerst nach Weimar und ist 1752 Kilometer lang statt 1878. Die kürzeste Tour überhaupt — die, die du beim Durchprobieren mit ANZAHL = 8 bekommst — ist 1674 Kilometer lang. Um wie viel Prozent ist die Heuristik schlechter?

2-Opt: Kreuzungen auflösen

Jetzt kommt die Idee wieder ins Spiel, mit der ihr selbst gearbeitet habt. Zeichnet man eine Tour auf, in der sich zwei Strecken kreuzen, sieht man sofort: Das kann nicht optimal sein. Nimmt man die beiden Kreuzungsstrecken heraus und verbindet die Enden anders, wird die Tour kürzer.

Aus den Kanten A → B und C → D werden A → C und D → B, und das Stück dazwischen wird umgedreht.

Links kreuzen sich die Kanten A → B und C → D. Rechts sind sie durch A → C und D → B ersetzt — und die Pfeile zeigen, was dabei leicht übersehen wird: Das Stück von B über E und F nach C wird jetzt andersherum durchfahren.

Ein Programm sieht die Kreuzung nicht. Es muss es anders machen: Es nimmt zwei Kanten heraus, verbindet neu, rechnet die Länge aus — und behält die Änderung, wenn die Tour kürzer geworden ist. Danach fängt es von vorn an, solange sich noch etwas verbessern lässt.

Weil man auch hier nicht alle Fälle unendlich lange durchprobieren kann, hört man nach einer festen Zahl von Durchläufen oder nach abgelaufener Zeit auf. Auch das ist typisch für Heuristiken: Man bestimmt selbst, wie viel Rechenzeit einem die Sache wert ist.

Aufgabe

Wo dir das wiederbegegnet

Hast du das Muster einmal gesehen, findest du es überall. Ein Paketdienst plant jeden Morgen Touren mit Hunderten von Stopps, und weil jeden Tag andere Pakete im Wagen liegen, ist es jeden Morgen eine neue Tour; die beste Reihenfolge rechnet dafür niemand aus. Ein Krankenhaus verteilt Dienste über die Woche, ohne dass jemand zwei Nachtschichten hintereinander bekommt. Eine Schule baut aus Klassen, Lehrkräften und Räumen einen Stundenplan, in dem nichts doppelt belegt ist. Jedes Mal geht es darum, aus unerreichbar vielen Möglichkeiten eine gute auszuwählen, und jedes Mal ist die beste unerreichbar.

Und deshalb ist die wichtigste Frage an einen Algorithmus nicht „Findet er die beste Lösung?", sondern „Findet er in der Zeit, die ich habe, eine gute genug?"

Noch mehr üben

Aufgabe

Aufgabe

Du hast damit das nachgebaut, was NP-vollständige Probleme ausmacht: Prüfen ist einfach, Finden ist schwer.