Randomisierter Algorithmus

A Randomisierter Algorithmus ist ein Algorithmus das verwendet einen Grad an Zufälligkeit als Teil seiner Logik oder Prozedur. Der Algorithmus verwendet normalerweise einheitlich zufällig Bits als Hilfseingabe, um sein Verhalten zu steuern, in der Hoffnung, eine gute Leistung im "durchschnittlichen Fall" über alle möglichen Auswahlmöglichkeiten der zufälligen Entscheidungen zu erzielen, die durch die zufälligen Bits bestimmt werden. Somit sind entweder die Laufzeit oder die Ausgabe (oder beide) zufällige Variablen.

Man muss zwischen Algorithmen unterscheiden, die die zufällige Eingabe verwenden, damit sie immer mit der richtigen Antwort enden, aber wo die erwartete Laufzeit endlich ist (endlich (Las Vegas -Algorithmen, zum Beispiel Schnelle Sorte^[1]) und Algorithmen, die die Chance haben, ein falsches Ergebnis zu erzielen (Monte Carlo -AlgorithmenZum Beispiel der Monte -Carlo -Algorithmus für die MFAs Problem^[2]) oder nicht ein Ergebnis erzeugen, indem ein Fehler signalisiert oder nicht beendet wird. In einigen Fällen sind probabilistische Algorithmen das einzige praktische Mittel zur Lösung eines Problems.^[3]

In der üblichen Praxis werden randomisierte Algorithmen unter Verwendung von a angenähert Pseudorandom -Zahlengenerator anstelle einer echten Quelle von zufälligen Bits; Eine solche Implementierung kann von den erwarteten theoretischen Verhaltensweisen und mathematischen Garantien abweichen, die von der Existenz eines idealen wahren Zufallszahlengenerators abhängen können.

Motivation

Betrachten Sie als motivierendes Beispiel das Problem der Suche nach einem "a' in einem (n Array von n Elemente.

Eingang: Eine Auswahl an n≥2 Elemente, in denen die Hälfte „ist“aUnd die andere Hälfte sind "b's.

Ausgabe: Finden Sie ein "a’Im Array.

Wir geben zwei Versionen des Algorithmus, einen Las Vegas Algorithmus und ein Monte Carlo Algorithmus.

Las Vegas -Algorithmus:

finda_lv(Array A, n) Start  wiederholen  Nach dem Zufallsprinzip auswählen eines Element aus von n Elemente.  bis um 'a' ist gefunden Ende 

Dieser Algorithmus gelingt mit der Wahrscheinlichkeit 1. Die Anzahl der Iterationen variiert und kann willkürlich groß sein, aber die erwartete Anzahl von Iterationen ist

$oder$

Da es konstant ist, ist die erwartete Laufzeit über viele Anrufe ${\ displayStyle \ theta (1)}$. (Sehen Große Theta -Notation))

Monte Carlo -Algorithmus:

finda_mc(Array A, n, k) Start  i : = 0  wiederholen  Nach dem Zufallsprinzip auswählen eines Element aus von n Elemente.  i : = i + 1  bis um i = k oder 'a' ist gefunden Ende 

Wenn ein 'aEs wird gefunden, der Algorithmus ist erfolgreich, sonst scheitert der Algorithmus. Nach k Iterationen, die Wahrscheinlichkeit, ein „zu finden“a' ist:

Dieser Algorithmus garantiert keinen Erfolg, aber die Laufzeit ist begrenzt. Die Anzahl der Iterationen ist immer geringer als oder gleich k. Die Laufzeit (erwartet und absolut) zu nehmen, ist k ständig ${\ displayStyle \ theta (1)}$.

