Probabilistische Algorithmen WS15-16
Aus ProgrammingWiki
Inhaltsverzeichnis |
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. Fast 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 Lösungsmöglichkeit sind probabilistische Algorithmen.
Herleitung
Bisher behandelte Algorithmen folgten nur einem starrem Arbeitsablauf. Dies führt 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 gewählt werden. Dadurch liefert der Algorithmus nun bei gleichen Eingaben unterschiedliche Ergebnisse zurück. Diese Algorithmen werden wiederum auf probabilistische Turingmaschine ausgeführt. Diese besitzen die Fähigkeit, Arbeitsschritte mit Zufallsexperimenten zu steuern. Dies führt schließlich aber dazu das, dass Ergebnisse des Algorithmus ungültig sein können. Dabei ist jedoch die Wahrscheinlichkeit des Fehlerfalls 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$ falsch.
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 zurück geben, 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 und die Ergebnisse sind nicht immer gültig. Dies ist jedoch die Abgrenzung zu den Heuristiken. Ähnlich zum P = NP-Problem existiert das P = BPP-Problem.
Quellen
- Vorlesung Randomisierte Algorithmen, Karlsruher Institut für Technologie (Folien 1 -- 3, Skript 1)
- [1]
