Las Vegas Algorithmus

Im Computer, a Las Vegas Algorithmus ist ein Randomisierter Algorithmus Das gibt immer Korrekt Ergebnisse; Das heißt, es erzeugt 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 enthält die Einschränkung, dass die erwartet Die Laufzeit ist endlich, wo die Erwartung über den Raum von zufälligen Informationen oder Entropie im Algorithmus durchgeführt wird. Eine alternative Definition erfordert, dass ein Las Vegas -Algorithmus immer endet (ist Wirksam), kann aber a ausgeben Symbol nicht Teil des Lösungsraums Um einen Fehler bei der Suche nach einer Lösung zu finden.[1] Die Art der Las -Vegas -Algorithmen macht sie in Situationen geeignet, in denen die Anzahl der möglichen Lösungen begrenzt ist und in denen die Richtigkeit einer Kandidatenlösung relativ einfach ist, während die Suche nach einer Lösung komplex ist.

Las Vegas -Algorithmen sind auf dem Gebiet von herausragend künstliche Intelligenzund in anderen Bereichen der Informatik und Unternehmensforschung. In AI, Stochastische lokale Suche (SLS) Algorithmen gelten als vom Typ Las Vegas. SLS -Algorithmen wurden verwendet, um sich zu adressieren NP-Complete Entscheidungsprobleme und Np-harte Kombinatorische Optimierung Probleme.[2] Einige systematische Suchmethoden, wie z. B. moderne Varianten der Davis -Putnam -Algorithmus Verwenden Sie für die Aussagenerfragen (SAT) auch nicht deterministische Entscheidungen und können daher auch als Las-Vegas-Algorithmen angesehen werden.[3]

Geschichte

Las Vegas -Algorithmen wurden von eingeführt von László Babai 1979 im Kontext der Graph Isomorphismus Problemals dual zu Monte Carlo -Algorithmen.[4] Babai[5] führte den Begriff "Las Vegas -Algorithmus" zusammen mit einem Beispiel mit Münzflips vor: Der Algorithmus hängt von einer Reihe unabhängiger Münzflips ab, und es besteht eine geringe Ausfallwahrscheinlichkeit (kein Ergebnis). Im Gegensatz zu Monte -Carlo -Algorithmen kann der Las Vegas -Algorithmus jedoch die Richtigkeit eines beliebigen Ergebniss garantieren.

Beispiel 

// Las Vegas -Algorithmus wiederholen:   k = Randint(n)   wenn A[k] == 1,   Rückkehr k;

Wie oben erwähnt, geben Las Vegas -Algorithmen immer korrekte Ergebnisse zurück. Der obige Code zeigt diese Eigenschaft. Eine Variable k wird zufällig erzeugt; nach k wird erzeugt, k wird verwendet, um das Array zu indizieren A. Wenn dieser Index den Wert 1 enthält, dann k ist zurück gekommen; 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 oben genannten Code) ist es für willkürlich viel Zeit, sich vor dem Algorithmus zu vergrößern.

Definition

Dieser Abschnitt enthält die Bedingungen, die das Las Vegas -Typ eines Algorithmus charakterisieren.

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

  1. Wann immer für eine bestimmte Probleminstanz x∈X eine Lösung S zurückgibt, ist S garantiert eine gültige Lösung von x
  2. Bei jeder gegebenen Instanz x ist die Laufzeit von a eine zufällige Variable RTAxt

Es gibt drei Vorstellungen von Vollständigkeit Für Las Vegas -Algorithmen:

  • Komplette Las Vegas -Algorithmen kann garantiert jedes lösbare Problem innerhalb der Laufzeit t lösenMax, wo tMax ist eine instanzabhängige Konstante.

Ließ P (RtAxt ≤ t) Bezeichne die Wahrscheinlichkeit, dass A eine Lösung für eine lösliche Instanz x mit der Zeit innerhalb von T findet, dann ist a genau dann vollständig, wenn für jedes x es vorhanden ist

