AuK/Näherungsverfahren 1 SS10

Wiki-Quelltext dieser Seite.

<language>Java</language>
'''Autoren:'''
#Patrick Breite  ([mailto:sipabrei@stud.hs-zigr.de sipabrei@stud.hs-zigr.de])
#Marcel Mücke  ([mailto:simamuec@stud.hs-zigr.de simamuec@stud.hs-zigr.de])


=Einführung=

[[Bild:Simamuec_Show_wss_img.jpeg|center| Effizienz von Algorithmen]]

Das Thema der Effizienten Näherungsalgorithmen baut zum teil auf andere Themenkomplexe auf,die sehr zu empfehlen sind:
<br> [[AuK/Greedy-Algorithmen_SS10|Greedy-Algorithmen]]
<br> [[AuK/Probabilistische_Algorithmen_SS10|Probabilistische Algorithmen]]
<br> [[AuK/P-NP-Problem_SS10|P-NP-Problem]]

=Heuristiken=
=Begriff=

Der Begriff Heuristik ist aus dem altgriechischen Wort "heuriskien" abgeleitet und bedeutet so viel wie "(auf)-finden" bzw. "entdecken".
=Motivation=
=Anwendungsgebiete=

===Wirtschaftswissenschaften===

===Philosophie===

===Psychologie===

===Mathematik===


===Informatik===

Heuristiken werden in der Informatik hauptsächlihc genutzt um mit möglichst geringem Rechenaufwand ein meist recht komplexes Problem zu lösen und eine zwar nicht optimale, aber dennoch zulässige Lösung zu erhalten. Es wird also im gegensatz zu anderen Algorithmen nicht garantiert, dass eine optimale Lösung errechnet wird, wodurch sich der Rechenaufwand und die somit benötigte Zeit meistens stark reduzieren und manchmal sogar fast minimieren. Bekannte Heuristiken sind zum Beispiel Simulated annealing und Greedy-Heuristiken, wie zum Beispiel die Nearest neighbour heuristic oder die Farthest insertion heuristic.

=Springerproblem=



===Erläuterung des Springerproblems===

Vor mehr als 200 Jahren formulierte der Schweizer Mathematiker Leonhard Euler erstmals das Problem des ''Rösselsprungs'', auch Springerproblem genannt:

''"Gibts es für einen Springer einen Weg, der jedes Feld eines n x n-Schachbrettes genau einmal besucht?"''

Um diese Problem lösen zu können, muss bekannt sein, dass ein Springer eine Schachfigur ist, welche von ihrem aktuellem Feld <math>A(x_1 , y_1)</math> zu einem Feld <math>B(x_2 , y_2)</math> bewegt werden kann, wobei zu beachten ist das entweder 


<math>|x_1 - x_2| = 1</math> und <math>|y_1 - y_2| = 2</math>

oder

<math>|x_1 - x_2| = 2</math> und <math>|y_1 - y_2| = 1</math>   

für die Bewegungen des Springers gelten muss.

Auf dem folgenden Bild sind die möglichen Züge eines Springers zu erkennen.

[[Bild:Sipabrei_Sprungmoeglichkeiten.gif|thumb|left|250px|mögliche Züge für einen Springer]]

[[Bild:Simamuec_Springertour.gif|thumb|left|250px|eine ausgewählte Lösung für das Springerproblem]]
























.

===Lösung mit Backtracking===

Lange Zeit war für die Lösung des sogenannten ''Rösselsprungs'' nur der Naive Algorithmus mit Backtracking bekannt, wodurch ein Exponentieller Aufwand Zeitaufwand entsteht. Der Versuch mit diesem Algorithmus eine Lösung für ein n x n-Schachbrett mit <math>n>7</math> zu finden ist nur mit enormem Zeitaufwand zu lösen, da bei einem 8 x 8-Schachbrett bereits über 3 Milliarden Züge überprüft werden müssten um mit einem reinen Backtracking Algorithmus zum Ziel zu gelangen.

