Einleitung

Motivation

Besonders in der Praxis sind NP-vollständige Probleme, für die es keine 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". 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. 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 langer Zeit, 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. Eine Springertour heißt geschlossen, wenn das Endfeld des Springers einen Springerzug vom Startfeld entfernt ist. Ein Springer ist eine Schachfigur, die sich von ihrem aktuellen Feld A(x_1 , y_1) zu einem Feld B(x_2 , y_2)) bewegen kann. Dabei muss beachtet werden das:

|x_1 - x_2| = 1 und |y_1 - y_2| = 2

bzw.

|x_1 - x_2| = 2 und |y_1 - y_2| = 1

Das bedeutet der Springer kann in einem Zug in jede Richtung zwei Felder vorwärts und ein Feld seitwärts bewegt werden kann. 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.

eine ausgewählte Lösung für das Springerproblem

.

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.

Also ist der Algorithmus mit exponentiellem Zeitaufwand verbunden. Es kann jedoch schnell gezeigt werden, das für Felder der Größe 2x2, 3x3 und 4x4 keine Lösung existieren.

Warnsdorff Heuristik

Die Warnsdorff Heuristik 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 eine 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

Ein Algorithmus dieser Art leistet folgendes:

• 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 \n^2 Zügen wird die gesuchte Springertour ausgegeben.

Allerdings bietet die Heuristik von Warnsdorff nur eine näherungsweise Lösung des Springerproblems, da bei größeren Spielfelder nicht immer alles Sackgassen gemieden werden. Falls alle Sackgassen gemieden werden, arbeitet diese Heuristik arbeitet in der Polynomzeit \mathcal{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.

Nun einige Modifikationen der Warnsdorff Heuristik:

1. Wähle nicht das zuletzt/zuerst betrachtete Feld mit dem geringsten Feldwert, sondern das zuerst/zuletzt betrachtete Feld.

2. Wähle bei gleichwertigen Feldwerten die Felder mit den geringsten Feldwerten und bei einer Dopplung wähle eines zufällig aus.

3. Wähle das Feld, das die größte Summe aller Feldwerte der möcglichen Foldefelder hat.

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

Lokale Suche

Unter bestimmten Voraussetzungen können die bereits vorgestellten Verfahren „Verzweigen und Begrenzen“ , „Greedy“ und noch nicht vorgestellte „Hill Climbing“ auch für Nährungen 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 (Im Folgenden werden nun 4 verschiedene Herangehensweisen erklärt)

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. Diese Heuristik arbeitet in Polynomzeit \mathcal{O}(n^2). Aber 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 im Kreis stehen und baut sie dann so wieder auf, dass man sie mittels farthest insertion in die Rundreise integriert. In diesem Bereich ist die Rundweglänge kürzer als zuvor.

Hill Climbing

Threshold accepting

Simulatet annealing

Tabu-Suche

Der Sinflut-Algorithmus

Übungen

Literatur

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