Praktische Informatik 1

0.2 Einführungsbeispiel

Um sich der Frage zu nähern, was eigentlich praktische Informatik ist, betrachtet man am besten ein Beispiel. Ein bekanntes Problem der Informatik ist das Problem des Handlungsreisenden (Travelling Salesman Problem, TSP). Ein Handlungsreisender muss bei seiner Arbeit Kunden besuchen, die in verschiedenen Orten wohnen. Aufgabe der Sekretärin ist es nun, eine Tour zu planen, die ihn zu jedem Kunden genau einmal führt und am Schluss wieder zum Ausgangspunkt zurück bringt. Natürlich sollte die Tour optimal sein, d.h., möglichst wenig Ressourcen verbrauchen. Abhängig davon, welchen Begriff von Ressource man zu Grunde legt, gibt es verschiedene Varianten der Aufgabenstellung. Beim allgemeinen TSP gehen wir davon aus, dass der Handlungsreisende z.B. mit dem Flugzeug unterwegs ist: da es nicht immer von jedem beliebigen Punkt zu jedem anderen eine direkte Flugverbindung gibt, muss die Sekretärin das Streckennetz der Fluggesellschaften und die jeweiligen Flugzeiten (oder Ticketpreise) berücksichtigen. Beim euklidischen TSP bewegt sich der Handlungsreisende zu Fuß oder mit dem Auto, d.h. er kommt überall hin und die Kosten sind proportional zu den Entfernungen zwischen den Punkten auf der Landkarte. Das metrische TSP ist eine Verallgemeinerung des euklidischen und ein Spezialfall des allgemeinen TSP: zwischen je zwei Punkten besteht eine Verbindung, und die Dreiecksungleichung gilt (die Summe der Kosten von A nach B und der Kosten von B nach C ist größer gleich der Kosten von A nach C).
Hier ist ein Beispiel für das allgemeine TSP:

Die beiden angegebenen Lösungen haben die Länge 33 und 22. Welches ist die optimale Tour?

Hier ist ein Beispiel für das euklidische TSP (nach http://mathsrv.ku-eichstaett.de/MGF/homes/grothmann/java/TSP/):

Dieses euklidische TSP hat 250 Punkte. Angegeben sind eine Näherungslösung (Weglänge 12,91) und eine optimale Lösung (Weglänge 12,48).

Was ist nun eine geeignete Methode, um das Problem zu lösen? Eine häufige Herangehensweise der Informatik ist es, ein Problem auf ein einfacheres zurückzuführen. Wir wissen, wie die Lösung eines TSP mit nur 2 Punkten (Firmensitz und ein Kunde) aussieht: Der Handlungsreisende muss hin- zurückfahren. Angenommen, wir wissen, wie wir eine Tour mit n Punkten löst. Dann kommen wir zu einer Lösung für (n+1) Punkten, indem wir einen beliebigen Punkt zunächst weglassen, eine optimale Tour für n Punkte konstruieren, und den weggelassenen Punkt dann als erstes Ziel in die Tour einfügen. Das ist natürlich noch nicht die optimale Lösung, aber wenn man das für alle Punkte der Reihe nach macht und die Tour mit der minimalen Länge wählt, bekommt man dadurch das Optimum.

Diesen Algorithmus könnte man etwa wie folgt notieren:

Wir nehmen an, der Startpunkt (Firmensitz) sei fest gegeben und notieren eine Tour durch die Folge der zu besuchenden Punkte (ohne den Startpunkt S) und durch die zugehörige Länge.
Tour minTour (Punktmenge M) {

Wenn M einelementig (M={A}) dann

Rückgabe ((A, 2* |SA|))

Sonst {

// Berechne die kürzeste Tour rekursiv

Sei minT eine neue Tour, wobei zunächst

Punkte (minT) = undefiniert, Länge(minT)=unendlich;

Für jedes x aus M {

Tour rek = minTour (M-{x});

Sei A der erste Ort von rek;

Sei Tour try gegeben durch

Punkte (try) = append(x, Punkte(rek)));

Länge (try) = Länge(rek) - |SA| + |Sx| + |xA|;

Wenn Länge(try) < Länge(minT) {minT=try};

}

Rückgabe minT;

}

}
Wenn wir den Ablauf dieser rekursiven Funktion z.B. für die Punkte {ABC} betrachten, stellen wir folgende Aufrufe fest:

