Randomisierter Algorithmus
Bei randomisierten Algorithmen werden Zufallszahlen (in der Implementierung meist Pseudozufallszahlen) verwendet, um Algorithmen mit akzeptabler Laufzeit für komplizierte Probleme zu bekommen. Bei den meisten randomisierten Algorithmen "bezahlt" man allerdings für die gute Laufzeit damit, dass der Algorithmus mit einer beschränkten Wahrscheinlichkeit Fehler machen darf. Diese werden auch stochastische oder probabilistische Algorithmen genannt, allerdings sind nicht alle randomisierten Algorithmen probabilistisch (siehe unten).
Ob ein Fehler auftritt oder nicht, hängt sowohl von der Eingabe (der Instanz des Problems) als auch von der Zufallszahl ab. Dadurch kann man durch wiederholtes Durchführen des Algorithmus (mit verschiedenen Zufallszahlen) das korrekte Ergebnis als das "mehrheitliche Ergebnis" ermitteln. Die genauen Wahrscheinlichkeiten dabei hängen von Details des Algorithmus ab, die allgemeine Idee ist jedoch Folgende:
- Voraussetzung: die Wahrscheinlichkeit für einen Fehler muss insgesamt (Ja- und Nein-Antworten) < 1 / 2 sein, sonst funktioniert die "Verstärkung der Wahrscheinlichkeit für die korrekten Antwort" (engl. probability amplification) nicht
- Bei gleicher Eingabe ist die Wahrscheinlichkeit für einen Fehler beim ersten Durchlauf des Algorithmus also < 1 / 2, beim zweiten < 1 / 22 und beim n-ten Durchlauf < 1 / 2n, also ziemlich klein, meist vernachlässigbar
Also muss die Anzahl der Durchläufe des Algorithmus so gewählt werden, dass der entstehende Fehler vernachlässigbar ist. Deshalb werden randomisierte Algorithmen in Fällen angewendet, in denen die Laufzeit nicht zu hoch sein soll und eine gewisse Fehlerwahrscheinlichkeit tolerierbar ist.
Es gibt verschiedene Varianten von erlaubten Fehlern:
- einseitiger Fehler: Hier darf nur bei einer der möglichen Ausgaben (ja/nein) ein Fehler -- mit Wahrscheinlichkeit < 1 -- auftreten. Beispielsweise darf der Miller-Rabin-Test für die Primalität einer natürlichen Zahl zwar fälschlicherweise behaupten, die Zahl sei prim, wenn der Algorithmus aber ausgibt, dass es sich um eine zusammengesetzte Zahl handelt, dann ist diese Ausgabe garantiert korrekt. Wenn nach mehrfacher Ausführung des Algorithmus das Ergebnis jedesmal "Primzahl" lautete, kann man jedoch mit hoher Wahrscheinlichkeit davon ausgehen, dass dies zutrifft. (Für die genaue Abschätzung der Wahrscheinlichkeit wird in diesem Fall ein Ergebnis aus der Zahlentheorie benötigt).
- Monte-Carlo-Algorithmen gehören zu den Algorithmen mit einseitigem Fehler.
- Beim zweiseitiger Fehler darf sowohl die ja- als auch die nein-Antwort falsch sein. Um damit eine Gesamt-Fehlerwahrscheinlichkeit < 1 / 2 zu erreichen, muss die Wahrscheinlichkeit für jeden der beiden erlaubten Fehler < 1 / 2 sein, also kann man bei jeder Antwort davon ausgehen, dass sie mit einer Wahrscheinlichkeit von mehr als 50% korrekt ist. Damit ist analog zu den einseitigen Fehlern eine probability amplification möglich.
Eine Klasse von randomisierten Algorithmen, die nicht zu den probabilistischen Algorithmen gehören, sind die Las-Vegas-Algorithmen, die immer die korrekte Antwort liefern. Hier bestimmt die Zufallszahl die Laufzeit, es kann also vorkommen, dass ein Las-Vegas-Algorithmus sehr lang braucht, um das Ergebnis zu ermitteln.
Weblinks
Übersicht über randomisierten Algorithmen