Näherungsverfahren 1 SS11

Autoren:

• Martin Eisenhammer
• Alexander Pischel

Approximation des Optimums

In der Praxis interessiert man sich für NP-vollständige Probleme, für denen es keine effizienten Algorithmen gibt. Für eine sinnvolle Lösung sind deshalb "Ersatzalgorithmen" sinnvoll, die sich durch eine Modifizierung des Problems gefunden werden können. Das geschieht z.B. durch das Verstärken oder Abschwächen von Nebenbedingungen oder durch das Einschränken auf Teilprobleme. Das Ergebnis solcher Näherungsalgorithmen sollte sich möglichst geringfügig von der exakten Lösung abweichen.

Heuristik

Der Begriff Heuristik kommt aus dem griechischen "heuriskein" und bedeutet "auffinden" oder "entdecken". Eine Heuristik ist eine Methode, mit der man ein Problem sinnvoll lösen kann, die aber nicht immer funktioniert. Es werden aus einer Vielzahl von Möglichkeiten eine gewisse Anzahl von Möglichkeiten herausgefiltert. Ein Bauer sagt zum Beispiel am Abend schlechtes Wetter für den nächsten Tag vorher und mach am nächsten Tag nur die Aufgaben, die bei schlechtem Wetter möglich sind. Dabei wendet er globale und individuelle Erfahrungsgrundsätze an.

Der Unterschied zwischen Heuristiken und probabilistische Algorithmen besteht darin, dass bei probabilistischen Algorithmen Entscheidungen durch Zufall getroffen werden.

Heuristiken eignen sich vermutlich für NP-vollständige Probleme.

Heuristiken für das Springerproblem

Das Springerproblem, auch das Problem des Rösselsprungs genannt, wurde vor über 200 Jahren von Euler folgendermaßen formuliert:

"Gibt es für einen Springer einen Weg, der jedes Feld eines n \times n-Schachbrettes genau einmal besucht?"

Ein Springer ist eine Schachfigur, die sich von ihrem aktuellen Feld A(x_A,y_A) zu einem Feld B(x_B,y_B) bewegen kann. Dabei gilt entweder

|x_A - x_B|= 2 und |y_A - y_B|= 1 oder

|x_A - x_B|= 1 und |y_A - y_B|= 2 ,

"Im Klartext" bedeutet dies, dass der Springer 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.

Die Anzahl der erreichbaren Felder variiert dabei, so kann ein Springer in einer Ecke des Brettes lediglich zwei mögliche Züge ausführen, während ein Springer in der Mitte des Brettes ganze acht Zugmöglichkeiten besitzt. Ein Schaubild mit Springer S und Springer R plus deren mögliche Züge veranschaulicht den Sachverhalt:

Zu beachten ist, dass es sich bei dem Springerproblem um ein Entscheidungsproblem handelt. Das bedeutet, es wird nicht nach einem konkreten Weg gefragt, sondern lediglich nach der Existenz eines solchen. Auch das Startfeld des Springers ist nicht festgelegt, das heißt, dass auf jedem der n^2 Felder begonnen werden kann. Dies ist wichtig, da im Allgemeinen nicht für jedes Startfeld ein (vollständiger) Springerweg besteht.

Das Springerproblem kann als eine Art des $\textsc{hamilton}$-Weg-Problems (alle Knoten eines Graphen werden genau ein Mal besucht) aufgefasst werden. Im Gegensatz zu diesem allgemeineren Problem ist das Springerproblem jedoch nicht NP-vollständig, d.h. zur Lösung existieren effiziente Algorithmen.

