Monte Carlo algoritm

Ej att förväxla med Monte Carlo-metoden .

Vid beräkning är en Monte Carlo-algoritm en randomiserad algoritm vars utdata kan vara felaktig med en viss (vanligtvis liten) sannolikhet . Två exempel på sådana algoritmer är Karger–Stein-algoritmen och Monte Carlo-algoritmen för minsta återkopplingsbågeuppsättning .

Namnet syftar på det storslagna kasinot i Monacos furstendöme vid Monte Carlo, som är välkänt runt om i världen som en ikon för hasardspel. Termen "Monte Carlo" introducerades först 1947 av Nicholas Metropolis .

Las Vegas-algoritmer är en dubbel av Monte Carlo-algoritmer som aldrig returnerar ett felaktigt svar. Däremot kan de göra slumpmässiga val som en del av sitt arbete. Som ett resultat kan tiden det ta variera mellan körningarna, även med samma input.

Om det finns en procedur för att verifiera om svaret som ges av en Monte Carlo-algoritm är korrekt, och sannolikheten för ett korrekt svar är gränsad över noll, så kommer med sannolikhet ett att köra algoritmen upprepade gånger medan du testar svaren så småningom ge ett korrekt svar . Huruvida denna process är en Las Vegas-algoritm beror på om ett stopp med sannolikhet anses uppfylla definitionen.

Ensidigt vs tvåsidigt fel

Även om svaret som returneras av en deterministisk algoritm alltid förväntas vara korrekt, är detta inte fallet för Monte Carlo-algoritmer. För beslutsproblem klassificeras dessa algoritmer i allmänhet som antingen falskt -biased eller sant -biased. En falskt partisk Monte Carlo-algoritm är alltid korrekt när den returnerar false ; en sann -biased algoritm är alltid korrekt när den returnerar sant . Även om det här beskriver algoritmer med ensidiga fel , kanske andra inte har någon partiskhet; dessa sägs ha dubbelsidiga fel . Svaret de ger (antingen sant eller falskt ) kommer att vara felaktigt eller korrekt, med viss begränsad sannolikhet.

Till exempel används Solovay–Strassen-primalitetstestet för att avgöra om ett givet tal är ett primtal . Det svarar alltid sant för primtalsinmatningar; för sammansatta indata svarar den falskt med sannolikhet minst 1 ⁄ 2 och sant med sannolikhet mindre än 1 ⁄ 2 . Således falska svar från algoritmen säker på att vara korrekta, medan de sanna svaren förblir osäkra; detta sägs vara en . 1⁄ 2 -korrekt falskt partisk algoritm

Förstärkning

För en Monte Carlo-algoritm med ensidiga fel kan misslyckandesannolikheten minskas (och framgångssannolikheten förstärkas) genom att köra algoritmen k gånger. Betrakta återigen Solovay–Strassen-algoritmen som är 1 ⁄ 2 -korrekt falskt partisk . Man kan köra denna algoritm flera gånger och returnera ett falskt svar om det når ett falskt svar inom k ​​iterationer, och annars returnera sant . Alltså, om talet är primtal är svaret alltid korrekt, och om talet är sammansatt är svaret korrekt med sannolikhet minst 1−(1− 1 ⁄ 2 ) k ⁼ 1−2 ^−k .

För Monte Carlo-beslutsalgoritmer med dubbelsidigt fel kan felsannolikheten återigen minskas genom att köra algoritmen k gånger och returnera majoritetsfunktionen för svaren.

Komplexitetsklasser

Komplexitetsklassen BPP beskriver beslutsproblem som kan lösas med polynom-tids Monte Carlo-algoritmer med en begränsad sannolikhet för tvåsidiga fel , och komplexitetsklassen RP beskriver problem som kan lösas av en Monte Carlo-algoritm med en begränsad sannolikhet på ett -sidigt fel: om det korrekta svaret är falskt säger algoritmen alltid det, men den kan svara felaktigt i vissa fall där det korrekta svaret är sant . Däremot beskriver komplexitetsklassen ZPP problem som kan lösas av Las Vegas-algoritmer för förväntad polynomtid. ZPP ⊆ RP ⊆ BPP , men det är inte känt om någon av dessa komplexitetsklasser är skild från varandra; det vill säga, Monte Carlo-algoritmer kan ha mer beräkningskraft än Las Vegas-algoritmer, men detta har inte bevisats. En annan komplexitetsklass, PP , beskriver beslutsproblem med en polynom-tids Monte Carlo-algoritm som är mer exakt än att vända ett mynt men där felsannolikheten inte nödvändigtvis kan avgränsas från 1 ⁄ 2 .

Tillämpningar i beräkningsmässig talteori

Välkända Monte Carlo-algoritmer inkluderar Solovay-Strassen-primalitetstestet, Baillie-PSW-primalitetstestet , Miller-Rabin-primalitetstestet och vissa snabba varianter av Schreier-Sims-algoritmen i beräkningsgruppteori .

Se även

• Monte Carlo metoder , algoritmer som används i fysisk simulering och beräkningsstatistik baserade på att ta stickprov
• Atlantic City algoritm
• Las Vegas algoritm

Källor

•   Motwani, Rajeev ; Raghavan, Prabhakar (1995). Randomiserade algoritmer . New York : Cambridge University Press. ISBN 0-521-47465-5 .
•   Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). "Kapitel 5. Probabilistisk analys och randomiserade algoritmer". Introduktion till algoritmer (2:a upplagan). Boston : MIT Press och McGraw-Hill. ISBN 0-262-53196-8 .
•   Berman, Kenneth A.; Paul, Jerome L. (2005). "Kapitel 24. Probabilistiska och randomiserade algoritmer". Algoritmer: Sekventiella, parallella och distribuerade . Boston : Kursteknik. ISBN 0-534-42057-5 .