Las-Vegas-Algorithmen

Aus ProgrammingWiki

von Gruppe 1

Las-Vegas-Algorithmen sind randomisierte Algorithmen, die uns garantieren, dass jede berechnete Ausgabe korrekt ist. somist ist ein falsches Resultat in diesem Modell der randomisierten Berechnung verboten. In der Literatur benutzt man aber zwei unterschiedliche Modelle der Las-Vegas-Algorithmen und zwar abhängig davon, ob auch eine Antwort "?" mit der Bedeutung "Ich weiß es nicht" bzw. "In diesem Lauf war ich nicht im Stande, die richtige Lösung zu berechnen", zulässig ist.

Bei der ersten, strengeren Möglichkeit, definiert sich ein Algorithmus A als Las-Vegas-Algorithmus für die Berechnung der Funktion F, wenn für jede Eingabe x von F gilt:

.

Bei dieser Definition des Las-Vegas-Algorithmus wird immer die erwartete Komplexität der Algorithmen untersucht, etwa die erwartete Zeitkomplexität . Hier ist es zu erwarten, dass man unterschiedlich lange Läufe auf einer Eingabe erhält. Wären nämlich alle Läufe ungefähr gleich lang, könnte man einfach einen genauso effizienten deterministischen Algorithmus entwerfen, indem immer ein fester Lauf des randomisierten Algorithmus simuliert wird. Da die Zufallsbits nur Einfluss auf die Vorgehensweise des Algorithmus haben, liefert der Las-Vegas-Algorithmus immer ein korrektes Ergebnis, wenn er terminiert. Die Zeitkomplexität ist in diesem Fall eine Zufallsvariable. Ein bekanntes Beispiel ist der Random-Quicksort-Algorithmus, der sein Pivotelement zufällig wählt, dessen Ausgabe aber immer sortiert ist. Dadurch lassen sich keine Best-Case und Worst-Case-Beispiele mehr konstruieren. Aber der Worst-Case kann natürlich auch dann noch eintretten, wenn zufällig das schlechteste Pivot-Element gewählt wird.

Die zweite Möglichkeit der Spezifikation von Las-Vegas-Algorithmen sagt aus, dass der Algorithmus A ein Las-Vegas-Algorithmus für eine Funktion F ist, wenn für jede Eingabe x gilt:

• und
• 

Wie zu erkennen ist, schließt die zweite Bedingung eine falsche Antwort aus, d. h. es wird entweder die richtige Antwort ausgegeben, oder die Antwort "?". Die erste Bedinung legt fest, dass ein richtiges Resultat von mindestens eine Wahrscheinlichkeit von größer oder gleich haben muss. Die Konstante ist dabei recht willkürlich gewählt und kann mit jedem beliebigen Wert zwischen 0 und 1 ersetzt werden, da sich die Wahrscheinlichkeit, das richtige Ergebnis berechnet zu haben, durch die Anzahl der unabhängigen Läufe von beliebig erhöhen lässt.

Um aus dem Modell, bei dem die Antowrt "?" erlaubt ist, ein Modell zu erhalten, bei dem immer alle Aussagen korrekt sind, kann man wie folgt vorgehen: Wenn A ein Las-VegaslAlgorithmus ist, der mit beschränkter Wahrscheinlichkeit ein "?" ausgeben darf, dann wird A modifiziert, in dem immer, anstatt "?" auszugeben, der Algorithmus auf die selbe Eingabe neu gestartet. Das führt zu einem neuen Algorithmus A'. Wenn man annimmt, dass der Algorithmus dabei in einem Durchlauf immer mit der Wahrscheinlichkeit das richtige Ergebnis liefert, hat man schnell eine hohe Wahrscheinlichkeit, nach wenigen Durchläufen ein richtiges Ergebnis zu erhalten.

• Soll die Zeitkomplexität des Algorithmus beschränkt werden, liegt die Wahrscheinlichkeit, dass der Algorithmus ein korrektes Ergebnis liefert. Es gibt also Fälle, in denen der Algorithmus kein Ergebnis ausgibt.

Dame n*n

Die Wahrscheinlichkeit, dass ein Las-Vegas-Algorithmus terminiert, lässt sich durch eine Erhöhung der Rechenzeit erkaufen. Es kann jedoch auch sinnvoll sein, eine größere Wahrscheinlichkeit für das Scheitern in Kauf zu nehmen, wenn dadurch die Zeit abnimmt, einen Misserfolg zu erkennen.