Aus ProgrammingWiki

Autoren

Dominik Bitterlich

Alexander Häse

Inhaltsverzeichnis 1 Einleitung 1.1 Motivation 1.2 Heuristiken 2 Heuristiken für das Springerproblem 2.1 Backtracking 2.2 Warnsdorff Heuristik 2.3 Modifikationen der Warnsdorff Heuristik 2.4 Der Conrad-Algorithmus 3 Lokale Suche 3.1 Verzweigen und Begrenzen 3.2 Greedy Heuristiken 3.2.1 Nearest neighbour heuristic 3.2.2 Farthest insertion 3.2.3 Random insertion 3.2.4 Best insertion 3.3 Hill Climbing 3.4 Threshold accepting 3.5 Simulated annealing 3.6 Tabu-Suche 3.7 Der Sintflut-Algorithmus 4 Übungen 4.1 Lösungen 5 Literatur 6 Weblinks

Einleitung

Motivation

Besonders in der Praxis sind NP-vollständige Probleme, für die es keine bekannten effizienten Algorithmen gibt, von großem Interesse. Dies zeigte sich bei der Diskussion des P-NP-Problems. Durch Modifizierung des Problems können sogenannte "Ersatzalgorithmen" gefunden werden. Dies geschieht durch Verstärken oder Abschwächen von Nebenbedingungen oder durch das Einschränken auf Teilprobleme. Man bedient sich also bestimmter Heuristiken, die zumindestens approximative (näherungsweise) Lösungen bieten. Doch es muss auch dafür gesorgt sein dass die Abweichung des Resultats von der unbekannten exakten Lösung möglichst gering ist.

Heuristiken

Heuristik stammt aus dem Griechischen und ist von dem Wort "heuriskien" abgeleitet und bedeutet so viel wie "(auf)-finden" bzw. "entdecken". Anhand von intuitiven Regeln und Erfahrungen wird versucht eine Näherungslösung zu finden. Es handelt sich dabei um ein Verfahren mit dem man ein Problem sinnvoll löse kann, für das jedoch nicht garantiert werden kann das es zu 100% funktioniert. Außerdem ist die Fehlerwahrscheinlichkeit nicht bestimmbar. Bei diesem Verfahren wird aus einer Vielzahl von Möglichkeiten eine Gewissen Anzahl heraus gefiltert. Die sogenannte Brute-Force-Methode ist das Gegenteil zu Heuristiken.

Heuristiken für das Springerproblem

Ausgedacht wurde es vor über 200 Jahren, genauer im Jahre 1758, und zwar von dem Schweizer Leonhard Euler. Das Springerproblem ist ein kombinatorisches Problem, das darin besteht, für einen Springer auf einem leeren $nxn-$ Schachbrett eine Route zu finden, auf der dieser jedes Feld genau einmal besucht wird. Ein Springer ist eine Schachfigur, die sich von ihrem aktuellen Feld zu einem Feld bewegen kann. Dabei muss beachtet werden das:

und

bzw.

und

Das bedeutet der Springer kann in einem Zug in jede Richtung zwei Felder vorwärts und ein Feld seitwärts bewegt werden. Die Koordinaten können dabei Werte natürlicher Zahlen aus [1,n] annehmen. Abhängig von der Position des Springers auf dem Spielfeld ist die Anzahl der erreichbaren Felder. Ein Springer in der Ecke des Spielfeldes hat zwei Möglichkeit sich zu bewegen Hingegen ein Springer in der Mitte des Spielfeldes acht Zugmöglichkeiten besitzt. Das Startfeld des Springers ist nicht festgelegt, also kann auf jedem der Felder begonnen werden. Allerdings gibt es nicht für jeden Startpunkt eine Lösung.

Backtracking