Randomisierte Algorithmen sind besonders nützlich, wenn sie mit einem böswilligen "Gegner" konfrontiert sind oder Angreifer wer versucht absichtlich, den Algorithmus einen schlechten Eingang zu füttern (siehe schlimmste Fallkomplexität und Wettbewerbsanalyse (Online -Algorithmus)) wie in der Gefangenendilemma. Es ist aus diesem Grund das Zufälligkeit ist allgegenwärtig in Kryptographie. In kryptografischen Anwendungen können Pseudo-Random-Zahlen nicht verwendet werden, da der Gegner sie vorhersagen kann, was den Algorithmus effektiv deterministisch macht. Daher entweder eine Quelle wirklich zufälliger Zahlen oder a Kryptografisch sichern Pseudo-Random-Zahlengenerator ist nötig. Ein weiterer Bereich, in dem Zufälligkeit inhärent ist Quanten-Computing.

Im obigen Beispiel gibt der Las Vegas -Algorithmus immer die richtige Antwort aus, aber seine Laufzeit ist eine zufällige Variable. Der Monte Carlo -Algorithmus (im Zusammenhang mit dem Monte Carlo -Methode für die Simulation) wird garantiert in einer Zeit abgeschlossen, die durch eine Funktion die Eingangsgröße und deren Parameter begrenzt werden kann k, aber erlaubt a Kleine Fehlerwahrscheinlichkeit. Beobachten Sie, dass jeder Las Vegas -Algorithmus in einen Monte -Carlo -Algorithmus (via "umgewandelt werden kann Markovs Ungleichheit) Durch die Ausgabe einer willkürlichen, möglicherweise falschen Antwort, wenn sie innerhalb einer bestimmten Zeit nicht abgeschlossen ist. Wenn ein effizientes Überprüfungsprozedur vorhanden ist, um zu prüfen, ob eine Antwort korrekt ist, kann ein Monte -Carlo -Algorithmus in einen Las Vegas -Algorithmus umgewandelt werden, indem der Monte -Carlo -Algorithmus wiederholt ausgeführt wird, bis eine korrekte Antwort erhalten wird.

Rechenkomplexität

Computerkomplexitätstheorie Modelle randomisierte Algorithmen als Probabilistische Turing -Maschinen. Beide Las Vegas und Monte Carlo -Algorithmen werden berücksichtigt und mehrere Komplexitätsklassen werden untersucht. Die grundlegendste randomisierte Komplexitätsklasse ist RP, was die Klasse von ist Entscheidungsprobleme für das es einen effizienten (polynomialen Zeitpunkt) randomisierten Algorithmus (oder probabilistische Turing-Maschine) gibt, der keine Instanzen mit absoluter Gewissheit erkennt und Ja-Instanzen mit einer Wahrscheinlichkeit von mindestens 1/2 erkennt. Die Komplementklasse für RP ist Co-RP. Problemklassen mit (möglicherweise nicht terminierenden) Algorithmen mit Polynomzeit Durchschnittliche Falllaufzeit, deren Ausgabe immer korrekt ist Zpp.

Die Klasse von Problemen, für die sowohl Ja als auch No-Instances mit einem Fehler identifiziert werden dürfen, wird aufgerufen BPP. Diese Klasse fungiert als randomisiertes Äquivalent von P, d.h. bpp die Klasse effizienter randomisierter Algorithmen darstellt.

Geschichte

Eine wichtige Forschungslinie bei randomisierten Algorithmen in Zahlentheorie kann zurückverfolgt werden Pocklingtons Algorithmus, ab 1917, was findet Quadratwurzeln Modulo -Primzahlen.^[4] Die Untersuchung randomisierter Algorithmen in der Zahlentheorie wurde durch die Entdeckung von A von 1977 angerichtet Randomisierter Primalitätstest (d.h. Primalität einer Zahl) nach Robert M. Solovay und Volker Strassen. Bald darauf zeigte Michael O. Rabin, dass die 1976 1976 Millers Primalitätstest Kann in einen randomisierten Algorithmus verwandelt werden. Zu dieser Zeit kein praktisch deterministischer Algorithmus Für Primalität war bekannt.

Der Müller -Rabin -Primalitätstest beruht auf einer binären Beziehung zwischen zwei positiven Ganzzahlen k und n das kann ausgedrückt werden, indem man das sagt k "ist ein Zeuge der Kompositheit von" n. Es kann gezeigt werden, dass

• Wenn die Kompositheit von einem Zeugen gibt n, dann n ist zusammengesetzt (d. H., n ist nicht Prime), und
• Wenn n ist zusammengesetzt, dann mindestens drei Viertel der natürlichen Zahlen weniger als n sind Zeugen seiner Kompositheit und
• Es gibt einen schnellen Algorithmus, der gegeben ist k und nErmitteln Sie, ob k ist ein Zeuge der Kompositheit von n.

Beachten Sie, dass dies impliziert, dass das Primalitätsproblem in Co-RP.

Wenn man nach dem Zufallsprinzip Wählt 100 Zahlen weniger als eine zusammengesetzte Zahl nund dann ist die Wahrscheinlichkeit, einen solchen "Zeugen" nicht zu finden, (1/4)¹⁰⁰ Daher ist dies für die meisten praktischen Zwecke ein guter Primalitätstest. Wenn n ist groß, es kann keinen anderen Test geben, der praktisch ist. Die Fehlerwahrscheinlichkeit kann durch genügend unabhängige Tests auf willkürlichem Maße reduziert werden.

Daher ist in der Praxis keine Strafe im Zusammenhang mit der Annahme einer geringen Fehlerwahrscheinlichkeit verbunden, da die Wahrscheinlichkeit von Fehler astronomisch mit ein wenig Sorgfalt astronomisch klein gemacht werden kann. In der Tat wurde seitdem ein deterministischer Polynom-Zeit-Primalitätstest gefunden (siehe ASS -Primalitätstest), es hat die älteren probabilistischen Tests in nicht ersetzt kryptografisch Software Es wird auch nicht erwartet, dass dies auf absehbare Zeit tut.

Beispiele

Schnelle Sorte

Schnelle Sorte ist ein bekannter, häufig verwendeter Algorithmus, bei dem Zufälligkeit nützlich sein kann. Viele deterministische Versionen dieses Algorithmus erfordern O(n²) Zeit zu sortieren n Zahlen für einige genau definierte Klasse von degenerierten Eingängen (wie ein bereits sortiertes Array) mit der spezifischen Klasse von Eingängen, die dieses durch das Protokoll für die Pivot-Auswahl definierte Verhalten erzeugen. Wenn der Algorithmus jedoch die Pivot -Elemente gleichmäßig zufällig aus wählt, hat er eine nachsichtige Wahrscheinlichkeit, dass er in die Fertigstellung kommt, in O(nProtokolln) Zeit unabhängig von den Eigenschaften der Eingabe.

Randomisierte inkrementelle Konstruktionen in der Geometrie

Im Computergeometrie, eine Standardtechnik zum Aufbau einer Struktur wie a konvexer Rumpf oder Delaunay -Triangulation muss die Eingangspunkte zufällig durchdringen und sie dann einzeln in die vorhandene Struktur einfügen. Die Randomisierung stellt sicher, dass die erwartete Anzahl von Änderungen der Struktur durch eine Einfügung gering ist, und daher kann die erwartete Laufzeit des Algorithmus von oben begrenzt werden. Diese Technik wird als randomisierte inkrementelle Konstruktion bezeichnet.^[5]

Min Cut

Eingang: EIN Graph G(V,E))