Die wohl simpelste Herangehensweise wäre ein schlichter naiver Algorithmus mit Backtracking, dieser scheitert jedoch schon an relativ kleinen Schachbrettern (etwa ab Größe 10 \times 10) aufgrund des exponentiellen Aufwandes. Jedoch gibt es ebenfalls einen Algorithmus, der das Problem für n \times n große Bretter in \mathcal{O}=(n^2) exakt löst(im Prinzip für eine gerade Feldzahl m in \mathcal{O}=(m). Mit diesem Algorithmus soll sich nun jedoch nicht näher befasst werden.

Eine sehr bekannte Heuristik zur Lösung des Springerproblems stellt die $\textsc{warnsdorff}$-Heuristik dar. ihr liegt die einfache (und richtige) Vermutung zugrunde, dass ein Feld eher Gefahr läuft, isoliert zu werden(und damit eine Lösung auf dem aktuellen Weg ausschließt), wenn es nur wenige mögliche Folgefelder gibt, da diese Anzahl gleich der Anzahl Felder ist, von denen aus man das entsprechende Feld betreten kann. Davon ausgehend lassen sich folgende Regeln formulieren:

• Ziehe stets auf das Feld mit der niedrigsten Zahl (noch) möglicher Folgefelder.
• Sollten mehrere Folgefelder die gleiche Zahl möglicher Folgefelder aufweisen, ziehe auf das zuletzt betrachtete Feld. (Es kann auch genauso gut das zuerst betrachtete Feld sein, entscheidend ist lediglich, dass ein geeignetes Feld gewählt wird)

Ein diese Heuristik nutzender Algorithmus leistet folgendes:

• Das zuletzt besuchte Feld ist nicht mehr begehbar und wird somit als Folgefeld für alle Felder gestrichen (dh. implizit, die Feldwerte der Folgefelder werden dekrementiert.)
• Das zuletzt besuchte Feld wird als ebensolches markiert und landet in einer Wegliste.
• Das als nächstes zu besuchende Feld wird nach o.g. Kriterien ermittelt.
• Sollte es kein Folgefeld geben, wird abgebrochen (und z.B. eine Fehlermeldung ausgegeben.)
• Nach n^2 Zügen wird eine Springertour ausgegeben.

Diese Heuristik liefert eine näherungsweise Lösung des Springerproblems, jedoch meidet diese Heuristik für hinreichend große Felder nicht alle Sackgassen. Für hinreichende kleine Bretter (2 \leq n \leq 4, von der Triviallösung für n = 1 kann getrost abgesehen werden) gibt es hingegen keinerlei Lösungen.

Diese Heuristik arbeitet ebenfalls in Polynomzeit, genauer in \mathcal{O}=(n^2), jedoch nur, falls sie alle Sackgassen meidet. Da dies, wie bereits angebracht, nicht für beliebig große Bretter zutrifft, arbeitet der Algorithmus tatsächlich mit einem höheren Aufwand als dem angegebenen.

Aufgrund dieser Tatsache liegt es nahe, die Heuristik zu modifizieren, um so einen effizienteren Algorithmus erzeugen zu können. So könnte zum Beispiel einfach das nächste zu besuchende Feld zufällig ausgewählt werden, anstatt das letzte geeignete Feld zu betreten. Auch andere Modifikationen sind sinnvoll, wie zum Beispiel:

• Wähle als nächstes Feld das am nächsten zur Brettmitte gelegene.
• Wähle als nächstes Feld jenes, welches die größte Summe aller Feldwerte dessen möglicher Folgefelder besitzt.

Neben dem klassischen Springerproblem gibt es auch Varianten mit verschärften Bedingungen:

1. Gibt es eine geschlossene Springertour? (D.h., der Springer kann vom Zielfeld in einem Zug das Startfeld erreichen.)
2. Gibt es einen Springerweg auf einem n \times n Schachbrett von einem vorgegebenen Startfeld S zu einem vorgegebenen Zielfeld Z?
3. Gibt es einen Springerweg auf einem n \times m Schachbrett von einem vorgegebenen Startfeld S zu einem vorgegebenen Zielfeld Z?

Problem 1 lässt sich auch mit der Frage nach der Existenz eines $\textsc{Hamilton}$-Kreises beschreiben.

Lokale Suche

DNA Computing

Evolutionäre Algorithmen

Der Prozess der Evolution ist ein Prozess, der in der Natur dafür sorgt, dass sich Arten bzw. Populationen bestimmten Bedingungen anpassen. Dies geschieht durch verschiedene Faktoren (Mutation, Selektion, Rekombination als Hauptfaktoren) und dient dazu, Populationen gegenüber oben genannten Bedingungen zu optimieren, damit sie höhere Chancen haben, ihre Existenz beizubehalten.

Mutation als zufälliger Faktor ist dazu gedacht, mögliche neue Varianten zu finden, um festzustellen, ob sie für ihren Lebensraum eine verbesserte Anpassung darstellen oder ungeeignet sind. Mutation sorgen für gewöhnlich nur für geringfügige Veränderungen am Genpool einer Population, sind aber die Grundlage für Veränderungen in der Evolution, da sich viele kleine Änderungen zu einer großen Gesamtänderung aufsummieren.

Rekombination beschreibt den Prozess, aus dem Erbgut zweier Individuen Erbgut für ein Nachkommenindividuum zu erzeugen, das sich aus dem alten Erbgut zusammensetzt. Durch diesen Faktor können Kombinationen von Eigenschaften gefunden werden, die dem Optimum näher kommen als die vorhandenen.

Selektion als einziger gerichteter Vorgang sorgt dafür, dass sich eher bzw. nur die vorteilhaftesten Eigenschaften einer Population durchsetzen. Dabei wird in der Natur allerdings kein höheres Ziel angesteuert, sondern lediglich die Optimale momentane Anpassung erstrebt. Ein Fitnesswert, der aussagt, wie viel ein Individuum im Moment "taugt". So kann zum Beispiel über die Anzahl der Nachkommen ein Fitnesswert mit folgender Formel gebildet werden:

G' stellt dabei das Individuum mit der höchsten Anzahl an Nachkommen in der Population dar.

Wie man bis hier leicht bemerken kann, ist Evolution ein optimierungsprozess mit