Der Standardalgorithmus für die Lösung solcher Probleme ist das sogenannte Backtracking. Hierbei durchläuft der Algorithmus jede mögliche Kombination. Das bedeutet die Figur wird solange gesetzt, bis entweder die Lösung gefunden wurde, oder man nicht mehr weitersetzen kann. In diesem Fall nimmt man einen Zug zurück und versucht eine Lösung über einen Alternativweg zu finden. Allerdings würde eine Lösung für ein relativ kleines Spielfeld, Monate oder sogar Jahre dauern. Es kann jedoch schnell gezeigt werden, das für Felder der Größe 2x2, 3x3 und 4x4 keine Lösung existieren.

Feldgröße	Laufzeit
5x5	21 Sekunden
6x6	609 Sekunden
7x7	38954 Sekunden
8x8	Tage
9x9	Monate
10x10	Jahre

Also arbeitet dieser Algorithmus nicht mit dem Aufwand sondern ist mit exponentiellem Zeitaufwand verbunden.

Warnsdorff Heuristik

Die Warnsdorff-Heuristik wurde 1823 von dem Herr Warnsdorff entwickelt und beruht auf der Beobachtung, dass die Felder mit besonders geringer Anzahl an Folgefeldern, Gefahr laufen isoliert zu werden, was bedeutet das damit eine Lösung auf dem aktuellen Weg nicht möglich ist. Das ist so weil die Anzahl der Folgefelder eines Feldes A gleich ist mit der Anzahl der Felder von denen ein Springer auf A ziehen kann Warnsdorff entwickelte desshalb folgende Regeln:

1. Ziehe stets auf das Feld mit der niedrigsten Zahl noch möglicher Folgefelder

2. Haben mehrere Felder die gleiche minimale Anzahl, so ziehe auf das zuerst bzw. zuletzt betrachtete Feld

Einen kurzen Algorithmus, zur Lösung des Springerpoblems mit der Warnsdorff-Heuristik, finden Sie in diesem Java Programm

ausführen

So ein Algorithmus wird folgendermaßen abgearbeitet:

• Das zuletzt besuchte Feld ist nicht mehr erreichbar und wird somit als Folgefeld für alle anderen Felder gestrichen
• Das zuletzt besuchte Feld wird als besucht markiert und landet in einer Wegliste.
• Das als nächstes zu besuchende Feld wird ermittelt.
• Sollte es kein Folgefeld geben, wird abgebrochen und eine Fehlermeldung erzeugt
• Nach Zügen wird die gesuchte Springertour ausgegeben.

Die Heuristik von Warnsdorff bietet eine näherungsweise Lösung des Springerproblems. Für alle ( mit ) wird in annehmbarer Zeit eine Lösung gefunden. Man konnte allerdings nachweisen, dass bei Bretter größer als 76x76 nicht immer eine Lösung gefunden wird, da nicht alle Sackgassen gemieden werden. Das bedeutet also die Warnsdorff-Heuristik arbeitet nicht mit dem Aufwand $O(n^2)$!

Modifikationen der Warnsdorff Heuristik

Es ist möglich eine Heuristik zu modifizieren um eventuell eine Verbesserung zu erreichen. Diese Verbesserungen sind allerdings nur schwer nachweisbar, da die Tests dafür kompliziert und umständlich sind. Aufgrund der Tatsache das die Warnsdorff Heuristik nicht mit dem Aufwand arbeitet, weil nicht alle Sackgassen gemieden werden, könnte man folgende Modifikationen anwenden:

• Wähle bei gleichwertigen Feldern mit dem kleinsten Feldwert das Folgefeld zufällig aus.

• Wähle das Feld, das die größte Summe aller Feldwerte der möglichen Folgefelder hat.

• Wähle das Feld, das am weitesten vom Brettrand entfernt ist, also in Zentrumsnähe liegt.

Der Conrad-Algorithmus