Ausgabe: EIN schneiden Verteilung der Eckpunkte in L und Rmit der minimalen Anzahl von Kanten zwischen den Kanten L und R.

Erinnern Sie sich daran, dass die Kontraktion von zwei Knoten, u und v, in einem (Multi-) Diagramm ergibt einen neuen Knoten u 'Mit Kanten, die die Vereinigung der Kanten sind, die an beiden Fällen vorkommt u oder v, außer von allen Kanten, die sich verbinden u und v. Abbildung 1 zeigt ein Beispiel für die Kontraktion von Scheitelpunkten A und B. Nach der Kontraktion kann das resultierende Diagramm parallele Kanten haben, enthält jedoch keine Selbstschleifen.

Abbildung 2: erfolgreicher Lauf von Kargers Algorithmus in einem 10-Versortex-Diagramm. Der minimale Schnitt hat Größe 3 und wird durch die Scheitelpunktfarben angezeigt.

Abbildung 1: Kontraktion von Scheitelpunkt A und B

Kargers^[6] Grundalgorithmus:

Start     I = 1 wiederholen  wiederholen             Nehmen Sie eine zufällige Kante (u, v) ∈ E in G Ersetzen Sie u und v durch die Kontraktion u ' bis um Nur 2 Knoten erhalten das entsprechende Schnittergebnis ci         i = i + 1 bis um i = m Ausgabe des minimalen Schnitts unter c1, C2, ..., Cm.Ende 

