Randomisierter Algorithmus

Ein randomisierter Algorithmus (auch stochastischer oder probabilistischer Algorithmus) verwendet – im Gegensatz zu einem deterministischen Algorithmus – Zufallsbits, um seinen Ablauf zu steuern. Es wird nicht verlangt, dass ein randomisierter Algorithmus immer effizient eine richtige Lösung findet. Randomisierte Algorithmen sind in vielen Fällen einfacher zu verstehen, einfacher zu implementieren und effizienter als deterministische Algorithmen für dasselbe Problem. Ein Beispiel, das dies zeigt, ist der AKS-Primzahltest, der zwar deterministisch ist, aber viel ineffizienter und viel schwieriger zu implementieren als beispielsweise der Primzahltest von Solovay und Strassen.

Algorithmustypen

Verschiedene Klassen der Algorithmen

Las-Vegas

Randomisierte Algorithmen, die nie ein falsches Ergebnis liefern, bezeichnet man auch als Las-Vegas-Algorithmen. Es gibt zwei Varianten von Las-Vegas-Algorithmen:

• Algorithmen, die immer das richtige Ergebnis liefern, deren Rechenzeit aber (bei ungünstiger Wahl der Zufallsbits) sehr groß werden kann. In vielen Fällen ist der Algorithmus nur im Erwartungsfall schnell, nicht aber im schlimmsten Fall. Ein Beispiel ist die Variante von Quicksort, bei der das Pivotelement zufällig gewählt wird. Die erwartete Rechenzeit beträgt $O(n \log n)$, bei ungünstiger Wahl der Zufallsbits werden dagegen $O(n^2)$ Schritte benötigt.
• Algorithmen, die versagen dürfen (= aufgeben dürfen), aber niemals ein falsches Ergebnis liefern dürfen. Die Qualität dieser Art von Algorithmen kann man durch eine obere Schranke für die Versagenswahrscheinlichkeit beschreiben.

Monte-Carlo

Randomisierte Algorithmen, die auch ein falsches Ergebnis liefern dürfen, bezeichnet man auch als Monte-Carlo-Algorithmen. Die Qualität von Monte-Carlo-Algorithmen kann man durch eine obere Schranke für die Fehlerwahrscheinlichkeit beschreiben.

Von randomisierten Algorithmen spricht man nur, wenn man den Erwartungswert der Rechenzeit und/oder die Fehler- bzw. Versagenswahrscheinlichkeit abschätzen kann. Algorithmen, bei denen nur intuitiv plausibel ist, dass sie gute Ergebnisse liefern, oder Algorithmen, bei denen man dies durch Experimente auf typischen Eingaben bewiesen hat, bezeichnet man dagegen als heuristische Algorithmen.

Bei der Analyse von erwarteter Rechenzeit und/oder Fehlerwahrscheinlichkeit geht man in der Regel davon aus, dass die Zufallsbits unabhängig erzeugt werden. In Implementierungen verwendet man anstelle von richtigen Zufallsbits üblicherweise Pseudozufallszahlen, die natürlich nicht mehr unabhängig sind. Dadurch ist es möglich, dass sich Implementierungen schlechter verhalten, als die Analyse erwarten lässt.

Fehlerarten von Monte-Carlo-Algorithmen für Entscheidungsprobleme

Bei Entscheidungsproblemen (Problemen, die durch Ja-Nein-Fragen beschrieben werden können) unterscheidet man ein- und zweiseitigen Fehler:

• Bei zweiseitigem Fehler dürfen Eingaben, bei denen die richtige Antwort Ja lautet, auch verworfen werden, und Eingaben, bei denen die richtige Antwort Nein lautet auch akzeptiert werden. Die Fehlerwahrscheinlichkeit muss in diesem Fall sinnvollerweise kleiner als 1/2 sein, da man mit einem Münzwurf unabhängig von der Eingabe die Fehlerwahrscheinlichkeit $1/2$ erreichen kann (dieser Ansatz ist offensichtlich keine sinnvolle Lösung für das betrachtete Problem).
• Bei einseitigem Fehler dürfen Eingaben, bei denen die richtige Antwort Ja lautet, auch verworfen werden, dagegen müssen Eingaben, bei denen die richtige Antwort Nein lautet verworfen werden. Hierbei sind Fehlerwahrscheinlichkeiten kleiner als 1 sinnvoll.