Eine Schülergruppe gelang es 1992 im Rahmen des Bundeswettstreits für Informatik eine vollständige Lösung für das Springerproblem zu entwickeln. Der Conrad-Algorithmus wurde nach Axel Conrad, einem Mitglied der Gruppe, benannt. Er arbeitet nach dem Teile und Herrsche Prinzip. Hier wird ein beliebig großes Spielfeld, in 5x5 kleine Spielfelder zerlegt. Ist die Seitenlänge des Spielfeldes kein Vielfaches von 5, so entstehen bei der Zerlegung L-förmige Teile und ein Mittelteil der Größe 6x6 bis 9x9. Es ist möglich von diesen kleinen Teil-Spielfeldern, in die anliege Spielfelder zu springen. So löst man erst ein Teil-Spielfeld und bewegt sich dann von außen nach innen bis die Springertour komplett ist. Dadurch ist es diesem Algorithmus möglich, Spielfelder beliebiger Größe exakt zu lösen. D.h. dieser Algorithmus arbeitet mit dem Aufwand .

Lokale Suche

Unter bestimmten Voraussetzungen können die bereits vorgestellten Verfahren „Verzweigen und Begrenzen“ und „Greedy“ auch für Näherungen verwendet werden.

Verzweigen und Begrenzen

Beim Verzweigen und Begrenzen wird die eigentliche Schrankenfunktion nicht mehr berechnet sondern durch eine Schätzfunktion ersetzt. Das bedeutet das die Bound Berechnung entfällt und es wird akzeptiert das keine Schranke berechnet wurde. Das Ergebnis wird dadurch, dass es sich um ein Näherungsalgorithmus handelt, vom optimal Ergebnis abweichen, jedoch kann man davon ausgehen das Ergebnis in den meisten Fällen zufriedenstellend ist da diese Abweichungen nur minimal.

Greedy Heuristiken

Während das bereits kennen gelernte Greedy-Verfahren eine exakte Lösung bietet, wird bei der Greedy-Heuristik nach einer lokalen Verbesserung gestrebt. Dafür werden weder vorübergehende Verschlechterungen akzeptiert, noch Entscheidungen zurück genommen. Wird eine Greedy-Heuristik zur approximativen Lösung eines TSP verwendet, heisst das nichts anderes als den gewinnträchtigsten Knoten als nächsten in die Rundreise einzubinden um eine möglichst kurze Rundreise zu gewährleisten. Das Rundreiseproblem gehört in die Kategorie der NP-vollständigen Problemen. Für solche Probleme ist kein effizienter Algorithmus bekannt ist.

Nearest neighbour heuristic

Diese Herangehensweise ist eine recht kurzsichtige Methode. Sie startet bei einem zufällig gewählten Knoten und wählt dann als nächsten Knoten, der den aktuellem Standort am nächsten ist. Leider sind die entstanden Ergebnisse sind nicht wirklich zufrieden stellend.

Farthest insertion

Hier gibt es zwei Möglichkeiten:

• Man startet bei den jeweils engsten zusammenliegenden Knoten und erweitert die Rundreise um jeweils den Knoten, dessen Minimalabstand zu einem bereits auf der Route vorhanden Knoten maximal ist.
• Man benutzt eine „konvexe Hülle“, bei der alle am äußeren Rand liegenden Knoten verbunden werden. So entsteht eine Hülle um die noch nicht integrierten Knoten welche dann wie gehabt eingebunden werden. Die entstanden Ergebnisse sind zufriedenstellend.

Random insertion

Hier wird ein unbenutzter Knoten zufällig ausgewählt und so in die Rundreise integriert, dass die Rundreiselänge minimal wird.

Best insertion

Mittlerweile hat man herausgefunden das große Schritte besser sind als kleine, d.h. beim TSP werden anstatt kleine Veränderungen zu betrachtet, möglichst große gewählt. Hier zerstört man die Städte, die in einem bestimmten Kreis stehen. Danach baut man sie wieder auf und integriert sie nach Farthest-insertion in die Route. diesem Bereich ist die Rundreise dann meistens kürzer als vorher.