In jeder Ausführung der äußeren Schleife wiederholt der Algorithmus die innere Schleife, bis nur 2 Knoten verbleiben, der entsprechende Schnitt wird erhalten. Die Laufzeit einer Ausführung ist ${\ displayStyle o (n)}$, und n bezeichnet die Anzahl der Eckpunkte. Nach m Times Ausführungen der äußeren Schleife geben den Mindestschnitt zwischen allen Ergebnissen aus. Die Abbildung 2 gibt ein Beispiel für eine Ausführung des Algorithmus. Nach der Ausführung erhalten wir einen Schnitt von Größe 3.

Analyse des Algorithmus

Die Wahrscheinlichkeit, dass der Algorithmus erfolgreich ist, ist 1 - die Wahrscheinlichkeit, dass alle Versuche fehlschlagen. Durch Unabhängigkeit ist die Wahrscheinlichkeit, dass alle Versuche scheitern

$$oder C)).}$$

Durch Lemma 1 die Wahrscheinlichkeit, dass C_i = C ist die Wahrscheinlichkeit, dass keine Kante von C wird während der Iteration ausgewählt i. Betrachten Sie die innere Schleife und lassen Sie es G_j bezeichnen die Grafik danach j Kantenkontraktionen, wo j ∈ {0, 1,…. n - 3}. G_j hat n − j Eckpunkte. Wir verwenden die Kettenregel von Bedingte Möglichkeiten. Die Wahrscheinlichkeit, dass die bei der Iteration gewählte Kante ausgewählt wurde j ist nicht in C, Angesichts der Tatsache, dass keine Kante von C wurde schon einmal ausgewählt, ist ${\ displaystyle 1-{\ frac {k} {| e (g_ {j}) |}}}$. Beachten Sie, dass G_j Hat noch einen Schnitt der Größe kAlso von Lemma 2 hat es immer noch zumindest ${\ displayStyle {\ frac {(n-j) k} {2}}}$ Kanten.

Daher, $oder }$.

Nach der Kettenregel die Wahrscheinlichkeit, den Minenschnitt zu finden C ist

$$oder \ rechts) \ links ({\ frac {n-4} {n-2}} \ rechts) \ ldots \ links ({\ frac {3} {5}} \ rechts) \ links ({\ frac {2} {4}} \ rechts) \ links ({\ frac {1} {3}} \ rechts).}.}$$

Stornierung gibt an $oder$. Somit ist die Wahrscheinlichkeit, dass der Algorithmus erfolgreich ist ${\ displayStyle 1- \ links (1-{\ frac {2} {n (n-1)}} \ rechts)^{m}}$. Zum ${\ displayStyle m = {\ frac {n (n-1)} {2}} \ ln n}$Dies entspricht der ${\ displayStyle 1-{\ frac {1} {n}}}$. Der Algorithmus findet den min -Schnitt mit Wahrscheinlichkeit ${\ displayStyle 1-{\ frac {1} {n}}}$, rechtzeitig ${\ displayStyle o (mn) = o (n^{3} \ log n)}$.

Derandomisierung

Zufälligkeit kann als Ressource wie Raum und Zeit angesehen werden. Derandomisierung ist dann der Prozess von Entfernen Zufälligkeit (oder so wenig davon wie möglich verwenden). Es ist derzeit nicht bekannt, ob alle Algorithmen desandomisiert werden können, ohne ihre Laufzeit signifikant zu erhöhen. Zum Beispiel in RechenkomplexitätEs ist nicht bekannt, ob P = BPP, d.h. wir wissen nicht, ob wir einen willkürlichen randomisierten Algorithmus aufnehmen können, der in der Polynomzeit mit einer geringen Fehlerwahrscheinlichkeit läuft, und es verreumomisieren, dass es in Polynomzeit ohne Zufälligkeit ausgeführt wird.