einige tMax so dass P (RtAxt ≤ tMax) = 1.

  • ungefähr vollständige Las -Vegas -Algorithmen Lösen Sie jedes Problem mit einer Wahrscheinlichkeit, die auf 1 konvergiert, wenn sich die Laufzeit unendlich nähert. Somit ist a ungefähr vollständig, wenn für jede Instanz x, limt → ∞ P (RtAxt ≤ t) = 1.
  • im Wesentlichen unvollständige Las -Vegas -Algorithmen sind Las Vegas -Algorithmen, die nicht ungefähr vollständig sind.

Die ungefähre Vollständigkeit ist in erster Linie theoretischer Interesse, da die Zeitbeschränkungen für das Finden von Lösungen normalerweise zu groß sind, um praktisch zu nutzen.

Anwendungsszenarien

Las Vegas -Algorithmen haben unterschiedliche Kriterien für die Bewertung basierend auf der Problemeinstellung. Diese Kriterien sind in drei Kategorien mit unterschiedlichen Zeitgrenzen unterteilt, da Las Vegas -Algorithmen keine festgelegte Zeitkomplexität haben. Hier sind einige mögliche Anwendungsszenarien:

  • Typ 1: Es gibt keine Zeitlimits, was bedeutet, dass der Algorithmus ausgeführt wird, bis er die Lösung findet.
  • Typ 2: Es gibt ein Zeitlimit t tMax für das Ergebnis des Ergebnisses.
  • Typ 3: Der Nutzen einer Lösung wird durch die Zeit bestimmt, die für die Ermittlung der Lösung erforderlich ist.

(Typ 1 und Typ 2 sind spezielle Fälle von Typ 3.)

Für Typ 1, bei dem es keine Zeitlimit gibt, kann die durchschnittliche Laufzeit das Laufzeitverhalten darstellen. Dies ist nicht der gleiche Fall für Typ 2.

Hier, P(Rt ≤ tMax), was die Wahrscheinlichkeit ist, innerhalb der Zeit eine Lösung zu finden, beschreibt sein Laufzeitverhalten.

Im Fall von Typ 3 kann sein Laufzeitverhalten nur durch die Laufzeitverteilungsfunktion dargestellt werden Rtd: R → [0,1] definiert als Rtd(t) = P(Rt ≤ t) oder seine Annäherung.

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

Mit diesen Daten können wir problemlos andere Kriterien wie die mittlere Laufzeit, die Standardabweichung, die Median-, Perzentil- oder Erfolgswahrscheinlichkeiten erhalten P(Rt ≤ t) für willkürliche Zeitlimit t.

Anwendungen

Analogie

Las Vegas -Algorithmen entstehen häufig in Suchprobleme. Beispielsweise kann eine Online -Suche nach Informationen zu verwandten Websites nach den gewünschten Informationen durchsuchen. Die zeitliche Komplexität reicht somit von "Glück" und dem Sofort finden, bis hin zu "unglücklich" und viel Zeit damit zu verbringen. Sobald die richtige Website gefunden wurde, besteht keine Fehlermöglichkeit.[7]

Randomisierte Quicksort 

EINGANG:   # A ist eine Reihe von N -Elementen def randomized_quicksort(A):  wenn n == 1:  Rückkehr A  # A ist sortiert.  anders:  i = zufällig.Randrange(1, n)  # Nimmt eine Zufallszahl im Bereich 1 ~ n  X = A[i]  # Das Pivot -Element  "" "Partition A in Elemente <x, x und> x #, wie in der obigen Abbildung gezeigt.     Führen Sie Quicksort auf einem [1 bis i-1] und einem [i+1 bis n] aus.     Kombinieren Sie die Antworten, um ein sortiertes Array zu erhalten. "" "

Ein einfaches Beispiel ist randomisiert Schnelle Sorte, wo der Drehpunkt zufällig ausgewählt wird und die Elemente in drei Partitionen unterteilt: Elemente weniger als Drehzahl, Elemente, die dem Pivot entsprechen, und Elemente, die größer als Pivot sind. Das randomisierte QuickSort benötigt viele Ressourcen, generiert jedoch immer das sortierte Array als Ausgabe.[8]

