Las Vegas-Algorithmus - Las Vegas algorithm

Im Computing ist ein Las Vegas-Algorithmus ein randomisierter Algorithmus , der immer korrekte Ergebnisse liefert ; dh er liefert immer das richtige Ergebnis oder informiert über den Fehler. Die Laufzeit eines Las Vegas-Algorithmus unterscheidet sich jedoch je nach Eingabe. Die übliche Definition eines Las Vegas-Algorithmus beinhaltet die Einschränkung, dass die erwartete Laufzeit endlich ist, wobei die Erwartung über den Raum der im Algorithmus verwendeten Zufallsinformation oder Entropie ausgeführt wird. Eine alternative Definition erfordert, dass ein Las Vegas-Algorithmus immer terminiert ( effektiv ist ), aber ein Symbol ausgeben kann, das nicht Teil des Lösungsraums ist , um einen Fehler beim Finden einer Lösung anzuzeigen. Die Art der Las Vegas-Algorithmen macht sie für Situationen geeignet, in denen die Anzahl möglicher Lösungen begrenzt ist und die Überprüfung der Korrektheit eines Lösungskandidaten relativ einfach ist, während das Finden einer Lösung komplex ist.

Las Vegas-Algorithmen sind im Bereich der künstlichen Intelligenz und in anderen Bereichen der Informatik und des Operations Research bekannt . In der KI werden stochastische lokale Suchalgorithmen (SLS) als vom Las-Vegas-Typ angesehen. SLS-Algorithmen wurden verwendet, um NP-vollständige Entscheidungsprobleme und NP-harte kombinatorische Optimierungsprobleme anzugehen . Einige systematische Suchmethoden, wie beispielsweise moderne Varianten des Davis-Putnam-Algorithmus für propositionale Erfüllbarkeit (SAT), verwenden jedoch auch nicht-deterministische Entscheidungen und können daher auch als Las-Vegas-Algorithmen angesehen werden.

Geschichte

Las Vegas-Algorithmen wurden 1979 von László Babai im Zusammenhang mit dem Graphenisomorphismusproblem als Dual zu Monte-Carlo-Algorithmen eingeführt . Babai führte den Begriff "Las Vegas-Algorithmus" zusammen mit einem Beispiel für Münzwürfe ein: Der Algorithmus hängt von einer Reihe unabhängiger Münzwürfe ab, und es besteht eine geringe Wahrscheinlichkeit eines Fehlers (kein Ergebnis). Im Gegensatz zu Monte-Carlo-Algorithmen kann der Las Vegas-Algorithmus jedoch die Richtigkeit jedes gemeldeten Ergebnisses garantieren.

Beispiel

// Las Vegas algorithm
repeat:
    k = RandInt(n)
    if A[k] == 1,
        return k;

Wie oben erwähnt, liefern Las Vegas-Algorithmen immer korrekte Ergebnisse. Der obige Code veranschaulicht diese Eigenschaft. Eine Variable k wird zufällig generiert; Nachdem k generiert wurde, wird k verwendet, um das Array A zu indizieren . Wenn dieser Index den Wert 1 enthält, wird k zurückgegeben; andernfalls wiederholt der Algorithmus diesen Vorgang, bis er 1 findet. Obwohl dieser Las Vegas-Algorithmus garantiert die richtige Antwort findet, hat er keine feste Laufzeit; Aufgrund der Randomisierung (in Zeile 3 des obigen Codes) kann beliebig viel Zeit vergehen, bis der Algorithmus endet.

Definition

In diesem Abschnitt werden die Bedingungen beschrieben, die den Las Vegas-Typ eines Algorithmus charakterisieren.

Ein Algorithmus A ist ein Las Vegas-Algorithmus für die Problemklasse X, wenn

1. Immer wenn für eine gegebene Probleminstanz x∈X eine Lösung s zurückgegeben wird, ist s garantiert eine gültige Lösung von x
2. auf jeder gegebenen Instanz x ist die Laufzeit von A eine Zufallsvariable RT _A,x

Es gibt drei Begriffe der Vollständigkeit für Las Vegas-Algorithmen:

• Es kann garantiert werden, dass vollständige Las Vegas-Algorithmen jedes lösbare Problem innerhalb der Laufzeit t max lösen , wobei t max eine instanzabhängige Konstante ist.

Sei P(RT _A,x ≤ t) die Wahrscheinlichkeit, dass A eine Lösung für eine auflösbare Instanz x in der Zeit innerhalb von t findet, dann ist A genau dann vollständig, wenn für jedes x existiert

einige t max mit P(RT _A,x ≤ t _max ) = 1.