Zusammenhänge zwischen Las-Vegas- und Monte-Carlo-Algorithmen

Las-Vegas-Algorithmen lassen sich stets in Monte-Carlo-Algorithmen umformen: Die Ausgabe ? kann einfach als falsche Ausgabe interpretiert werden. Wenn eine obere Schranke $p(n)$ nur für den Erwartungswert der Rechenzeit des Las-Vegas-Algorithmus bekannt ist, kann man den Algorithmus nach $cp(n)$ Schritten abbrechen und ? ausgeben. Die Wahrscheinlichkeit, dass dies passiert, ist nach der Markow-Ungleichung durch 1/c beschränkt.

Da Monte-Carlo-Algorithmen falsche Lösungen ausgeben können und diese falschen Lösungen nicht extra gekennzeichnet werden müssen, ist es schwieriger, Monte-Carlo-Algorithmen in Las-Vegas-Algorithmen umzuformen. Dies ist möglich, wenn man zusätzlich einen Verifizierer für die Lösung hat, also einen Algorithmus, der zu einem Lösungsvorschlag testen kann, ob der Vorschlag korrekt ist. Man erhält einen Las-Vegas-Algorithmus, indem man den gegebenen Monte-Carlo-Algorithmus ausführt, anschließend mit dem Verifizierer überprüft, ob die berechnete Lösung korrekt ist, und dieses Verfahren so lange iteriert, bis eine korrekte Lösung berechnet wurde. Die worst-case-Rechenzeit dieses Ansatzes ist zwar nicht nach oben beschränkt, allerdings kann man den Erwartungswert der Anzahl der Iterationen nach oben abschätzen. Wenn man keinen Verifizierer zur Verfügung hat, ist im Allgemeinen nicht klar, wie man aus einem Monte-Carlo-Algorithmus einen Las-Vegas-Algorithmus konstruieren kann.

Komplexitätsklassen

Die Klasse PP

$Prob(M(w)=L(w)) > 1/2$

Typ: & Monte Carlo Algorithmus

Die Klasse PP (probabilistic polynomial) sind alle Sprachen L, so dass es eine probabilistische Turingmaschine M gibt, die polynomiell zeitbeschränkt ist und für alle w diese Formel gilt.

In dieser Klasse existiert ein beidseitiger Fehler. Die Wahrscheinlichkeit, dass das erzielte Ergebnis korrekt ist, liegt über 1/2.

Die Klasse BPP

$Prob(M(w)=L(w)) > 1/2 + e$

Typ: & Monte Carlo Algorithmus

Die Klasse BPP (bounded error probabilistic polynomial) sind alle Sprachen L, so dass es eine probabilistische Turingmaschine $M$ gibt, die polynomiell zeitbeschränkt ist und für alle w bei $e>0$ diese Formel gilt.

In dieser Klasse existiert ein beidseitiger Fehler. Die Wahrscheinlichkeit, dass das erzielte Ergebnis korrekt ist, liegt in einem bekannten Bereich.

Die Klasse RP

w ∈ L: $Prob(M(w)=1) > 1/2$

w ∉ L: $Prob(M(w)=0) = 1$

Typ: & Monte Carlo Algorithmus

Die Klasse RP (random polinomial) sind alle Sprachen L, so dass es eine probabilistische Turingmaschine M gibt, die polynomiell zeitbeschränkt ist und diese Formel gilt.

In dieser Klasse liegt ein einseitiger Fehler vor.

Die Klasse ZPP

w ∈ L: $Prob(M(w)=0) = 0$ $Prob(M(w)=1) > 1/2$