Es ist offensichtlich, dass Quicksort immer die Lösung erzeugt, die in diesem Fall das sortierte Array. Leider ist die Zeitkomplexität nicht so offensichtlich. Es stellt sich heraus, dass die Laufzeit davon abhängt, welches Element wir als Drehpunkt auswählen.

  • Der schlimmste Fall θ (n2) Wenn der Drehpunkt das kleinste oder das größte Element ist.
  • Durch die Randomisierung, bei der der Drehpunkt zufällig ausgewählt wird und jedes Mal genau ein mittlerer Wert ist, kann der QuickSort in θ (θ (nProtokolln).

Die Laufzeit von Quicksort hängt stark davon ab, wie gut der Drehpunkt ausgewählt ist. Wenn ein Pivot -Wert entweder zu groß oder klein ist, ist die Partition unausgeglichen, was zu einer schlechten Laufzeiteffizienz führt. Wenn der Wert von Drehzahl jedoch in der Nähe der Mitte des Arrays liegt, ist die Aufteilung einigermaßen ausgewogen und führt zu einer schnelleren Laufzeit. Da der Drehpunkt zufällig ausgewählt wird, wird die Laufzeit die meiste Zeit gut und gelegentlich schlecht sein.

Im Fall eines durchschnittlichen Falles ist es schwierig zu bestimmen, da die Analyse nicht von der Eingangsverteilung abhängt, sondern von den zufälligen Entscheidungen, die der Algorithmus trifft. Der Durchschnitt von Quicksort wird über alle möglichen zufälligen Auswahlmöglichkeiten berechnet, die der Algorithmus bei der Auswahl des Pivots treffen könnte.

Obwohl die Worst-Case-Laufzeit θ ist (n2) Die Durchschnittsfall-Laufzeit beträgt θ (θ (nProtokolln). Es stellt sich heraus, dass der schlimmste Fall nicht oft passiert. Für große Werte von n, die Laufzeit ist θ (nProtokolln) mit hoher Wahrscheinlichkeit.

Beachten Sie, dass die Wahrscheinlichkeit, dass der Drehpunkt jedes Mal das mittlere Wertelement ist n Zahlen, was sehr selten ist. Es ist jedoch immer noch die gleiche Laufzeit, wenn die Spaltung 10% -90% anstelle von 50% –50% beträgt, da die Tiefe des Rekursionsbaums immer noch sein wird O(Protokolln) mit O(n) Zeiten, die jede Rekursionsniveau genommen haben.

Randomisierter gieriger Algorithmus für acht Queens -Problem

Das Acht Queens Problem wird normalerweise mit einem Backtracking -Algorithmus gelöst. Ein Las Vegas -Algorithmus kann jedoch angewendet werden; In der Tat ist es effizienter als Backtracking.

Platzieren Sie 8 Queens auf ein Schachbrett, damit niemand einen anderen angreift. Denken Sie daran, dass eine Königin andere Stücke in derselben Reihe, in der Säule und in der Diagonale angreift.

Annehmen, dass k Zeilen, 0 ≤ k ≤ 8, werden erfolgreich von Queens besetzt.

Wenn k = 8, dann mit dem Erfolg auf. Andernfalls besetzen Sie die Reihe k + 1.

Berechnen Sie alle Positionen in dieser Reihe, die nicht von vorhandenen Königinnen angegriffen wurden. Wenn es keine gibt, scheitern Sie. Andernfalls wählen Sie einen zufälligen, inkrement k und wiederholen.

Beachten Sie, dass der Algorithmus einfach fehlschlägt, wenn eine Königin nicht platziert werden kann. Der Vorgang kann jedoch wiederholt werden und erzeugt jedes Mal eine andere Anordnung.[9]

Komplexitätsklasse

Das Komplexitätsklasse von Entscheidungsprobleme das hat Las Vegas -Algorithmen mit erwartet Die Polynomlaufzeit ist Zpp.

Es stellt sich heraus, dass

Dies ist eng mit der Art und Weise verbunden, wie Las Vegas -Algorithmen manchmal konstruiert werden. Nämlich die Klasse RP besteht aus allen Entscheidungsproblemen, auf die ein randomisierter Polynom-Zeit-Algorithmus existiert, der immer richtig antwortet, wenn die richtige Antwort "Nein" ist, aber mit einer bestimmten Wahrscheinlichkeit, die von einem entfernt ist, falsch ist, wenn die Antwort "Ja" ist. Wenn ein solcher Algorithmus sowohl für ein Problem als auch für seine Ergänzung (mit den Antworten "Ja und" Nein "ausgetauscht) existiert, können die beiden Algorithmen gleichzeitig und wiederholt ausgeführt werden von ihnen gibt eine endgültige Antwort zurück. Dies ist die Standardmethode, um einen Las Vegas -Algorithmus zu konstruieren, der in der erwarteten Polynomzeit läuft. Beachten Sie, dass es im Allgemeinen in der Laufzeit eines Las Vegas -Algorithmus keine schlimmste Obergrenze gibt.

Optimaler Las Vegas -Algorithmus

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

  1. Der Las Vegas -Algorithmus A(x) Läuft wiederholt für eine Reihe t1 Schritte. Wenn A(x) stoppt dann während der Laufzeit A(x) erledigt; Ansonsten wiederholen Sie den Vorgang von Anfang an für einen anderen t2 Schritte und so weiter.
  2. Entwerfen einer Strategie, die unter allen Strategien für optimal ist A(x) angesichts der vollständigen Informationen über die Verteilung von TA(x).

Die Existenz der optimalen Strategie könnte eine faszinierende theoretische Beobachtung sein. Im wirklichen Leben ist es jedoch nicht praktisch, weil es nicht einfach ist, die Informationen zur Verteilung von zu finden TA(x). Darüber hinaus gibt es keinen Sinn, das Experiment wiederholt auszuführen, um die Informationen über die Verteilung zu erhalten, da die meiste Zeit die Antwort nur einmal für jeden benötigt wird x.[10]

Beziehung zu Monte -Carlo -Algorithmen

Las Vegas -Algorithmen können mit kontrastieren Monte Carlo -Algorithmen, in denen die verwendeten Ressourcen begrenzt sind, aber die Antwort kann mit einem bestimmten (normalerweise klein) falsch sein Wahrscheinlichkeit. Ein Las Vegas -Algorithmus kann in einen Monte -Carlo -Algorithmus umgewandelt werden, indem es für die festgelegte Zeit ausgeführt und eine zufällige Antwort generiert wird, wenn er nicht beendet wird. Durch Anwendung von Markovs UngleichheitWir können die Grenze auf die Wahrscheinlichkeit festlegen, dass der Las Vegas -Algorithmus die feste Grenze überschreiten würde.

Hier ist eine Tabelle, in der Las Vegas und Monte Carlo -Algorithmen verglichen werden:[11]

Laufzeit Richtigkeit
Las Vegas Algorithmus probabilistisch sicher
Monte Carlo Algorithmus sicher probabilistisch

Wenn eine deterministische Möglichkeit zum Testen auf Korrektheit verfügbar ist, ist es möglich, einen Monte -Carlo -Algorithmus in einen Las Vegas -Algorithmus zu verwandeln. Es ist jedoch schwierig, einen Monte -Carlo -Algorithmus in einen Las Vegas -Algorithmus umzuwandeln, ohne den Algorithmus zu testen. Andererseits ist es einfach, einen Las Vegas -Algorithmus in einen Monte -Carlo -Algorithmus zu wechseln. Dies kann durch Ausführen eines Las -Vegas -Algorithmus für einen bestimmten Zeitraum durchgeführt werden, der durch Konfidenzparameter angegeben ist. Wenn der Algorithmus die Lösung innerhalb der Zeit findet, ist es Erfolg und wenn nicht, kann die Ausgabe einfach "sorry" sein.

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

Angenommen, es gibt ein Array mit der Länge von gerade n. Die Hälfte der Einträge in der Array beträgt 0 und die verbleibende Hälfte von 1. Das Ziel hier ist es, einen Index zu finden, der eine 1 enthält.

// Las Vegas -Algorithmus wiederholen:  k = Randint(n)  wenn A[k] == 1,  Rückkehr k;          // Monte Carlo -Algorithmus wiederholen 300 mal:  k = Randint(n)  wenn A[k] == 1  Rückkehr k Rückkehr "Gescheitert"

Da Las Vegas nicht endet, wenn es 1 im Array findet, spielt es nicht mit der Richtigkeit, sondern der Laufzeit. Auf der anderen Seite läuft Monte Carlo 300 Mal, was bedeutet, dass Monte Carlo innerhalb des 300 -fachen Schleifens "1" im Array "1" findet, bis er den Code tatsächlich ausgeführt hat. Es könnte die Lösung finden oder nicht. Daher spielt Monte Carlo im Gegensatz zu Las Vegas nicht mit Laufzeit, sondern mit der Korrektheit.

Siehe auch

Verweise

Zitate

  1. ^ Steven D. Galbraith (2012). Mathematik der öffentlichen Schlüsselkryptographie. Cambridge University Press. p. 16. ISBN 978-1-107-01392-6.
  2. ^ Selman, B., Kautz, H.A. (1996).
  3. ^ Hoos, Holger H .. „Über die empirische Bewertung von Las Vegas -Algorithmen - Positionspapier.“ (1998).
  4. ^ * László Babai, Monte-Carlo-Algorithmen im Graph-Isomorphismus-Test, Université de Montréal, D.M.S. Nr. 79-10.
  5. ^ Babai, László. "Monte-Carlo-Algorithmen im Graph-Isomorphismus-Test." (1979).
  6. ^ H. H. Hoos und T. Stutzle. Bewertung von Las Vegas -Algorithmen - Fallstricke und Heilmittel. In Proceedings der vierzehnten Konferenz über Unsicherheit in der künstlichen Intelligenz (UAI-98), Seiten 238–245. Morgan Kaufmann Publishers, San Francisco, CA, 1998.
  7. ^ Randomisierte Algorithmen. Brilliant.org. Abgerufen 23:54, 24. Oktober 2018, von https://brilliant.org/wiki/randomized-algorithms-overview/
  8. ^ "Von Las Vegas bis Monte Carlo: Randomisierte Algorithmen in maschinellen Lernsystemen". In Richtung Data Science. 2018-09-07. Abgerufen 2018-10-25.
  9. ^ Barringer, Howard (Dezember 2010). "Randomisierte Algorithmen - eine kurze Einführung" (PDF). www.cs.man.ac.uk. Abgerufen 2018-12-08.
  10. ^ Luby, Michael (27. September 1993). "Optimale Beschleunigung von Las Vegas -Algorithmen". Informationsverarbeitungsbriefe. 47 (4): 173–180. doi:10.1016/0020-0190 (93) 90029-9.
  11. ^ Goodrich, Michael. Algorithmus Design und Anwendungen: Randomisierte Algorithmen. Wiley, 2015, https://nscpolteksby.ac.id/ebook/files/ebook/computler%20Engineering/algorithm%20design%20and%20Anlications%20A4%20(2015)/20.%20Chapter%2019%20-%20. 23. Oktober 2018.
  12. ^ Procaccia, Ariel (5. November 2015). "Große theoretische Ideen in der Informatik" (PDF). www.cs.cmu.edu (Power Point). Abgerufen 3. November 2018.

Quellen

  • Algorithmen und Theorie des Berechnungshandbuchs, CRC Press LLC, 1999.
  • "Las Vegas -Algorithmus", in Wörterbuch von Algorithmen und Datenstrukturen [Online], Paul E. Black, Hrsg., U. Nationales Institut für Standards und Technologie. 17. Juli 2006. (abgerufen am 9. Mai 2009) erhältlich unter: [1]