Es gibt spezifische Methoden, die verwendet werden können, um bestimmte randomisierte Algorithmen zu Derandomisieren:

• das Methode der bedingten Wahrscheinlichkeitenund seine Verallgemeinerung, Pessimistische Schätzer
• Diskrepanztheorie (die zum Derandomisieren von geometrischen Algorithmen verwendet wird)
• Die Ausbeutung einer begrenzten Unabhängigkeit in den vom Algorithmus verwendeten zufälligen Variablen, wie die paarweise Unabhängigkeit benutzt in Universal Hashing
• die Verwendung von Expander -Diagramme (oder Dispergierer im Allgemeinen) zu verstärken Eine begrenzte Menge an anfänglicher Zufälligkeit (dieser letzte Ansatz wird auch als Generierung bezeichnet Pseudorandom Bits aus einer zufälligen Quelle und führt zum verwandten Thema Pseudorandomess)
• Ändern des randomisierten Algorithmus, um eine Hash-Funktion als Zufälligkeitsquelle für die Aufgaben des Algorithmus zu verwenden, und dann den Algorithmus desesandomisierten, indem alle möglichen Parameter (Saatgut) der Hash-Funktion bruten. Diese Technik wird normalerweise verwendet, um einen Stichprobenraum ausführlich zu durchsuchen und den Algorithmus deterministisch zu machen (z. B. randomisierte Graphenalgorithmen)

Wo Zufälligkeit hilft

Wenn das Berechnungsmodell beschränkt ist Turing -MaschinenEs ist derzeit eine offene Frage, ob die Fähigkeit, zufällige Entscheidungen zu treffen, einige Probleme in der Polynomzeit gelöst werden können, die ohne diese Fähigkeit in der Polynomzeit nicht gelöst werden können. Dies ist die Frage, ob p = bpp. In anderen Kontexten gibt es jedoch spezifische Beispiele für Probleme, bei denen die Randomisierung strikte Verbesserungen ergibt.

• Basierend auf dem anfänglichen motivierenden Beispiel: Bei einer exponentiell langen 2 -Zeichenfolge von 2^k Charaktere, halb a und halb b, a Zufallszugriffsmaschine erfordert 2^k–1 Lookups im schlimmsten Fall, um den Index von einem zu finden a; Wenn es zufällige Entscheidungen treffen dürfen, kann es dieses Problem in einer erwarteten Polynomzahl von Such -Lookups lösen.
• Die natürliche Art, eine numerische Berechnung in eingebettete Systeme oder Cyber-physische Systeme ist ein Ergebnis zu liefern, das dem richtigen mit hoher Wahrscheinlichkeit (oder wahrscheinlich ungefähr korrekter Berechnung (PACC)) annähert. Das harte Problem im Zusammenhang mit der Bewertung des Diskrepanzverlusts zwischen der angenäherten und der korrekten Berechnung kann effektiv angegangen werden, indem auf die Randomisierung zurückgreifen^[7]
• Im KommunikationskomplexitätDie Gleichheit von zwei Zeichenfolgen kann auf eine gewisse Zuverlässigkeit verwendet werden ${\ displayStyle \ log n}$ Kommunikation mit einem randomisierten Protokoll. Jedes deterministische Protokoll erfordert ${\ displayStyle \ theta (n)}$ Bits, wenn sie gegen einen starken Gegner verteidigen.^[8]
• Das Volumen eines konvexen Körpers kann durch einen randomisierten Algorithmus auf willkürliche Genauigkeit in der Polynomzeit geschätzt werden.^[9] Bárány und FÜredi zeigten, dass kein deterministischer Algorithmus dasselbe tun kann.^[10] Dies ist bedingungslos wahr, d. H. Ohne sich auf komplexitätstheoretische Annahmen zu verlassen, vorausgesetzt, der konvexe Körper kann nur als schwarze Box abgefragt werden.
• Ein komplexitätstheoretischeres Beispiel für einen Ort, an dem Zufälligkeit zu helfen scheint, ist die Klasse IP. IP besteht aus allen Sprachen, die (mit hoher Wahrscheinlichkeit) durch eine polynomial lange Wechselwirkung zwischen einem allmächtigen Prover und einem Verifier akzeptiert werden können, der einen BPP-Algorithmus implementiert. Ip = PSPACE.^[11] Wenn jedoch der Überprüfer deterministisch ist, dann ip = ip = Np.
• In einem Chemisches Reaktionsnetzwerk (Ein endlicher Satz von Reaktionen wie A + B → 2C + D, das mit einer endlichen Anzahl von Molekülen arbeitet), ist die Fähigkeit, jemals einen bestimmten Zielzustand von einem Anfangszustand zu erreichen Der Zustand (unter Verwendung der Standard-Konzentrationswahrscheinlichkeit, für die als nächstes eine Reaktion auftritt) ist unentscheidbar. Insbesondere kann eine begrenzte Turing -Maschine mit willkürlich hoher Wahrscheinlichkeit für korrektes Laufen für alle Zeiten simuliert werden, nur wenn ein zufälliges chemisches Reaktionsnetzwerk verwendet wird. Mit einem einfachen nicht deterministischen chemischen Reaktionsnetzwerk (jede mögliche Reaktion kann als nächstes auftreten) ist die Rechenleistung begrenzt primitive rekursive Funktionen.^[12]

