V algoritmizace , je Monte-Carlo algoritmus je randomizované algoritmus , jehož doba spouštění je deterministický, ale jehož výsledkem může být nesprávné s určitou pravděpodobností (obvykle minimální). Jinými slovy, algoritmus Monte-Carlo je algoritmus, který využívá zdroj náhody, jehož výpočetní čas je známý od začátku (žádné překvapení o délce výpočtu), jehož výstup však nemusí být reakce na nastolený problém, ale toto je velmi vzácný případ. Výhodou těchto algoritmů je nízká pravděpodobnost selhání a rychlost.
Dva další typy pravděpodobnostních algoritmů jsou rodina algoritmů Las Vegas a skupina algoritmů Atlantic City (en) . Algoritmy Las Vegas trvají náhodné provedení, ale přesto produkují správnou odpověď. Algoritmy Atlantic City dávají pravděpodobně správnou odpověď v pravděpodobně rychlé době obratu. Algoritmus Monte-Carlo lze transformovat do algoritmu Las Vegas, pokud existuje postup schopný ověřit správnost výsledku. Opravdu stačí spustit algoritmus Monte-Carlo, dokud nepřinese správnou odpověď.
Mimochodem, kvalifikace Monte-Carlo odkazuje na Monacké knížectví a jeho slavné kasino s názvem Casino de Monte-Carlo , Mekku hazardních her.
Algoritmus Monte-Carlo má dvě charakteristiky: zaprvé je náhodný , to znamená, že při výpočtu používá náhodný faktor , zadruhé je jeho doba provedení deterministická. Jeho náhodná povaha se projevuje ve výsledku, který může být s určitou pravděpodobností nesprávný (obvykle minimální), ale lze jej důsledně kvantifikovat.
Test Solovay-Strassenovy primality je test, který určuje, zda je dané číslo prvočíslo . Pro prvočísla odpovídá vždy pravdivě , zatímco pro složená (tj. Neprvořadá) čísla odpovídá nepravdivě s pravděpodobností nejméně ½ a true s pravděpodobností maximálně ½. Falešné odpovědi algoritmu jsou tedy správné, zatímco pravdivé odpovědi jsou náhodné; jinými slovy je algoritmus předpjatý směrem k nepravdivé.
Zatímco odpověď vrácená deterministickým algoritmem je vždy přesná, u algoritmů Monte-Carlo tomu tak není, což může být pouze v případě zkreslení. Předpokládejme, že se jedná o řešení rozhodovacího problému, o těchto algoritmech se pak říká, že jsou buď nezaujaté, nebo zaujaté směrem k nepravdě, nebo zaujaté vůči pravdě. Algoritmus Monte-Carlo s nesprávným předpětím je vždy správný, když vrací hodnotu false ; algoritmus vychýlený směrem k true je vždy správný, když vrátí true . Pokud jde o nezaujaté algoritmy Monte-Carlo, jejich odpověď (pravdivá nebo nepravdivá) bude buď nesprávná, nebo správná s určitou omezenou pravděpodobností.
V angličtině mluvíme o jednostranné chybě a oboustranné chybě .
Vzhledem k neobjektivnímu algoritmu Monte Carlo lze jeho pravděpodobnost selhání snížit (a zvýšit jeho pravděpodobnost úspěchu) jeho provedením k krát. Zvažte znovu Solovay-Strassenův algoritmus, který je zaujatý vůči falešnému. Můžeme jej spustit několikrát, aby se vrátil true, pokud odpoví true během k kroků iterace a false jinak. Pokud je tedy číslo prvočíslo, pak je odpověď opravdu správná, a pokud je číslo složené, pak je odpověď správná se zvýšenou pravděpodobností alespoň 1− (1– ½) k = 1−2 −k .
Pro nezaujaté rozhodovací algoritmy Monte Carlo lze pravděpodobnost chyby snížit také spuštěním algoritmu k krát a vrácením odpovědi, která odpovídá většině.
Třída složitosti BPP ( pravděpodobnostní polynomiální čas s omezenou chybou ) popisuje rozhodovací problémy, které lze vyřešit nestranným algoritmem Monte-Carlo v polynomiálním čase, s pravděpodobností omezené chyby.
Třída složitosti RP (pro randomizovaný polynomiální čas ) popisuje problémy, které lze vyřešit s omezenou pravděpodobností chyby pomocí zkresleného algoritmu Monte-Carlo: pokud je správná odpověď nepravdivá , algoritmus to říká, ale může odpovědět nepravdivě v případech kde je správná odpověď pravdivá .
Na druhou stranu třída složitosti ZPP (pro pravděpodobnostní polynomiální čas s nulovou chybou ) popisuje řešitelné problémy v polynomiálním čase pomocí algoritmu Las Vegas. Máme ZPP ⊆ RP ⊆ BPP, ale nevíme, zda jsou tyto třídy složitosti vzájemně odlišné. Jinými slovy, algoritmy Monte-Carlo mohou mít lepší výkon než algoritmy Las Vegas, ale to nebylo prokázáno.
Jinou třídou složitosti je PP (pro polynomiální pravděpodobnost ); popisuje rozhodovací problémy řešené v polynomiálním čase pomocí algoritmu Monte-Carlo, který poskytuje přesnější výsledek než jednoduché losování, ale jehož pravděpodobnost chyby nelze výrazně snížit pod ½.
Pozoruhodné algoritmy Monte-Carlo zahrnují test primality Solovay-Strassen a test primality Miller-Rabin a některé rychlé variace algoritmu Schreier-Sims v teorii výpočetní skupiny .
Řešení problému obchodního cestujícího je obtížné, vzhledem ke složitosti problému může být použití metod pravděpodobnostní optimalizace efektivní při získávání aproximace nejlepšího řešení za kratší dobu než u deterministických metod.
Minimální řezKarger algoritmus je algoritmus Monte Carlo k problému minimálního řezu .