Las Vegas (algoritmus)

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 24. července 2019; ověření vyžaduje 1 úpravu .

Las Vegas je typ pravděpodobnostního algoritmu (viz také Monte Carlo Algorithms ).

Myšlenka algoritmu Las Vegas je následující. Pokud máme určitý pravděpodobnostní algoritmus , který dává správný výsledek s určitou pravděpodobností, a je možné algoritmicky zkontrolovat správnost výsledku algoritmu (řekněme pomocí algoritmu ), pak můžeme algoritmus provádět, dokud kontrola nezjistí, že výsledek je správný. $A$ $A$ $K$ $A$

Spusťte algoritmus s výsledkem , dokud není pravdivý.

A

r

K(r)

Název tohoto principu byl dán jednak jako narážka na metodu Monte Carlo . Na druhou stranu tento název naráží na "metodu výher v kasinu", která je podobná procesu algoritmu - "pokud budu hrát znovu a znovu, určitě jednou vyhraju."

Je třeba poznamenat, že algoritmus Las Vegas zaručuje správný výsledek. Algoritmus běží v konečném, ale nedeterministickém čase. Můžete zadat pouze pravděpodobnost získání výsledku v daném čase.

Příkladem algoritmu souvisejícího s třídou Las Vegas je třídicí algoritmus Bogosort : data, která mají být seřazena, jsou náhodně zamíchána a poté je zkontrolováno, zda jsou ve správném pořadí. V případě poruchy se míchání mnohokrát opakuje, dokud není dosaženo požadovaného pořadí.

Vztah s algoritmy Monte Carlo

Nechť je algoritmus Las Vegas s očekávanou časovou složitostí , kde je délka vstupu. Pokud se po krocích ( ) zastavíme , dostaneme algoritmus Monte Carlo s pravděpodobností chyby . K prokázání věty uvažujme jako vstup délky a - náhodnou veličinu popisující časovou složitost . Pak matematické očekávání a podle Markovovy nerovnosti : . $\mathcal{A}$ $f(n)$ $n$ $\mathcal{A}$ $\alpha \cdot f(n)$ $0<\alpha<1$ ${\mathcal {B}}$ $1/\alfa$ $X$ $n$ $T$ $\mathcal{A}$ $\mathbb {E} [T]\leqslant f(n)$ $\mathbb {P} r[T\geqslant \alpha \cdot f(n)]\leqslant \mathbb {P} r[T\geqslant \alpha \cdot \mathbb {E} [T]]\leqslant 1 /\alpha$

Odkazy

Příručka Algorithms and Theory of Computation , CRC Press LLC, 1999
"Algorithm Las Vegas" / Dictionary of Algorithms and Data Structures , Paul E. Black, ed., US NIST . 17. července 2006.