Ein Applet welches mit einem Backtracking Algorithmus und verschiedenen anderen Algorithmen arbeitet um den Zeitaufwand zu verringern finden sie [http://w1.859.telia.com/~u85905224/knight/dknight.htm hier]. Es ist zu beachten dass in diesem Algorithmus bestimmte Sackgassen schon vor dem Programmstart ausgeschlossen werden, um die Lösung dieses 8 x 8-Schachbretts in einer möglichst kurzen Zeit zu gewährleisten.

===Warnsdorff Heuristik=== 

Die Warnsdorff Heuristik wurde 1823 von H.C. Wanrsdorff entwickelt und der Grundgedanke ist, dass Felder mit wenigen Folgefeldern schnell isoliert werden und so nicht mehr besucht werden können. 

Warnsdorff entwickelte desshalb folgende Regeln:

1. Ziehe auf das Feld mit der geringsten Zahl an noch zu erreichenden unbesuchten Folgefelder.

2. Wenn 2 oder mehr Felder die selbe Anzahl an noch zu erreichenden unbesuchten Folgefelder aufweisen ziehe auf das Feld, welches zuletzt (oder zuerst) betrachtet wurde.

Wenn man Beispielsweise die 1. Regel auf ein  anwendet auf ein noch leeres Schachbrett sieht dies folgendermaßen aus:
<code id="4c0e41b99e49d" hidden>
 int[][] schachbrett = new int[8][8];
schachbrett[0][0]=2;
schachbrett[7][7]=2;
schachbrett[0][7]=2;
schachbrett[7][0]=2;

schachbrett[1][6]=4;
schachbrett[1][1]=4;
schachbrett[6][1]=4;
schachbrett[6][6]=4;

schachbrett[1][0]=3;
schachbrett[0][6]=3;
schachbrett[6][7]=3;
schachbrett[0][1]=3;
schachbrett[1][7]=3;
schachbrett[7][1]=3;
schachbrett[6][0]=3;
schachbrett[7][6]=3;

 for(int j=2;j<6;j++){
   for(int i=2;i<6;i++){
schachbrett[j][i]=8;
schachbrett[1][i]=6;
schachbrett[6][i]=6;
schachbrett[i][1]=6;
schachbrett[i][6]=6;
schachbrett[0][i]=4;
schachbrett[i][0]=4;
schachbrett[7][i]=4;
schachbrett[i][7]=4;
   }
 }
for(int i=0;i<8;i++){
  System.out.println();
	  for (int j = 0; j < 8; j++) {
		System.out.print(schachbrett[i][j] + " ");
	  }
}
</code>
<eval id="4c0e16e3c7564">
</eval>
Die Heuristik von Warnsdorff garantiert jedoch nur eine näherungsweise Lösung des Springerproblems, da bei größeren Schachbrettern nicht alle Sackgassen gemieden werden, was für Warnsdorff unmöglich zu untersuchen war, da er noch keine Computer zur Verfügung gehabt hat, welche diese Springertour auf beispielsweise einem 100x100 großem Schachbrett errechnen. 

Weiterhin kann man zeigen, dass es für Schachbretter der Größe <math>n \le 4</math> keine Lösungen existieren, da der Springer immer in einer Sackgasse landet, egal von wo er startet. Sie können dies auch in dem unten verlinktem Java Programm austesten. 

Einen kurzen Algorithmus, zur Lösung des Springerpoblems mit der Warnsdorff Heuristik, finden Sie in diesem [[AuK/Näherungsverfahren_1_SS10/Java1|Java Programm]] und ebenfalls ist [http://web.telia.com/~u85905224/knight/dWarnsd.htm dieses Applet] zu empfehlen, wenn man selbst einen Weg für das Springerproblem finden möchte und um den Weg des Springers vielleicht besser nachvollziehen zu können.

===Modifikationen der Warnsdorff Heuristik===

Es ist möglich eine Heuristic zu modifizieren um eventuell eine Verbessserung zu erreichen, jedoch kann man bei Heuristiken nur sehr schwer nachweisen in wieweit die Heuristik sich verbessert hat, da sehr umständliche und komplizierte Tests durchgeführt werden müssen.

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.

[[Bild:Sipabrei_L_loesung.gif|thumb|right|150 px|Ein Beispiel für das Zerlegen eines Schachbretts]]
===Algorithmus von Axel Conrad===

1992 entwickelte eine Schülergruppe im Rahmen des Bundeswettstreits für Informatik, einen Algorithmus für die Lösung des Springerproblems in <math>O(n^2)</math>.<br> Der Conrad-Algorithmus ist nach einem seiner Erfinder Axel Conrad benannt und stützt sich auf das Prinzig von [[AuK/Teile_und_Herrsche_1_SS10 | Teile und Herrsche]] auf. Der Conrad-Algorithmus 
schafft es ein Schachbrett beliebiger Größe exakt zu lösen und zwar indem man ein 5x5 große Teile zerlegt. Wenn die Seitenlänge des Schachbretts kein Vielfaches von 5 ist, entstehen L-förmige Teilbretter am Rand und in der Mitte ergibt sich ein 6x6 oder 9x9 großes Feld. Da es möglich ist von einem dieser kleineren Teile in einen anliegenden zu springen kann man so alle einzelnen kleineren Schachbretter durchqueren und eine Springertour finden. Bei der entwicklung dieses Algorithmus von Axel Conrad und sineen Mitschülern entstand ein Algorithmus mit dem sich sogar für ein Schachbrett der Größe 100.000.000 x 123.456.789 innerhalb einer Sekunde eine Spingertour berechnen lässt. Axel Conrad gibt auf [http://www.axel-conrad.de/springer/springer.html seiner Website] unter anderem auch eine Lösung für nicht quadratische Schachbretter an. Axel Conrad und Diana Schmied gelang es sogar im Jahr 1998 einen Algorithmus zu entwickeln, welcher in der Lage ist ein <math>n-</math>dimensionales Schachbrett zu lösen.

=Lokale Suche=

===Verzweigen und Begrenzen===


Der ihnen schon bekannte branch and bound Algorithmus (siehe [[AuK/Verzweigen_und_beschränken_SS10 | Verzweigen und beschränken SS10]]) wird folgendermaßen abgewandelt:

1. Anstatt die eigentliche Schrankenfunktion zu berechnen wird diese durch eine  mehr oder weniger grobe Schätzfunktion ersetzt

2. Die Bound-Berechnung entfällt -> man akzeptiert also, dass nicht wirklich eine Schranke berechnet wurde

Das Ergebnis ist ein Näherungsalgorithmus, dessen Ergebnis zwar vom Optimum abweichen wird, jedoch kann man in den meisten Fällen sagen, dass die Ergebnisse zufriedenstellend bis gut sind, also in der Regel eine kaum nennenswerte Abweichung vom Optimums aufzeigen.

===Greedy-Heuristiken===

Der Unterschied zwischen einer Greedy-Heuristik und einem Greedy-Verfahren ist hauptsächlich die Qualität der Lösungen, da ein Greedy-Verfahren eine exakte Lösung und eine Greedy-Heuristik nur eine Näherungslösung, welche jedoch in den meisten Fällen recht nah an der exakten Lösung liegt, liefert. Ein Greedy-Verfahren benötigt, anders als eine Greedy-Heuristik, zur Angabe einer exakten Lösung ein Matroid als zugrunde liegende algebraische Struktur. Es ist beispielsweise beim Bruchteil-Rucksackproblem der Fall, dass die zugrunde liegende algebraische Struktur ein Matroid ist, jedoch nicht beim 0/1-Rucksackproblem. Wendet man trotz dem nicht vorhandenem Matroid beim 0/1-Rucksackproblem ein Greedy-Verfahren an, so erhält man eine Näherungslösung und man spricht dann von einer Greedy-Heuristik.

Greedy-Heuristiken zeichnen sich dadruch aus, dass sie immer nach einem lokalem Optimum suchen und weder bereit sind eine Entscheidung zu revidieren noch eine lokale Verschlechterung zu ermöglichen.

Wenn man zum Beispiel eine Greedy-Heuristik zur Lösung des TSP verwenden möchte so wird man versuchen gerade den Knoten einzubinden, der den größten Gewinn, also hier die kürzeste Rundreise beschert. Beispielsweise könnte man auf die Idee kommen immer den Knoten einzubinden, welcher dem gerade betrachteten am nächsten liegt. Diese Strategie nennt man ''nearest neighbor heuristic''. Sie ist jedoch in den meisten Fällen nicht wirklich hilfreich, da die Ergebnisse meist unbrauchbar sind oder zumindest ziemlich weit vom Optimum abweichen. Bessere Resultate erhält man zum Beispiel mit der ''farthest insertion''. Bei der ''farthest insertion'' beginnt man die Knoten mit dem geringstem Abstand zu verbinden und erweitert die Tour dann um den Knoten, dessen Minimalabstand zu einem bereits auf der Rundreise liegendem Knoten maximal ist. Diese Technik führt zu ebenso guten Ergebnissen wie die ''random insertion'', bei der ein unbenutzter Knoten zufällig ausgewählt wird und so integriert wird, dass die daraus resultierende Länge der Rundreise minimal wird. Ein weiteres Greedy-Verfahren ist die ''nearest insertion''. Bei diesem Verfahren wird der Knoten eingebunden, der die geringste Verlängerung der daraus resultierenden Teilroute zur Folge hat. Es wurde mitlerweile bewiesen, dass größere Schritte besser sind als kleine, desshalb werden also anstelle kleine Veränderungen beim TSP zu betrachten möglichst große gewählt. Dies führt zu einem weiteren Greedy-Verfahren, der ''best insertion''. Bei diesem Verfahren geht man vor wie bei einem Bombenabwurf, es werden in einem kreisförmigen Gebiet alle Städte zertsört und dann nacheinander wieder aufgebaut, wobei man sie mittels der Farthest-Insertion-Methode in den Rundweg integriert, was ''best insertion'' genannt wird. Nach diesem Verfahren aus dem ''Ruin-and-recreate''-Bereich ist die entstandene Länge des Rundweges im allgemeinen kürzer als vorher.

Zwei schöne Applets für Greedy Heuristiken finden sie auf [http://www-e.uni-magdeburg.de/mertens/TSP/node2.html dieser Seite] von Stephan Mertens.

===Hill climbing===


Beim Hill-Climbing, auch Bergsteigeralgorithmus genannt, wird von einer beliebigen Startlösung aus versucht aus den in der nähe befindlichen Lösungen die bessere auszuwählen, bis keine Verbesserung mehr möglich ist.<br> Am Beispiel eines Bergsteigers bedeutet dies, das ein Bergsteiger auf einer beliebigen Postion in der Landschaft immer Versucht eine höhere Position zu erreichen. Dabei wird auch schnell der Schwachpunkt des Hill-Climbing-Algorithmus ersichtlich, denn er endet oft in einem lokalen Maximum. Bezogen auf den Bergsteiger bedeutet dies, wenn zwischen seiner aktuell höchsten (lokalen) Position und einer höheren (globalen) Position ein Tal liegt, hat er somit keine Möglichkeit diese zu erreichen.

Das Problem kann aber mit verschiedenen Ansätzen minimiert werden:
* mehrmaliges Ausführen der Methode
* mehrere Bergsteiger mit verschiedenen Startpunkten
* zufällige große Sprünge und danach erneutes Anwenden der Methode


<popup name="Programmablaufplan Hill-Climbing">
<center>
[[Bild:Simamuec_Hill-Climbing1.png|middle|250px| Hill-Climbing]]
</center>
</popup>

===Threshold accepting===


1990 veröffentlichten Dueck und Scheuer ihr Buch über die Schwellenakzeptanz (''Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing''). Der Threshold accepting Algorithmus befasst sich hauptsächlich damit einen gewisse Tolleranzgrenze <math>T</math> einzurichten um mögliche zwischenzeitliche Verschlechterungen zu ermöglichen, was zu besseren Näherungslösungen führen kann. Man würde also überprüfen, ob eine lokale Veränderung nach einer Bewertung um mehr als <math>T</math> von der vorhergehenden Lösung abweicht und sie verwerfen insofern dies der Fall ist. Es wird somit zu anfang ein <math>T</math> gewählt welches möglichst groß ist, wobei auch ein <math>T</math> gewält werden kann durch welches anfangs kaum Beschränkungen entstehen, da wenn über längere Zeit keine Verbesserungen eintretetn <math>T</math> langsam auf null gesenkt wird. Der Nachteil ist, dass wenn zum Beispiel der Bergsteiger aus dem zuvor beschriebenem Problem beim hill-climbing einen Nebengipfel erreicht hat und <math>T</math> bereits gesenkt wurde, so gibt es keine Möglichkeit für den Bergsteiger den höchsten Gipfel zu erreichen.


Der Unterschied zum simulated annealing besteht in der Behandlung der Verschlechterungen bei den neuen gegenüber den alten Lösungen.
Während beim simulated annealing mit einer bestimmten berechneten Wahrscheinlichkeit entschieden wird ob eine Verschlechterung akzeptiert wird oder nicht, wird beim threshold accepting jede Verschlechterung akzeptiert solange sie <math>T</math> nicht überschreitet.<br>Durch das wegfallen einer komplexen Berechnung für die Zufallszahl und die Exponentialfunktion ergibt sich ein besseres Laufzeitverhalten in Bezug auf die Geschwindigkeit. Beim threshold accepting können in der gleichen Zeit mehr Lösungen durchprobiert werden und gleichzeitig liefert er meist qualitativ bessere Lösungen.

==Simulated annealing===

[[Bild:Simamuec_SKmugshot.jpg|frame|rigth| Scott Kirkpatrick]]

Die Herren '''Scott Kirkpatrick''', '''Charles D. Gelatt''' und '''Mario P. Vecchi''' vom IBM-Forschungszentrum Yorktown Heights entwickelten  1983 das sogenannte simulated annealing, was übersetzt '''simuliertes langsames Abkühlen''' bedeutet.
<br>Dieses Verfahren wird hauptsächlich in der Werkstofftechnik eingesetzt. Bei diesem Verfahren werden Metalle erhitzt und dabei werden die atomaren Teilchen aus ihrer festen Gitterstruktur gelöst. Beim langsamen abkühlen verbinden sich die Teilchen wieder zu einer festeren und geordneteren Gitterstruktur. Dadurch erhält man Metalle mit verbesserten Eigenschaften(weniger Unregelmäßigkeiten in der Struktur). Zur Herstellung von Mikroprozessoren und Speicherbausteinen werden z.B. Materiallien wie Silizium benötigt welche keine Unregelmäßigkeiten besitzten. 

Der Algorithmus baut auf dem sogenannten Metropolisalgorithmus auf, der 1953 von Nicholas Metropolis et al. publiziert wurde. Der Metropolisalgotithmus ist eine '''Monte-Carlo-Methode''' (siehe [[AuK/Probabilistische_Algorithmen_SS10|Probabilistische Algorithmen]]) zur Erzeugung von Zuständen eines Systems basierend auf der Boltzmann-Verteilung. Im Gegensatz zum treshold accepting wird trotz Überschreiten der festen Toleranzschwelle <math>T</math> mit einer bestimmten Wahrscheinlichkeit, mittels Zufallszahl und Exponetialfunktion, zufällig entschieden, den Lösungsvorschlag doch zuzulassen. Diese Wahrscheinlichkeit richtet sich nach der Größe der Überschreitung von <math>T</math>. Sehr große Überschreitungen werden dabei deutlich seltener zugelassen als kleinere.

Beim simulated annealing wird nun zusätzlich noch <math>T</math> immer weiter abgesenkt. Dieses Verfahren wir hauptsächlich dazu benutzt ein globales Minimum zu finden. Bezogen auf das beispiel des Bergsteigers bedeutet dies, das er nun versucht in das tiefste Tal hinabzusteigen. Dabei kann es passieren das der Bergsteiger sich in einem lokalen Minimum (Tal) verfängt und erst wieder durch eine große Überschreitung von <math>T</math> frei kommt.


<popup name="Programmablaufplan Simulated Annealing">
<center>
[[Bild:Simamuec_Simulated_annealing1.png|middle|400px| simulated annealing]]
</center>
</popup>


Das untere Video verdeutlicht nochmal die Arbeitsweise des Algorithmus.
<video type=youtube>KQYfaitQn7g</video>

===Tabu-Suche===
[[Bild:Simamuec_Fred_Glover.JPG| frame|Fred W. Glover]]

Der Algorithmus der Tabu-Suche wurde von Fred Glover entwickelt und erfährt seitdem immer wieder Verbesserungen.
Die zugrunde liegende Idee basiert darauf, dass es bei den oben genannten Algorithmen (treshold accepting und simulated annealing) vorkommen kann das ein oder mehrere Schritte rückgängig gemacht werden. Um dies zu vermeiden werden die vorangegangen <math>x</math> Lösungen bzw. Schritte in einer sogenannten Tabu-Liste gespeichert, die mehrere Warteschlangen implementieren kann. Stimmt ein neuer 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.



Ein passendes Java-Applet zum besseren Verständnis befindet sich [http://siebn.de/other/tabusearch/ hier].






[[AuK/Näherungsverfahren_1_SS10/Video_Sintflut| .]]

===Sintflut-Algorithmus===

[[Bild:GD-3.jpg|frame|Gunter Dueck]]


Der Sintflutalgorithmus wurde 1993 von Gunter Dueck und Tobias Scheuer bei der Firma IBM in Heidelberg entwickelt.
Er ist eine Weiterentwicklung bzw. Vereinfachung des weiter oben beschriebenen "Simulated Annealing"-Algorithmus und hat im Gegensatz zu den Treshold-accepting-Verfahren keinen Schwellwert der für jeden Schritt vorgegeben ist sondern eine globale untere Schranke die sich langsam aber stetig erhöht. Dabei spielt es keine Rolle, ob der nächste Schritt näher oder weiter entfernt von der Lösung gegenüber dem vorigen Schritt liegt, solange die globale Schranke nicht unterschritten wird. Im laufe des Prozesses wird dadurch 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.

Am besten lässt sich dies am Beispiel des Bergsteigers erklären, der sich versucht während einer steigenden Flut auf den in seiner  Umgebung befindlichen 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 Wanderer ständig in Bewegung. Er merkt er sich dabei den höchsten Punkt den er bisher erreicht hat. Es ist ihm möglich jeden Gipfel und jedes Tal zu beschreiten, solange er sich über der Wasserlinie bewegt. Ist er komplett von den Wassermassen umgeben und kein Schritt mehr möglich, hat er den höchsten lokalen Punkt erreicht. 
<br>Die untere Abbildung zeigt die Anwendung im 2-dimensionalen Raum, wobei der '''rote Punkt''' den Wanderer, der '''gelbe Punkt''' den bisher höchsten lokalen Punkt und die '''blaue Linie''' den aktuellen Wasserstand darstellen.

[[Bild:Simamuec_Abbildung1.gif| frame| center| Sintflut in 2D]]<br>

<popup name="Programmablaufplan Sintflut-Algorithmus">
<center>
[[Bild:Simamuec_Sintflut-Algorithmus.png|250px| Sintflutalgorithmus]]
</center>
</popup>
Ein passende Java-Applet befindet sich [http://mume.fh-friedberg.de:6060/sirius/Sintflut/Html/Visualisierung2D.html hier].


Der Sintflut-Algorithmus arbeitet, wie auch treshold accepting, im Gegensatz zum simulated annealing deterministisch.
Bei geschickter Implementierung arbeiet er etwas schneller als die beiden anderen Verfahren, wobei er in der Qualität seiner Lösungen nicht ganz so stabil ist. Dieser vermeintliche Nachteil ist einfach zu erklären.

Wird die Schrittgröße des Wanderers zu groß gewählt, kann es passieren das er mit einem einzigen Schritt den Gipfel überspringt.
Ist die Schrittgröße stattdessen zu klein, steigt das Wasser zu schnell um möglichst viele verschiedene Punkte zu beschreiten.
Das bedeutet das der Algorithmus stark von der Schrittgröße abhängig ist.
Des Weiteren kann es passieren das der Wanderer auf einem niedrigeren Gipfel(lokales Maximum) von den Wassermassen eingeschlossen wird und damit keine Möglichkeit mehr hat auf den höheren Gipfel(globales Maximum) zu gelangen.

<br>[[Bild:Simamuec_Abbildung3.gif| frame|center| Schwachstelle des Sintflut-Algorithmus]] 

Dieser Nachteil wird mit steigender Anzahl der Dimensionen verkleinert. Schon bei der Anwendung im 3-dimensionalen Raum 
ergeben sich für den Wanderer mehr Möglichkeiten sich zu bewegen. Anstatt nur nach rechts oder links zu gehen kann er sich nun ebenfalls nach vorn und nach hinten bewegen, wobei auch hier die Wahrscheinlichkleit nur ein lokales Maximum zu erreichen vergleichsweise hoch ist. Die eigentliche Anwendung des Sintflut-Algorithmus liegt aber sowieso hauptsächlich im hochdimensionalen Raum mit 100 Dimensionen und mehr z.b. beim TSP.

  
<popup name="Anwendung des Sintflut-Algorithmus im 3-dimensionalen Raum">
<center>
<gallery widths="500" heights="300" perrow="2" caption="Sintflut-Algorithmus">
Bild:Simamuec_Abbildung6.jpg| erweiterte Möglichkeiten durch den 3-dimensionalen Raum
Bild:Simamuec_Abbildung8.jpg| Schwachstelle auch im 3-dimensionalen Raum
</gallery>
</center>
</popup>

Zum Abschluss nun noch die Möglichkeit ein sehenswertes Video von Tobias Scheuer, das den Sintflut-Algorithmus einfach und verständlich erklärt anzuschauen. Dieser Link ist aber irgendwo auf dieser Seite versteckt (kleiner Hinweis: Am besten immer direkt auf den Punkt kommen.) Viel Spass beim entdecken, es lohnt sich.

=Fazit=

Man kann sagen, dass Heuristiken in den meisten Fällen zwar keine Optimalen Lösungen zurückgeben, aber da meistens die Lösungen nur sehr geringfügig von einem Optimum abweichen und desshalb sehr nützliche Hilfsmittel sind um bei extrem komplexen Problemen mit möglichst kleinem Aufwand eine gute bis fast Optimale Lösung zu erhalten.

=Übungsaufgaben=

1. Überlegen Sie wie man es erreichen kann, dass beim verwenden der Warnsdorff-Heuristik bei der gleichen Startposition unterschiedliche Wege für den Springer entstehen und verändern Sie die Methode "findeBestenWeg" in diesem Programm.
<document>Sipabrei_AuK_Übung_norm.zip</document>

2. Entwerfen Sie für den treshold-accepting-algorithmus einen Programmablaufplan mithilfe des kostenlosen Programmes [http://www.gso-koeln.de/papdesigner/Download.html PapDesigner](Bitte nur die gepackte exe herunterladen, da nur diese auf den Hochschulrechner ohne Admin-Rechte funktioniert).

3. Experimentieren Sie mit den verlinkten Applets über die Greedy-heuristiken und das Springerproblem

[[AuK/Näherungsverfahren_1_SS10/Loesungen |Lösungen]]

=Quellen=

==Literatur==

; [1] Christian Wagenknecht
: Algorithmen und Komplexität,- Fachbuchverlag Leipzig, 2003.- ISBN 3-446-22314-2
; [2] Doina Logofatu
: Grundlegende Algorithmen mit Java - Vom Algorithmus zum fertigen Programm: Lern- und Arbeitsbuch für Informatiker und Mathematiker ,- Verlag Vieweg+Teubner, 2007.- ISBN 3834803693

==Weblinks==
<sup>[1]</sup> [http://de.wikipedia.org/wiki/Heuristik Wikipedia Heuristik]<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>
<sup>[6]</sup> [http://www.omnisophie.com/index.html www.omnisophie.com]<br>
<sup>[7]</sup> [http://siebn.de/other/tabusearch/ www.siebn.de]<br>
<sup>[8]</sup> [http://www.axel-conrad.de/springer/springer.html Axel Conrad]<br>