AuK/Näherungsverfahren 1 WS13-14
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Java</language>
;Autoren
:[mailto://s3dobitt@stud.hszg.de Dominik Bitterlich]<br/>
:[mailto://s3alhaes@stud.hszg.de Alexander Häse]
==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 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 <math>A(x_1 , y_1)</math> zu einem Feld <math>B(x_2 , y_2)</math>) bewegen kann. Dabei muss beachtet werden das:
<math>|x_1 - x_2| = 1</math> und <math>|y_1 - y_2| = 2</math>
bzw.
<math>|x_1 - x_2| = 2</math> und <math>|y_1 - y_2| = 1</math>
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.
[[Bild:S3dobitt_Knightstour2.gif|thumb|center|250px|Beispielslö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.
Es kann jedoch schnell gezeigt werden, das für Felder der Größe '''''2x2''''', '''''3x3''''' und '''''4x4''''' keine Lösung existieren.
{| class="wikitable" style="width:500px"
|-
!Feldgröße
!Laufzeit
|-
|5x5
|21 Sekunden
|-
|6x6
|609 Sekunden
|-
|7x7
|38954 Sekunden
|-
|8x8
|Tage
|-
|9x9
|Monate
|-
|10x10
|Jahre
|-
|}
Also arbeitet dieser Algorithmus nicht in Polynomzeit <math>\mathcal{O}(n^2)</math> 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
<popup name="Vollständigen Code">
<code id="529233192e2ff" >
boolean imSchachbrett(int x, int y, int breite, int länge) {
return ((0 <= x && x < breite) && (0 <= y && y < länge));
}
int möglicheSchritte(int[][] a, int breite, int länge, int x, int y) {
int anzahl = 0;
int xn, yn;
for (int i = 0; i < 8; i++) {
xn = x + nx[i];
yn = y + ny[i];
if (imSchachbrett(xn, yn, breite, länge) && a[xn][yn] == 0)
anzahl++;
}
return anzahl;
}
boolean findeBestenWeg(int[][] a, int breite, int länge, int[] xy) {
int temp = Integer.MAX_VALUE;
int xn, yn, xx = 0, yy = 0;
for (int i = 0; i < 8; i++) {
xn = xy[0] + nx[i];
yn = xy[1] + ny[i];
if (imSchachbrett(xn, yn, breite, länge) && a[xn][yn] == 0) {
int schritte = möglicheSchritte(a, breite, länge, xn, yn);
if (schritte < temp) {
temp = schritte;
xx = xn;
yy = yn;
}
}
}
if (temp < Integer.MAX_VALUE) {
xy[0] = xx;
xy[1] = yy;
return true;
}
return false;
}
int[] nx = { -2, -2, -1, -1, 1, 1, 2, 2 };
int[] ny = { -1, 1, -2, 2, -2, 2, -1, 1 };
int breite = 0;
int länge = 0;
int ye = 0;
int xe = 0;
int xn, yn;
länge = Integer.parseInt(JOptionPane.showInputDialog(null,
"Geben Sie die Breite eines n*m Schachbretts an : ", "6"));
breite = Integer.parseInt(JOptionPane.showInputDialog(null,
"Geben Sie die Länge eines n*m Schachbretts an : ", "6"));
xe = Integer.parseInt(JOptionPane.showInputDialog(null,
"Geben Sie die x-Koordinate des Springers an (zwischen 1 und "
+ breite + "): ", "2"));
while (xe > breite)
xe = Integer.parseInt(JOptionPane.showInputDialog(null,
"Geben Sie die x-Koordinate des Springers an(zwischen 1 und "
+ breite + "): ", "2"));
ye = Integer.parseInt(JOptionPane.showInputDialog(null,
"Geben Sie die y-Koordinate des Springers an (zwischen 1 und "
+ länge + "): ", "2"));
while (ye > länge)
ye = Integer.parseInt(JOptionPane.showInputDialog(null,
"Geben Sie die y-Koordinate des Springers an (zwischen 1 und "
+ länge + "): ", "2"));
ye--;
xe--;
int[][] a = new int[breite][länge];
int ursprungX = xe, ursprungY = ye;
a[ye][xe] = 1;
int ctr = 1;
int[] xy = new int[2];
xy[0] = ye;
xy[1] = xe;
while (findeBestenWeg(a, breite, länge, xy)) {
a[xy[0]][xy[1]] = ++ctr;
}
if (ctr == breite * länge) {
for (int i = 0; i < breite; i++) {
System.out.println();
System.out.println();
for (int j = 0; j < länge; j++) {
System.out.print(a[i][j] + "\t");
}
}
for (int i = 0; i < 8; i++) {
xn = ursprungX + nx[i];
yn = ursprungY + ny[i];
if (imSchachbrett(xn, yn, breite, länge)) {
if (a[ursprungY + ny[i]][ursprungX + nx[i]] == breite* länge){
gTour = true;
} else
gTour = false;
}
}System.out.println();
System.out.println();
if (gTour == true)
System.out.println("Es ist eine geschlossene Springertour!");
//else System.out.println("Es ist keine geschlossene Springertour!");
} else{
System.out.println("Es gibt keine Lösung für diese Startposition!!");
for (int i = 0; i < breite; i++) {
System.out.println();
System.out.println();
for (int j = 0; j < länge; j++) {
System.out.print(a[i][j] + "\t");
}
}
}
</code></popup>
<run id="52925b12a9222">
</run>
Im allgemeinen sollte so ein Algorithmus folgendes leisten können:
*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 <math>\(n^2 </math> Zügen wird die gesuchte Springertour ausgegeben.
Die Heuristik von Warnsdorff bietet eine näherungsweise Lösung des Springerproblems. Für alle <math>n</math>( mit <math>5 \leq n \leq 100 </math>) 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 in Polynomzeit $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 in der Polynomzeit <math>\mathcal{O}=(n^2)</math> 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 [http://programmingwiki.de/AuK/Teile_und_Herrsche_1_WS13-14 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 in Polynomzeit <math>\mathcal{O}=(n^2)</math>.
[[Bild:S3dobitt_Schachbrett_16x16_unterteilt.jpg|thumb|center|350px|Zerlegung eines Schachbretts]]
== Lokale Suche ==
Unter bestimmten Voraussetzungen können die bereits vorgestellten Verfahren [http://programmingwiki.de/AuK/Verzweigen_und_beschr%C3%A4nken_WS13-14 „Verzweigen und Begrenzen“] und [http://programmingwiki.de/AuK/Greedy-Algorithmen_WS13-14 „Greedy“] auch für Näherungen verwendet werden.
===Verzweigen und Begrenzen===
Beim [http://programmingwiki.de/AuK/Verzweigen_und_beschr%C3%A4nken_WS13-14 ''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 [http://programmingwiki.de/AuK/Greedy-Algorithmen_WS13-14 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. Diese Heuristik arbeitet in Polynomzeit <math>\mathcal{O}(n^2)</math>. 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===
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.
<popup name="Programmablaufplan">
<center>
[[Bild:S3dobitt_HillClibing.jpg|300px]]
</center>
</popup>
===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.
<popup name="Programmablaufplan">
<center>
[[Bild:S3dobitt_TresholdAccepting.jpg|450px]]
</center>
</popup>
===Simulatet 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 treshold 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.
<popup name="Programmablaufplan">
<center>
[[Bild:S3dobitt_SimulatedAnnealing.jpg|400px]]
</center>
</popup>
In dem folgendem Video wird die Arbeitsweise des Simulated-annealing-Verfahren nochmal verdeutlicht:
<video type=youtube>iaq_Fpr4KZc</video>
===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.
<popup name="Programmablaufplan">
<center>
'''siehe Übung'''
</center>
</popup>
=Ü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 [http://www.axel-conrad.de/springer/springer.html#etilung 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.
<popup name="Ansatz">
[[Bild:S3dobitt_Ansatz_Aufgabe_2.png|thumb|center|500px|Ansatz mit Zerlegung, Start- und Endpunkt des jeweiligen Spielfeldes]]
</popup><br><br>
3. Erstellen Sie einen Programmablaufplan für den ''Sintflut-Algorithmus''. Sie können dabei Zettel und Stift benutzen oder Sie benutzen das Online Programm [http://www.gliffy.com/index-e.php "Gliffy"] (zum Speichern Registrierung nötig)
===Lösungen===
'''1.'''
<popup name="Lösung">
coming soon
</popup><br><br>
'''2.'''
<popup name="Lösung">
coming soon
</popup><br><br>
'''3.'''
<popup name="Lösung">
<code hidden>coming soon</code>
</popup><br><br>
=Literatur=
Christian Wagenknecht ''Algorithmen und Komplexität.'' Fachbuchverlag Leipzig, 2003, ISBN 3-446-22314-2, Seite 153-163
=Weblinks=
<sup>[1]</sup> [http://www.axel-conrad.de/springer/springer.html Axel Conrad]<br>
<sup>[2]</sup> [http://de.wikipedia.org/wiki/Tabu-Suche Wikipedia Tabu-Suche]<br>
<sup>[3]</sup> [http://de.wikipedia.org/wiki/Bergsteigeralgorithmus Wikipedia hill climbing]<br>
<sup>[4]</sup> [http://www-e.uni-magdeburg.de/mertens/TSP/node2.html Construction Heuristics]<br>
<sup>[5]</sup> [http://mume.fh-friedberg.de:6060/sirius/Sintflut/Start.html fh-friedberg Sintflut]<br>