w ∉ L: $Prob(M(w)=1)= 0$ $Prob(M(w)=0) > 1/2$

Typ: & Las Vegas Algorithmus

Die Klasse ZPP (zero error probablistic polynomial) sind alle Sprachen L, so dass es eine probabilistische Turingmaschine M gibt, die polynomiell zeitbeschränkt ist und diese Formel gilt.

Verringerung der Fehler-/Versagenswahrscheinlichkeit (Probability Amplification)

Die Fehler- bzw. Versagenswahrscheinlichkeit von randomisierten Algorithmen kann durch unabhängiges Wiederholen verringert werden. Wenn man beispielsweise einen fehlerfreien Algorithmus mit einer Versagenswahrscheinlichkeit von 1/2 insgesamt $k$-mal laufen lässt, beträgt die Wahrscheinlichkeit, dass er in allen $k$ Iterationen versagt nur noch $(1/2)^k$. Wenn er in mindestens einer Iteration ein Ergebnis liefert, ist dies auch richtig, so dass es auch ausgegeben werden kann. Auf diese Weise kann man zeigen, dass jede konstante Versagenswahrscheinlichkeit aus dem Intervall $(0,1)$ (bis auf polynomielle Faktoren in der Rechenzeit) gleich gut ist. (Man überlegt sich leicht, dass die Versagenswahrscheinlichkeit $2^{-k}$ für zum Beispiel $k=100$ ein wirklich winzig kleine Versagenswahrscheinlichkeit ist; man müsste den Algorithmus im Durchschnitt $2^{100}$-mal laufen lassen, bis er das erste Mal versagt.) Derselbe Ansatz funktioniert für Algorithmen mit einseitigem Fehler. Bei Algorithmen mit zweiseitigem Fehler benötigt man dagegen eine Mehrheitsentscheidung, so dass die Analyse etwas schwieriger wird. Es ergibt sich aber wieder, dass jede konstante Fehlerwahrscheinlichkeit aus dem Intervall $(0,1/2)$ (bis auf polynomielle Faktoren in der Rechenzeit) gleich gut ist.

Derandomisierung

Unter Derandomisierung versteht man die Verringerung der Anzahl der Zufallsbits, die ein randomisierter Algorithmus benutzt. Dies ist aus dem folgenden Grund nützlich: Man kann jeden randomisierten Algorithmus deterministisch machen, indem man ihn für alle Belegungen der Zufallsbits simuliert. Allerdings bedeutet dies, dass bei der Verwendung von $c$ Zufallsbits die Rechenzeit um einen Faktor $2^c$ steigt, was in den meisten Fällen zu exponentieller Rechenzeit führt. Falls aber der Algorithmus bei Eingabelänge $n$ nur $O(\log n)$ Zufallsbits benötigt, führt dies nur zu einer polynomiellen Vergrößerung der Rechenzeit.

Ein Ansatz zur Derandomisierung besteht darin, genauer zu analysieren, wie der Algorithmus die Zufallsbits benutzt. Bei manchen randomisierten Algorithmen genügt es, dass die verwendeten Zufallsbits paarweise unabhängig sind. Man kann nun beispielsweise $n$ paarweise unabhängige Zufallsvariablen aus $O(\log n)$ vollständig unabhängigen Zufallsvariablen erzeugen. In einem zweiten Schritt kann man den Algorithmus mit dem zuvor beschriebenen Ansatz deterministisch machen.

Literatur

•  J. Hromkovič: Randomisierte Algorithmen: Methoden zum Entwurf von zufallsgesteuerten Systemen für Einsteiger. Vieweg+Teubner, 2004, ISBN 3-519-00470-4.
•  R. Motwani, P. Raghavan: Randomized Algorithms. Cambridge University Press, 1995, ISBN ISBN 0-521-47465-5.
•  I. Wegener: Komplexitätstheorie - Grenzen der Effizienz von Algorithmen. Springer, 2003, ISBN ISBN 3-540-00161-1.

Weblinks

• Übersicht über randomisierte Algorithmen