Probabilistische Algorithmen WS15-16

Wiki-Quelltext dieser Seite.

= Einleitung =
Oft können auch in "alltägliche" Fragestellungen zu Problemen mit zum Teil mindestens Exponentieller Laufzeit führen. Ein Beispiel ist die Zustellung von Lieferungen vom Lager zum Einzelhandel bei einer Handelskette. Fasst man die Filialen als Städte auf, und den Fahrer als Handelsreisenden, so hat man dies ins Traveling Salesman Problem (TSP) überführt. Folglich wird die Suche nach der exakten Lösung wahrscheinlich zu lange dauern. Ein Ausweg sind probabilistische Algorithmen.

= Herleitung =
Bisher behandelte Algorithmen würden nur einen starren Arbeitsableuf folge. Dies fürt bei gleichen Eingaben zu immer gleichen Ergebnissen, immer gleichem Speicherbedarf und immer gleicher Laufzeit. Der Ansatz der probabilistischen Algorithmen besteht darin diese Gleichheit durch Nutzung des Zufalls zu brechen. So kann bei der Suche in einem Baum einer zufälligen Kannte gefolgt werden, oder beim Färben eines Graphen ein zufälliger Nachbar. Dadurch liefert der Algorithmus nun bei gleichen Eingaben unterschiedliche Ergebnisse. Diese Algorithmen werden wiederum auf probabilistische Turingmaschine ausgeführt. Diese besitzen die Fähichkeit Arbeitsschritte mit Zufallsexperimenten zu steuern. Dies führt schließlich aber dazu das, dass Ergebnis des Algorithmus falsch sein kann. Dabei ist jedoch die Wahrscheinlichkeit stets bekannt.

= Klassifizierungen =
Analog zu deterministischen und nicht deterministischen Algorithmen gibt es auch bei probabilistischen Algorithmen Komplexitätsklassen. Des weiteren lassen sich verschiedene Typen von Algorithmen unterscheiden.

== Komplexitätsklassen ==
Die Einteilung der Komplexitätsklassen erfolgt anhand des Verhaltens bei Entscheidungsproblemen.

Die Klasse '''RP''' ''(random polynomial time)'' löst Entscheidungsprobleme in Polynomialzeit mit folgenden Fehlerwahrscheinlichkeiten: $NEIN = 0$; $JA \leq 1/2$.<br>
Die Klasse '''BPP''' ''(bounded-error probabilistic polynomial time)'' löst Entscheidungsprobleme in Polynomialzeit mit folgenden Fehlerwahrscheinlichkeiten: $JA$ und $NEIN \text{ jeweils} \leq 1/3$ falsch.<br>
Die Klasse '''PP''' ''(probabilistic polynomial time)'' löst Entscheidungsprobleme in Polynomialzeit mit folgenden Fehlerwahrscheinlichkeiten: $JA \leq 1/2$; $NEIN \leq 1/2$ falsch.<br>
Die Klasse '''ZPP''' ''(zero-error probabilistic polynomial time)'' löst Entscheidungsprobleme in Polynomialzeit mit folgenden Fehlerwahrscheinlichkeiten: $JA = NEIN = 0$; $Unbekannt/Abbruch \leq 1/2$.

== Algorithmustypen ==
Algorithmen, welche Probleme der oben genannten Komplexitätsklassen lösen lassen sich grundsätzlich in zwei Typen gliedern.<br>
Der '''Las-Vegas''' Typ, wird nur zum Lösen von ZPP Problem genutzt, da sie nie falsche Ergebnisse liefern.<br>
Der '''Monte-Carlo''' Typ wird für Probleme der Klassen RP, BPP und PP genutzt. Monte-Carlo Algorithmen können fehlerhafte ausgaben liefern, wobei die Wahrscheinlichkeit dessen stets bekannt ist.

= Zusammenfassung & Rückverknüpfung =
Probabilistische Algorithmen dienen u.a. zum schnelleren lösen komplexer Probleme. Sie lassen sich oft schnell formulieren ("wähle zufällig [...]"), ihre Fehlerwahrscheinlichkeiten zu bestimmen erfordert entsprechenden Aufwand. Dies ist jedoch die Abgrenzung zu den [[Hamilton_Kreise#Heuristiken | Heuristiken]]. Ähnlich zum [[P-NP-Problem_und_Näherungsverfahren#Offene_Fragen | P = NP-Problem]] existiert das P = BPP-Problem.

= Quellen =
* [http://liinwww.ira.uka.de/~thw/vl-rand-alg/ Vorlesung Randomisierte Algorithmen, Karlsruher Institut für Technologie (Folien 1 -- 3, Skript 1)]
* [https://en.wikipedia.org/wiki/RP_%28complexity%29]