Approximationsalgorithmen

Da Quantencomputer noch nicht im Alltag eingesetzt werden können und niemand einen effizienten Algorithmus für die Probleme aus NP gefunden hat (man geht auch davon aus, dass es ihn nicht gibt), müssen Algorithmen gefunden werden, die effizient eine Lösung dieser Probleme berechnen, die gut aber vielleicht nicht perfekt ist. Wenn es zu schwer ist, eine Kolorierung einer Landkarte mit 4 Farben zu finden (auch wenn man weiß, dass dies immer möglich ist), dann sollte man akzeptieren, eine Färbung zu finden, die mit 5 oder 6 Farben arbeitet. Solche Lösungen werden als Näherungslösungen bezeichnet. Es gibt verschiedene Ansätze, solche Näherungslösungen zu finden¹⁵.

Bei messbarer Qualität der Lösung (z.B. Länge einer Rundreise beim Traveling Salesman Problem) gibt die Approximationsgüte den Faktor an, um wie viel die Näherungslösung schlimmstenfalls schlechter ist als die optimale Lösung. Eine Güte von 1,01 würde also bedeuten, dass der Approximationsalgorithmus maximal 1% schlechter ist als die optimale Lösung. In der Praxis ist eine Güte von 1,5 oder sogar 2 schon ein guter Wert.

Deutschlandkarte_(Bunt).svg: Stefan-Xp [CC BY-SA 3.0], via Wikimedia Commons

Greedy-Algorithmus beim Problem des Handlungsreisenden, Start in Ulm, Zwischenstand nach 15 Schritten

In der Schule kann nur ein kleiner Einblick in die Prinzipien der Approximationsalgorithmen statt- finden. Der Bildungsplan schlägt vor, z.B. Greedy-Verfahren zu behandeln¹⁶. Dabei steht die Idee und nicht die Analyse der Güte im Vordergrund. Diese kann höchstens experimentell an einigen Beispielen ermittelt werden.

Greedy

Bei Greedy-Algorithmen geht man so vor, dass man bei jeder Entscheidung die momentan am besten erscheinende Möglichkeit wählt. Anders als beim Backtracking nimmt man diese aber nicht zurück, um andere Varianten auszupro- bieren, sondern bleibt bei dieser Entscheidung, auch wenn sie nicht optimal war.

Beispiel 1: Problem des Handlungsreisenden

Von der Startstadt aus wird als nächstes diejenige noch nicht besuchte Stadt angefahren, die am nächsten liegt. Von dort aus geht man wieder zur nächstgelegenen usw.

Das kann dazu führen, dass einzelne Städte in einer Ecke des Landes zunächst ausgelassen werden (hier z.B. Regensburg und Passau) und dann nur noch mit einem sehr weiten Weg zu erreichen sind.

Beispiel 2: Sitzplatzverteilung in einem Bus

Wenn jeder Schüler festgelegt hat, wie gerne er im Bus neben jedem anderen sitzen würde, dann könnte ein Greedy-Algorithmus in jedem Schritt einen noch nicht zugeteilten Schüler auswählen und denjenigen noch nicht platzierten Schüler dazusetzen, der die höchste Bewertung hat. Auch hier müssen eventuell am Ende Schüler zusammengesetzt werden, die sich überhaupt nicht ausstehen können.

Sequentielle Algorithmen

Sequentielle Algorithmen sind geeignet, wenn man die Knoten des Graphen in Teilmengen aufteilen muss. Sie werden dann nach einer gewissen Reihenfolge abgearbeitet und wenn möglich einer bestehenden Teilmenge hinzugefügt. Ist dies nicht möglich, beginnt man eine neue Teilmenge.

Man kann das Färbeproblem eines Graphen auf diese Art lösen: Alle Knoten einer Teilmenge werden in einer Farbe gefärbt. Ein neuer Knoten darf dieser Teilmenge nur dann hinzugefügt werden, wenn er keine gemeinsamen Kanten mit einem der Knoten dieser Teilmenge hat. Sortiert man die Knoten zunächst absteigend nach ihrem Grad, dann werden bei der Färbung eines planaren Graphen (einer Karte) nie mehr als sechs Farben verwendet.

Randomisierte Algorithmen

Bei randomisierten Algorithmen entscheidet der Zufall, wie die Lösung aussieht. Muss eine Entscheidung getroffen werden, wird sie per Zufallsgenerator entschieden.

Beispiel:

Sucht man z.B. einen maximalen Schnitt durch einen Graph, d.h. eine Aufteilung der Knoten in zwei Teilmengen, so dass möglichst viele Kanten zwischen beiden Teilmengen bestehen, kann man z.B. jeden Knoten mit der Wahrscheinlichkeit 1/2 einer der beiden Teilmengen zuordnen. Das Verfahren ist nicht sehr gut, liefert aber immer einen Schnitt, der im Durchschnitt halb so viele Kanten zerschneidet wie der optimale Algorithmus.

