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|400px| 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".

==Anwendungsgebiete==

===Wirtschaftswissenschaften===

===Philosophie===

===Psychologie===

===Mathematik===

===Informatik===

==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?"''
[[Bild:Sipabrei_340px-Knight's_tour.svg.png|frame|eine ausgewählte Lösung für das Springerproblem]]
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|middle|200px|mögliche Züge für einen Springer]]



===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 eingeschränkten Backtracking algorithmus arbeitet 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 diese 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 ein Feld 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 vielleicht besser nachvollziehen zu können.

=Lokale Suche=

===Verzweigen und Begrenzen===

===Greedy-Heuristiken===

===Hill climbing===

===Threshold accepting===
==Simulated annealing==

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


Um die Schwachstelle des treshold accepting zu vermeiden entwickelten die Herren Scott Kirkpatrick, C. D. Gellat und M. P. Vecchi vom IBM-Forschungszentrum Yorktown Heights 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 das keine Unregelmäßigkeiten besitzt. 


<video type=youtube>KQYfaitQn7g</video>

===Tabu-Suche===

[[Bild:Simamuec_Fred_Glover.JPG|frame|rigth|Fred W. Glover]]
<br>

===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_Abbildung2.gif|middle|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 vegleichsweise 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>
[[Bild:Simamuec_Abbildung6.jpg|frame|left|erweiterte Möglichkeiten durch den 3-dimensionalen Raum]]
[[Bild:Simamuec_Abbildung8.jpg|frame|rigth|Schwachstelle im 3-dimensionalen Raum]]
</center>
</popup>

Zum Abschluss findet man [http://www.omnisophie.com/downloads/spektrum_mathematische_optimierung.wmv hier] noch ein sehenswertes Video von Tobias Scheuer, das den Sintflut-Algorithmus einfach und verständlich erklärt.

=Fazit=
=Übungsaufgaben=
=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://www-e.uni-magdeburg.de/mertens/TSP/node2.html Construction Heuristics]<br>
<sup>[3]</sup> [http://mume.fh-friedberg.de:6060/sirius/Sintflut/Start.html fh-friedberg Sintflut]<br>
<sup>[4]</sup> [http://www.omnisophie.com/index.html www.omnisophie.com]<br>