Zwei Applets für die Greedy-Heuristiken finden sind auf der Seite von Stephan Mertens.

Hill Climbing

Eine weitere Verbesserungsstrategie ist das Hill Climbing auch local search genannt. Hill Climbing bedeutet übersetzt „Bergsteigen“, was auf die Arbeitsweise des Algorithmus hindeutet. Wie diese Analogie nahe legt, wird eine potenzielle Lösung für ein vorliegendes Problem Schritt für Schritt verbessert. Dabei wird jeweils eine lokale Veränderung durchgeführt und nur übernommen, wenn der entstandene Lösungskandidat besser geeignet ist. Anhand des Bergsteigers bedeutet das, dass er immer versucht eine höhere Position auf dem Weg zum Gipfel zu erreichen. Das Verfahren endet, wenn vom aktuellen Punkt aus keine weitere Verbesserung mehr möglich ist. Für den Bergsteiger bedeutet das, dass er entweder die Bergspitze (globales Maximum) erreicht hat oder eben nur einen Nebenhügel (lokales Maximum) von wo aus kein Weg zur Bergspitze (globales Maximum) führt. Dabei wird auch schnell die Schwachstelle des Hill-Climbing-Algorithmus ersichtlich, denn oft endet er in einem lokalem Maximum.

Für das Problem der lokalen Maxima gibt es folgende Lösungsansätze:

• Mehrere Bergsteiger beginnen an verschiedenen Startpunkten, sodass mehrere Maxima erreicht werden können
• Ein lokales Maximum wird verlassen und durch erneutes Bergsteigen kann dann ein anderes Maximum gefunden werden.

Threshold accepting

Dieser Algorithmus arbeitet mit einer Toleranzschwelle $T$, mit der es mögliche ist eine zwischenzeitliche Verschlechterung in Kauf zu nehmen. Dadurch kann man noch bessere Näherungslösungen erreichen. Hier überprüft man, ob eine lokale Veränderung nach einer Bewertung um mehr als $T$ von der vorhergehenden Lösung abweicht und sie verwerfen insofern dies der Fall ist. Anfangs wählt man ein möglichst großes $T$ bzw. ein $T$ durch welches kaum Beschränkungen entstehen. Der Bergsteiger aus dem vorhergehenden Beispiel darf dann auch Wege benutzen die nicht den höchsten Anstieg haben. Wenn nun über einen Längeren Zeitraum keine Verbesserungen eingetreten sind, senkt man $T$ langsam auf null. Allerdings ist der Bergsteiger auf einen Nebengipfel gelandet und $T$ wurde bereits auf null gesenkt, gibt es für ihn keine weitere Möglichkeit das globale Maximum zu erreichen.

Simulated annealing

1983 entwickelten Scott Kirkpatrick, Charles D. Gelatt und Mario P. Vecchi vom IBM-Forschungszentrum Yorktown Heights das sogenannte Simulated-annealing, was übersetzt simuliertes langsames Abkühlen bedeutet. Im Gegensatz zum Threshold-accepting wird hier beim Überschreiten der festen Toleranzschwelle $T$, nicht der gelieferte Lösungsvorschlag verboten. Es wird mit einer bestimmten Wahrscheinlichkeit, mittels Zufallszahl und Exponentialfunktion, zufällig entschieden, ob der gelieferte Lösungsvorschlag doch zu gelassen wird. Diese Wahrscheinlichkeit richtet sich nach der Größe der Überschreitung von. Dabei werden große Überschreitungen deutlich seltener zugelassen als kleinere. Das schließt aber nicht aus, dass gelegentlich auch größere Abweichungen zugelassen werden. Außerdem wird $T$ zusätzlich immer weiter gesenkt um eine globales Minimum zu finden. Für das Beispiel mit dem Bergsteiger würde das bedeutet, er könnte sich sogar mit einer großen Abweichung von $T$, noch vom Nebenhügel zurückziehen um in das tiefste Tal (lokales Minimum) hinab zu steigen. Es wurde jedoch festgestellt, dass das Simulated-annealing-Verfahren ziemlich lange brauch um sich aus einem lokalem Minimum zu befreien.