• ungefähr vollständige Las Vegas-Algorithmen lösen jedes Problem mit einer Wahrscheinlichkeit, die gegen 1 konvergiert, wenn sich die Laufzeit der Unendlichkeit nähert. Somit ist A näherungsweise vollständig, wenn für jede Instanz x, lim _t→∞ P(RT _A,x ≤ t) = 1.
• Im Wesentlichen unvollständige Las Vegas-Algorithmen sind Las Vegas-Algorithmen, die nicht annähernd vollständig sind.

Annähernde Vollständigkeit ist vor allem von theoretischem Interesse, da die Fristen für die Lösungsfindung meist zu groß sind, um praktisch nutzbar zu sein.

Anwendungsszenarien

Las Vegas Algorithmen haben je nach Problemstellung unterschiedliche Kriterien für die Bewertung. Diese Kriterien sind in drei Kategorien mit unterschiedlichen Zeitlimits unterteilt, da Las Vegas-Algorithmen keine festgelegte Zeitkomplexität haben. Hier einige mögliche Anwendungsszenarien:

Typ 1: Es gibt keine Zeitbegrenzungen, dh der Algorithmus läuft, bis er die Lösung gefunden hat.

Typ 2: Es gibt ein Zeitlimit t _max, um das Ergebnis zu finden.

Typ 3: Der Nutzen einer Lösung wird durch die Zeit bestimmt, die benötigt wird, um die Lösung zu finden.

Beachten Sie, dass Typ 1 und Typ 2 Sonderfälle von Typ 3 sind.

Bei Typ 1 ohne zeitliche Begrenzung kann die durchschnittliche Laufzeit das Laufzeitverhalten darstellen. Dies ist bei Typ 2 nicht derselbe Fall.

Dabei beschreibt P ( RT ≤ t _max ), also die Wahrscheinlichkeit, innerhalb der Zeit eine Lösung zu finden, sein Laufzeitverhalten.

Beim Typ 3 kann sein Laufzeitverhalten nur durch die Laufzeitverteilungsfunktion rtd : R → [0,1] definiert als rtd ( t ) = P ( RT ≤ t ) oder deren Näherung dargestellt werden.

Die Laufzeitverteilung (RTD) ist die charakteristische Art, das Laufzeitverhalten eines Las Vegas-Algorithmus zu beschreiben.

Mit diesen Daten können wir leicht andere Kriterien wie die mittlere Laufzeit, Standardabweichung, Median, Perzentile oder Erfolgswahrscheinlichkeiten P ( RT ≤ t ) für beliebige Zeitgrenzen t erhalten .

Anwendungen

Analogie

Las Vegas-Algorithmen treten häufig bei Suchproblemen auf . Zum Beispiel kann jemand, der online nach Informationen sucht, verwandte Websites nach den gewünschten Informationen durchsuchen. Der zeitliche Aufwand reicht also von „Glück“ und dem sofortigen Auffinden der Inhalte bis hin zu „Pech“ und hohem Zeitaufwand. Sobald die richtige Website gefunden ist, besteht keine Fehlermöglichkeit.

Randomisiertes QuickSort

INPUT: 
    # A is an array of n elements
def randomized_quicksort(A):
    if n == 1:
        return A  # A is sorted.
    else:
        i = random.randrange(1, n)  # Will take a random number in the range 1~n
        X = A[i]  # The pivot element
    """Partition A into elements < x, x, and >x  # as shown in the figure above.
    Execute Quicksort on A[1 to i-1] and A[i+1 to n].
    Combine the responses in order to obtain a sorted array."""

Ein einfaches Beispiel ist randomisierte QuickSort , bei der der Pivot zufällig gewählt wird und die Elemente in drei Partitionen unterteilt: Elemente kleiner als Pivot, Elemente gleich Pivot und Elemente größer als Pivot. Der randomisierte QuickSort benötigt viele Ressourcen, generiert aber immer das sortierte Array als Ausgabe.

Es ist offensichtlich, dass QuickSort immer die Lösung generiert, in diesem Fall das sortierte Array. Leider ist die zeitliche Komplexität nicht so offensichtlich. Es stellt sich heraus, dass die Laufzeit davon abhängt, welches Element wir als Pivot auswählen.

• Der schlimmste Fall Θ( n ² ), wenn der Pivot das kleinste oder das größte Element ist.

${\displaystyle T(n)=T(0)+T(n-1)+\Theta(n)}$

${\displaystyle T(n)=\Theta (1)+T(n-1)+\Theta (n)}$

${\displaystyle T(n)=T(n-1)+\Theta(n)}$

${\displaystyle T(n)=\Theta(n^{2})}$