minTour ({ABC}) ruft

minTour({BC}) ruft

minTour({C}) und

minTour({B}).

minTour({AC}) ruft

minTour({C}) und

minTour({A}).

minTour({AB}) ruft

minTour({B}) und

minTour({A}).

Das bedeutet, ein Aufruf mit n Punkten stützt sich auf n Aufrufe mit (n-1) Punkten ab, jeder davon stützt sich auf (n-1) Aufrufe mit (n-2) Punkten ab usw. Insgesamt gibt es

Aufrufe. Im Wesentlichen konstruiert der Algorithmus sämtliche Permutationen der Folge der Punkte. Die Anzahl der Permutationen von n Elementen ist n!. Wir sagen, der Algorithmus hat die Komplexität O(n!).

Nachfolgende Tabelle gibt einen Überblick über das Wachstum verschiedener Funktionen.

Wenn wir den Algorithmus auf einem schnellen Pentium DualCore ausführen, der bis zu 4 Milliarden Operationen pro Sekunde ausführt, dann müssen wir für n=10 etwa eine Millisekunde warten. Für n=50 erhöht sich unsere Wartezeit allerdings auf etwa 10²⁸=3.000.000.000.000.000.000.000.000.000 oder 3 Quatrilliarden Jahre. Das heisst, für große Werte von n ist der Algorithmus praktisch nicht verwendbar. Auf der anderen Seite ist es ein offenes Problem, ob es tatsächlich einen substantiell besseren Algorithmus gibt! Wer einen Algorithmus entdeckt, welcher das TSP mit einer polynomialen Anzahl von Schritten löst (abhängig von n), wird mit Sicherheit weltberühmt werden.
Natürlich gibt es einige Tricks, um die Laufzeit des Algorithmus zu verbessern. Zum Beispiel fällt auf, das während der Rekursion der gleiche Aufruf mehrmals stattfindet. Hier kann man sich mit dem Abspeichern von Zwischenergebnissen behelfen. Dann kann man die Suche stark parallelisieren. Auch hängt es sehr stark von der Implementierung ab, ob man den rekursiven Aufruf naiv oder raffiniert implementiert. Mit solchen Tricks ist es im Jahr 2004 gelungen, ein TSP mit 24.978 schwedischen Städten zu lösen (http://www.tsp.gatech.edu/ http://www.math.princeton.edu/tsp/d15sol/)! Der Weltrekord liegt laut Wikipedia (http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden) bei der Lösung eines Planungsproblems für das Layout integrierter Schaltkreise mit 85.900  Knoten. Zur Lösung solcher Probleme werden Netze von über hundert Hochleistungscomputern mit einer Gesamtsumme von über 20 Jahren Rechenzeit verwendet. Zum Vergleich: Im Jahr 1977 lag der Rekord noch bei 120 Städten!

Was macht man aber nun, wenn man das Problem in der Praxis (zum Beispiel in einer mittelständischen Reisebüro-Software) lösen will, wo man kein Hochleistungs-Rechnernetz zur Verfügung hat? Die Antwort der praktischen Informatik heißt Heuristik. Das Wort „Heuristik“ kommt aus der Seefahrt und bezeichnete früher Verfahren, um seine Position annähernd zu bestimmen. Heute bezeichnen wir damit Näherungsverfahren, die zwar nicht die optimale Lösung, aber eine hinreichend genaue Annäherung liefern. Java-Animationen mit verschiedenen Heuristiken sind zu finden unter (http://web.telia.com/~u85905224/tsp/TSP.htm) und (http://www-e.uni-magdeburg.de/mertens/TSP/index.html).

Heuristik 1: nächster Nachbar

Bei dieser Heuristik sucht der Reisende, ausgehend von einem beliebigen Punkt, zunächst den nächsten Nachbarn des aktuellen Punktes auf der Landkarte. Dann bewegt er sich zu diesem und wendet die Heuristik erneut an. Wenn er alle Kunden besucht hat, fährt er nach Hause zurück. Obwohl diese Heuristik sehr häufig im täglichen Leben angewendet wird, liefert sie schlechte Resultate, da der Heimweg und andere unterwegs „vergessene“ Punkte meist hohe Kosten verursachen.

Heuristik 2: gierige Dreieckstour-Erweiterung

Die Sekretärin wählt zunächst zwei Kunden willkürlich aus und startet mit einer einfachen „Dreieckstour“. Diese wird dann nach und nach erweitert, und zwar wird jede Stadt da in die Tour eingefügt, wo sie am besten „passt“, d.h., wo sie die gegebene Tour am wenigsten erweitert. Solche Strategien nennt man „gierig“, da sie nur auf lokale und Optimierung ausgerichtet sind und das Gesamtergebnis nicht berücksichtigen.

In der geschilderten Form sind noch zwei Zufallselemente enthalten: Die Wahl der ursprünglichen Dreieckstour, und die Reihenfolge, in der die Knoten hinzugefügt werden.

Heuristik 3: Hüllen-Erweiterung

Eine andere Variante dieser Heuristik startet mit der konvexen Hülle aller Punkte (d.h., den Punkten, die am weitesten außen liegen), und fügt der Reihe nach diejenigen Knoten hinzu, die die wenigsten Kosten verursachen. Das heißt, es werden der Reihe nach die Knoten hinzugefügt, die den geringsten Abstand von der bisher konstruierten Tour haben. Das ist wieder ein „gieriger“ Algorithmus, und zwar in doppelter Hinsicht: bei der Auswahl der Punkte und bei der Bestimmung der Einfügestelle.

Heuristik 4: inverse Hüllen-Erweiterung

Wieder starten wir mit der konvexen Hülle aller Punkte und fügen der Reihe nach diejenigen Knoten hinzu, die die meisten Zusatzkosten verursachen. Das heißt, es werden die Knoten hinzugefügt, die am weitesten von der bisherigen Tour entfernt liegen. Dadurch wird das Gesamtergebnis (die Form der Tour) frühzeitig stabilisiert.

Heuristik 5: Lin-Kernighan

Hier versucht man, eine bestehende Tour zu verbessern, indem man zwei Kantenpaare AB und CD sucht und durch die Kanten AC und BD ersetzt (so genannte 2-opt-Strategie). Im endgültigen Lin-Kernighan-Verfahren werden nicht nur Kantenpaare, sondern Mengen von Kanten ersetzt.

Wie wir sehen, führen konträre Ideen manchmal beide zu guten Ergebnissen. Es ist sehr schwer, die „Güte“ von Heuristiken abzuschätzen, da die Leistung immer vom verwendeten Beispiel abhängt. Für jede der genannten Heuristiken lassen sich Beispiele konstruieren, so dass das Ergebnis schlecht ist (die doppelte Länge der optimalen Tour oder noch mehr hat).

Ist es nicht möglich, eine Heuristik zu finden, die „auf jeden Fall“ ein akzeptables Resultat liefert?

Auch hier hat die praktische Informatik Beiträge zu liefern. S. Arora konstruierte 1996 einen „nahezu linearen“ randomisierten Algorithmus für das euklidische TSP, der für eine beliebige Konstante c eine (1+1/c)-Approximation in O(n log(n)^O(c)) Zeit konstruiert (http://www.cs.princeton.edu/~arora/pubs/tsp.ps). Das heißt, z.B. für c=10 bekommt man eine Tour, die höchstens 10% schlechter als die optimale ist, indem wir jeden Knoten durchschnittlich log(n)¹⁰ mal betrachten. Wie wir oben gesehen haben, ist log(n) „fast“ eine Konstante (in allen praktischen Fällen kleiner als 5). Daher ist dies „fast“ ein linearer Algorithmus. Der Algorithmus basiert auf raffinierten geometrischen Überlegungen, nämlich einer baumartigen Zerlegung der Ebene in Quadrate und einer Normierung der Schnittkanten der Verbindungslinien zwischen den Punkten.