Probabilistische Algorithmen 1 SS10
Inhaltsverzeichnis |
Autoren:
- Mateusz Zwierz (simazwie@stud.hs-zigr.de)
- Hans Markwart (sihamark@stud.hs-zigr.de)
Einleitung
Pseudozufallszahlen
<eval> (randomize) (random 5) </eval>
Monte-Carlo-Algorithmen
Las-Vegas-Algorithmen
Allgemeines
Las Vegas Algorihtmen sind eine Unterart von probabilistischen Algorithmen, ähnlich wie Monte Carlo Algorithmen. Der Name wurde geprägt von László Babai, wegen der Ähnlichkeit zu Monte Carlo Algorithmen und Las Vegas auch bekannt ist für seinen Glücksspielcharakter. Babai erarbeitete diese Art von Algorithmen ca. 1979 um die Graphenisomorphie zu überprüfen.
Eigenschaften
Die wichtigste Unterschied zu Monte Carlo Algorithmen ist, dass anstatt Näherungswerte zurückzugeben, Las vegas Algorithmen immer ein richtiges Ergebnis zurückgeben. Darüber hinaus gibt es noch einen Spezialfall, unzwar wenn der Algorithmus in eine Sackgasse führt, aber da es heißt, dass ein Las Vegas Algorithmen immer ein richtiges Ergebnis zurückliefert muss man es schaffen aus einer Sackgasse zurückzukommen. Die Antwort ist ganz einfach, wenn der Algorithmus in eine Sackgasse führt wiederholt man einfach den Algorithmus noch einmal mit der gleichen Eingabe. Die Wahrscheinlichkeit, dass nach wiederholter Ausführung des Algorithmus kein Ergebnis gefunden wird wird mit zunehmender Anzahl der Wiederholungen immer kleiner.
Zeitkomplexität
Um die Zeitkomplexität zu berechnen muss man sich erst einmal die Funktionsweise eines Las Vegas Algorithmus anschauen. Ein Las Vegas Algorithmus widerholt sich solange selbst bis er ein Ergebnis liefert. Der Algorithmus ist probabilistisch, d.h. er arbeitet mit Zufallszahlen, d.h man kann nicht vorhersagen wie viele Schritte ein Algorithmus braucht um ein oder kein Ergebnis zu liefern. Darüberhinaus muss man den Algorithmus n-mal wiederholen bis man ein Egebnis bekommt. Da man nich vorhersagen kann ob der Algorithmus ein Ergebnis liefert, kann man auch nicht vorhersagen wie viele Wiederholungen man braucht und letztendlich kann man auch nicht sagen wie lange es dauert.
Ant Colony Optimization
Quellen
Weblinks
;[1] http://en.wikipedia.org/wiki/Marco_Dorigo ;[2] http://en.wikipedia.org/wiki/Las_Vegas_algorithm ;[3] http://en.wikipedia.org/wiki/Ant_colony_optimization
Literatur
; [1] Christian Wagenknecht : Algorithmen und Komplexität.- Fachbuchverlag Leipzig, 2003.- ISBN 3-446-22314-2 ; [2] Marco Dorigo, Thomas Stützle : Ant Colony Optimization.- A Bradford Book, The MIT Press, 2004.- ISBN 0-262-04219-3 ; [3] Juraj Hromkovic : Randomisierte Algorithmen.- B. G. Teubner Verlag, 20034.- ISBN 3-519-00470-4