• Durch die Randomisierung, bei der der Pivot zufällig ausgewählt wird und jedes Mal genau ein mittlerer Wert ist, kann QuickSort jedoch in Θ( n log n ) durchgeführt werden.

${\displaystyle T(n)\leq 2*T(n/2)+\Theta(n)}$

${\displaystyle T(n)=\Theta(n\log(n))}$

Die Laufzeit von QuickSort hängt stark davon ab, wie gut der Pivot ausgewählt ist. Wenn ein Pivot-Wert entweder zu groß oder zu klein ist, ist die Partition unausgeglichen. Dieser Fall ergibt eine schlechte Laufzeit. Wenn der Pivot-Wert jedoch in der Nähe der Mitte des Arrays liegt, wird die Aufteilung einigermaßen ausgeglichen sein. So wird seine Laufzeit gut sein. Da der Pivot zufällig ausgewählt wird, ist die Laufzeit meistens gut und gelegentlich schlecht.

Im Fall des Durchschnittsfalls ist es schwer zu bestimmen, da die Analyse nicht von der Eingabeverteilung abhängt, sondern von den zufälligen Entscheidungen, die der Algorithmus trifft. Der Durchschnitt von QuickSort wird über alle möglichen zufälligen Entscheidungen berechnet, die der Algorithmus bei der Auswahl des Pivots treffen könnte.

Obwohl die Laufzeit im ungünstigsten Fall ( n ² ) beträgt, beträgt die durchschnittliche Laufzeit Θ( n log n ). Es stellt sich heraus, dass der schlimmste Fall nicht oft vorkommt. Für große Werte von n beträgt die Laufzeit mit hoher Wahrscheinlichkeit Θ( n log n ).

Beachten Sie, dass die Wahrscheinlichkeit, dass der Pivot jedes Mal das Mittelwertelement ist, eine von n Zahlen ist, was sehr selten ist. Es ist jedoch immer noch die gleiche Laufzeit, wenn die Aufteilung 10%-90% anstelle von 50%-50% beträgt, da die Tiefe des Rekursionsbaums immer noch O (log n ) beträgt, wobei jede Ebene von . O ( n ) verwendet wird Rekursion.

Randomisierter Greedy-Algorithmus für das Acht-Damen-Problem

Das Acht-Damen-Problem wird normalerweise mit einem Backtracking-Algorithmus gelöst. Es kann jedoch ein Las Vegas-Algorithmus angewendet werden; Tatsächlich ist es effizienter als Backtracking.

Legen Sie 8 Damen auf ein Schachbrett, damit niemand einen anderen angreift. Denken Sie daran, dass eine Dame andere Figuren in derselben Reihe, Spalte und Diagonalen angreift.

Nehmen Sie an, dass k Reihen, 0 k are 8, erfolgreich von Damen besetzt sind.

Wenn k = 8, dann mit Erfolg aufhören. Andernfalls fahren Sie fort, um Zeile k + 1 zu besetzen .

Berechnen Sie alle Positionen dieser Reihe, die nicht von bestehenden Damen angegriffen werden. Wenn es keine gibt, dann scheitern. Andernfalls wählen Sie zufällig eine aus, erhöhen k und wiederholen.

Beachten Sie, dass der Algorithmus einfach versagt, wenn eine Dame nicht platziert werden kann. Aber der Vorgang kann wiederholt werden und erzeugt jedes Mal eine andere Anordnung.

Komplexitätsklasse

Die Komplexitätsklasse von Entscheidungsproblemen mit Las Vegas-Algorithmen mit erwarteter polynomialer Laufzeit ist ZPP .

Es stellt sich heraus, dass

${\displaystyle {\textsf {ZPP}}={\textsf {RP}}\cap {\textsf {co-RP}}}$

was eng mit der Art und Weise verbunden ist, wie Las Vegas-Algorithmen manchmal konstruiert werden. Die Klasse RP besteht nämlich aus allen Entscheidungsproblemen, für die ein randomisierter Polynomialzeitalgorithmus existiert, der immer richtig antwortet, wenn die richtige Antwort "nein" ist, aber mit einer gewissen Wahrscheinlichkeit, die von eins weg begrenzt ist, falsch sein darf, wenn die Antwort " Ja". Wenn ein solcher Algorithmus sowohl für ein Problem als auch für sein Komplement existiert (wobei die Antworten "ja" und "nein" vertauscht sind), können die beiden Algorithmen gleichzeitig und wiederholt ausgeführt werden: Führen Sie jeden für eine konstante Anzahl von Schritten abwechselnd aus, bis eins von ihnen gibt eine definitive Antwort zurück. Dies ist die Standardmethode zum Konstruieren eines Las Vegas-Algorithmus, der in erwarteter polynomialer Zeit ausgeführt wird. Beachten Sie, dass es im Allgemeinen keine Obergrenze für den ungünstigsten Fall für die Laufzeit eines Las Vegas-Algorithmus gibt.

