Probabilistische Algorithmen WS15-16
Inhaltsverzeichnis |
http://programmingwiki.de/index.php?title=Probabilistische_Algorithmen_WS15-16
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.
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.
Die Klasse PP (probabilistic polynomial time) löst Entscheidungsprobleme in Polynomialzeit mit folgenden Fehlerwahrscheinlichkeiten: JA \leq 1/2; NEIN \leq 1/2 falsch.
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.
Der Las-Vegas Typ, wird nur zum Lösen von ZPP Problem genutzt, da sie nie falsche Ergebnisse liefern.
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 Heuristiken. Ähnlich zum P = NP-Problem existiert das P = BPP-Problem.