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". Anhand von intuitiven Regeln und Erfahrungen wird versucht Näherungslösungen 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 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

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

Dieser Algorithmus 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.

Die Heuristik von Warnsdorff bietet eine näherungsweise Lösung des Springerproblems. Für alle n( mit 5 \leq n \leq 100 ) 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.

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:

• Wähle bei gleichwertigen Feldwerten statt das zuletzt/zuerst betrachtete Feld mit dem kleinsten Feldwert, sondern das zuerst/zuletzt betrachtete Feld.

• Wähle bei gleichwertigen Feldwerten die Felder mit den geringsten Feldwerten, eines 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.

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 in einem bestimmten Kreis stehen. Danach baut man sie wieder auf und integriert sie nachFarthest-insertion in die Route. diesem Bereich ist die Rundreise dann meistens kürzer als vorher.

Hill Climbing

Threshold accepting

Simulatet annealing

Tabu-Suche

Der Sinflut-Algorithmus

Ü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

Literatur

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