Lokale Suche

Man kann eine zufällige Lösung unter Umständen noch schrittweise optimieren. Dazu verändert man die getroffenen Entscheidungen so, dass die Verbesserung der Lösung möglichst groß ist (Methode des steilsten Abstiegs). Man kommt aber auch hier nicht zwangsläufig zur optimalen Lösung insgesamt, da es lokale Extrema geben kann, in denen keine (einzelne) Veränderung eine Verbesserung bringt.

Üblicherweise wird dieses Verfahren dann mehrmals durchgeführt (z.B. 1000x). Das beste Ergebnis wird dann genommen. Dies hat den Vorteil, dass die Chance durch eine ungünstige Wahl am Anfang ein sehr schlechtes Ergebnis zu bekommen, erheblich reduziert wird.

Beispiel 1: Problem des Handlungsreisenden

Die Reihenfolge der Städte wird zunächst zufällig festgelegt. Nun kann man schrittweise Verbesserungen vornehmen. Dabei könnte man unterschiedliche Verfahren anwenden. Zum Beispiel:

• Man ändert die Position einer Stadt in der Liste, so dass die Gesamtstrecke dann möglichst kurz wird.
• Man vertauscht die Positionen zweier Städte in der Liste, so dass die Gesamtstrecke möglichst kurz wird.

Beispiel 2: Dominierende Menge

Man fügt am Anfang zufällig so lange Knoten zur dominierenden Menge hinzu, bis alle Knoten abgedeckt sind (d.h. einer ihrer Nachbarknoten in der dominierenden Menge ist). Danach versucht man so lange, einzelne Knoten aus der dominierenden Menge zu entfernen, wie immer noch alle Knoten abgedeckt sind.

Ob dies eine gute Näherungslösung produziert, müsste man dann untersuchen.

Genetische Algorithmen

Eine interessante Variante der Approximationsalgorithmen stellt ein genetischer Algorithmus dar. Man versucht die Evolution in der Natur nachzuempfinden. Man startet mit mehreren zufälligen Lösungen des Problems (z.B. einer Population von 1000).

Selektion: Aus diesen wählt man die besten aus (z.B. 50), alle anderen verwirft man.

Rekombination: Diese 50 besten werden nun gekreuzt, d.h. es wird ein Teil der Entscheidungen aus der Lösung A mit den restlichen Entscheidungen aus B kombiniert. Dadurch entsteht eine neue Lösung.

Mutation: Man kann auch mit einer gewissen Wahrscheinlichkeit noch Mutationen einbauen, d.h. zufällige Veränderungen der Lösung.

Auf diese Weise erzeugt man wieder eine Population. Nun beginnt der Zyklus der Selektion und Rekombination erneut. Auf diese Weise werden mehrere Zyklen durchgeführt. Allmählich sollten die Lösungen so besser werden (survival of the fittest).

Beispiel: Traveling Salesman

Die Städte werden in zufälliger Reihenfolge angeordnet. Die 50 kürzesten Routen werden ausgewählt. Für die Rekombination werden zwei Rundreisen ausgewählt und von der 1. Route die ersten x Städte übernommen, wobei die Zahl x zufällig festgelegt wird. Danach fügt man alle fehlenden Städte in der Reihenfolge der 2. Rundreise hinzu. Mutationen kann man einbauen, indem man die Position von zwei zufälligen Städten tauscht.

Bildquelle: Verlauf der Länge der kürzesten Rundreise der Population über die Generationen 0-60 (die Länge der optimalen Rundreise liegt vermutlich zwischen 5000 und 6000 km) von ZPG Informatik [CC BY-SA 4.0 DE], aus 1_graphen_hintergrund.odt

¹⁵ Liste von NP-vollständigen Problemen in Wikipedia,URL: https://en.wikipedia.org/wiki/List_of_NP-complete_problems

¹⁶ Bildungsplan Informatik (Schulversuch), 3.3.2.2 Algorithmen auf Datenstrukturen (12) "Strategien (zum Beispiel Greedy) zur Bestimmung von Näherungslösungen in polynomieller Laufzeit beschreiben und an geeigneten Problemstellungen (zum Beispiel 4-Farben-Problem, Dominating Sets) von Hand durchführen"
oder
Approximationsalgorithmen, Jan Johannsen (Vorlesung im Sommersemester 2007) ab Folie 28, URL: http://www2.tcs.ifi.lmu.de/~abel/lehre/SS07/Approx/Folien.pdf (Dez. 2020)

Hintergrundinformationen: Herunterladen [odt][990 KB]

Weiter zu Ausgewählte Graphen-Algorithmen