Siehe auch

• Probabilistische Analyse von Algorithmen
• Atlantic City Algorithmus
• Monte Carlo Algorithmus
• Las Vegas Algorithmus
• Bogosort
• Prinzip der aufgeschobenen Entscheidung
• Randomisierte Algorithmen als Nullsummenspiel
• Probabilistische Roadmap
• Hyperloglog
• Graf -min -Skizze
• ungefährer Zählalgorithmus
• Kargers Algorithmus

Anmerkungen

Verweise

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, und Clifford Stein. Einführung in Algorithmen, Zweite Ausgabe. MIT Press und McGraw -Hill, 1990. ISBN0-262-03293-7. Kapitel 5: Probabilistische Analyse und randomisierte Algorithmen, S. 91–122.
• Dirk Draheim. "Semantik des probabilistischen typisierten Lambda -Kalküls (Markov -Kettensemantik, Terminierungsverhalten und Denotationssemantik)." Springer, 2017.
• Jon Kleinberg und Éva Tardos. Algorithmus Design. Kapitel 13: "Randomisierte Algorithmen".
• Fallis, D. (2000). "Die Zuverlässigkeit randomisierter Algorithmen". Das britische Journal für die Philosophie der Wissenschaft. 51 (2): 255–271. doi:10.1093/bjps/51.2.255.
• M. Mitzenmacher und E. UPFAL. Wahrscheinlichkeit und Computer: Randomisierte Algorithmen und probabilistische Analyse. Cambridge University Press, New York (NY), 2005.
• Rajeev Motwani und P. Raghavan. Randomisierte Algorithmen. Cambridge University Press, New York (NY), 1995.
• Rajeev Motwani und P. Raghavan. Randomisierte Algorithmen. Eine Umfrage zu randomisierten Algorithmen.
• Christos Papadimitriou (1993), Rechenkomplexität (1. Aufl.), Addison Wesley, ISBN 978-0-201-53082-7 Kapitel 11: Randomisierte Berechnung, S. 241–278.
• Rabin, Michael O. (1980). "Probabilistischer Algorithmus zum Testen der Primalität". Journal of Zahlen -Theorie. 12: 128–138. doi:10.1016/0022-314x (80) 90084-0.
• A. A. Tsay, W. S. Lovejoy, David R. Karger, Zufällige Probenahme in Cut-, Fluss- und Netzwerkdesignproblemen, Mathematics of Operations Research, 24 (2): 383–413, 1999.