Optimaler Las Vegas-Algorithmus

Um einen Las Vegas-Algorithmus optimal zu gestalten, sollte die erwartete Laufzeit minimiert werden. Dies kann erfolgen durch:

1. Der Las-Vegas-Algorithmus A ( x ) läuft wiederholt für eine Anzahl von t ₁ Schritten. Wenn A ( x ) während der Laufzeit stoppt, wird A ( x ) ausgeführt; andernfalls wiederholen Sie den Vorgang von Anfang an für weitere t ₂ Schritte usw.
2. Entwerfen einer Strategie, die unter allen Strategien für A ( x ) optimal ist , wenn die vollständigen Informationen über die Verteilung von T _A ( x ) gegeben sind.

Die Existenz der optimalen Strategie könnte eine faszinierende theoretische Beobachtung sein. Dies ist jedoch im wirklichen Leben nicht praktikabel, da es nicht einfach ist, die Informationen über die Verteilung von T _A ( x ) zu finden. Außerdem macht es keinen Sinn, das Experiment wiederholt durchzuführen, um Informationen über die Verteilung zu erhalten, da die Antwort meistens nur einmal für jedes x benötigt wird .

Bezug zu Monte-Carlo-Algorithmen

Las Vegas-Algorithmen können mit Monte-Carlo-Algorithmen verglichen werden , bei denen die verwendeten Ressourcen begrenzt sind, die Antwort jedoch mit einer bestimmten (typischerweise kleinen) Wahrscheinlichkeit falsch sein kann . Ein Las Vegas-Algorithmus kann in einen Monte-Carlo-Algorithmus umgewandelt werden, indem er für eine festgelegte Zeit ausgeführt wird und eine zufällige Antwort generiert wird, wenn er nicht beendet wird. Durch eine Anwendung der Markovschen Ungleichung können wir die Grenze für die Wahrscheinlichkeit setzen, dass der Las Vegas-Algorithmus den festen Grenzwert überschreitet.

Hier ist eine Tabelle, die die Algorithmen von Las Vegas und Monte Carlo vergleicht:

Wenn eine deterministische Methode zum Testen der Korrektheit verfügbar ist, ist es möglich, einen Monte-Carlo-Algorithmus in einen Las-Vegas-Algorithmus umzuwandeln. Es ist jedoch schwierig, einen Monte-Carlo-Algorithmus in einen Las-Vegas-Algorithmus umzuwandeln, ohne den Algorithmus testen zu können. Andererseits ist es einfach, einen Las Vegas-Algorithmus in einen Monte-Carlo-Algorithmus zu ändern. Dies kann durch Ausführen eines Las Vegas-Algorithmus für einen bestimmten Zeitraum erfolgen, der durch den Konfidenzparameter angegeben wird. Findet der Algorithmus die Lösung innerhalb der Zeit, ist er erfolgreich und wenn nicht, kann die Ausgabe einfach "sorry" sein.

Dies ist ein Beispiel für Las Vegas- und Monte-Carlo-Algorithmen zum Vergleich:

Angenommen, es gibt ein Array mit der Länge von geraden n . Die Hälfte der Einträge im Array sind Nullen und die verbleibende Hälfte sind Einsen. Das Ziel hier ist es, einen Index zu finden, der eine 1 enthält.

//Las Vegas algorithm
repeat:
    k = RandInt(n)
    if A[k] == 1,
        return k;
        
//Monte Carlo algorithm
repeat 300 times:
    k = RandInt(n)
    if A[k] == 1
        return k
return "Failed"

Da Las Vegas nicht endet, bis es 1 im Array findet, zockt es nicht mit der Korrektheit sondern mit der Laufzeit. Auf der anderen Seite wird Monte Carlo 300 Mal ausgeführt, was bedeutet, dass es unmöglich ist zu wissen, dass Monte Carlo innerhalb von 300 Schleifendurchläufen "1" im Array findet, bis es den Code tatsächlich ausführt. Es könnte die Lösung finden oder nicht. Im Gegensatz zu Las Vegas spielt Monte Carlo daher nicht mit Laufzeit, sondern mit Korrektheit.

Siehe auch

• Monte-Carlo-Algorithmus
• Atlantic City-Algorithmus
• Zufall

Verweise

Zitate

Quellen