In dem folgendem Video wird die Arbeitsweise des Simulated-annealing-Verfahren nochmal verdeutlicht:

Tabu-Suche

Der Algorithmus der Tabu-Suche wurde von Fred Glover entwickelt. Beim threshold accepting sowie beim simulated annealing kann es vorkommen, dass ein oder mehrere Schritte rückgängig gemacht werden. Um zu sichern, dass in jedem rückgängig gemachten Schritt nur neue Lösungen erzeugt werden, wird die vorangegangenen $k$ Lösungen in einer sogenannten Tabu-Listen gespeichert. Diese kann in eine oder mehrer Warteschlangen implementiert werden. Stimmt nun ein neuer rückgängig gemachten Schritt mit einer Lösung in der Tabu-Liste überein, wird er verworfen und es muss eine neue Lösung gefunden werden, die noch nicht in der Tabu-Liste vorhanden ist.

Der Sintflut-Algorithmus

Entwickelt wurde der Sintflut-Algorithmus 1993 von den beiden Herren Gunter Dueck und Tobias Scheuer. Beim Sintflut-Algorithmus gibt es im Gegensatz zum Threshold-Accepting-Verfahren keinen Schwellwert $T$ der für jeden Schritt vorgegeben war, sondern nur noch eine Art globale Schranke $S$ für den Zielfunktionswert. Es kann sich in jedem frei entschieden werden, ob die schlechtere oder die bessere Lösung genommen wird. Bedingung dafür ist allerdings das $S$ nicht unterschritten wird. Im Prozessverlauf wird $S$ langsam erhöht wodurch die Anzahl der möglichen Schritte immer weiter eingeschränkt, bis keine Schritte mehr möglich sind und das gesuchte Optimum der Lösung gefunden ist. Für das Beispiel mit dem Bergsteiger bedeutet das er sich versucht während einer steigenden Flut auf den höchsten Punkt zu retten. Der höchste Punkt bzw. Gipfel ist dabei das gesuchte Optimum. Während der Wasserstand immer weiter steigt ist der Bergsteiger ständig in Bewegung und merkt sich dabei den höchsten Punkt, den er bisher erreicht hat. Zwischenzeitlich ist es ihm jedoch möglich jedes Tal und jeden Gipfel zu beschreitet unter der Bedingung das er sich über der Wasserlinie, also der globalen Schranke $S$ bewegt. Ist er komplett von den Wassermassen umgeben und kein Schritt mehr möglich, hat er das lokale Maximum erreicht.

Übungen

1. Nehmen Sie sich Zettel und Stift zur Hand und überprüfen Sie die Aussage, dass für $1 < n < 5$ keine Springertour existiert.

2. Besuchen Sie die Seite von Axel Conrad und versuchen Sie mit Hilfe des Conrad-Algorithmus, ein Schachbrett der Größe 16x16 zu lösen. Falls Sie trotz Website keinen Ansatz finden, versuchen Sie es mit folgendem Ansatz, bevor Sie in die Lösung sehen.

3. Erstellen Sie einen Programmablaufplan für den Sintflut-Algorithmus. Sehen Sie sich dazu die Beispiele aus der Vorlesung nochmal genau an. Sie können dabei Zettel und Stift benutzen oder Sie benutzen das Online Programm "Gliffy" (zum Speichern Registrierung nötig)

Lösungen

1.

2.

3.

Literatur

Christian Wagenknecht Algorithmen und Komplexität. Fachbuchverlag Leipzig, 2003, ISBN 3-446-22314-2, Seite 153-163

Weblinks

^[1] Axel Conrad
^[2] Wikipedia Tabu-Suche
^[3] Wikipedia hill climbing
^[4] Construction Heuristics
^[5] fh-friedberg Sintflut