Las Vegas (algoritm)

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 24 iulie 2019; verificarea necesită 1 editare .

Las Vegas este un tip de algoritm probabilistic (vezi și Algoritmi Monte Carlo ).

Ideea din spatele algoritmului Las Vegas este următoarea. Dacă avem un anumit algoritm probabilist care dă rezultatul corect cu o anumită probabilitate și este posibil să verificăm algoritmic rezultatul algoritmului pentru corectitudine (să zicem, folosind algoritmul ), atunci putem executa algoritmul până când verificarea stabilește că rezultatul este corect. $A$ $A$ $K$ $A$

Rulați algoritmul cu rezultatul până când acesta este adevărat.

A

r

K(r)

Numele acestui principiu a fost dat, pe de o parte, ca o aluzie la metoda Monte Carlo . Pe de altă parte, acest nume face aluzie la „metoda de câștig de cazinou”, care este similară cu procesul algoritmului - „dacă joc din nou și din nou, cu siguranță voi câștiga într-o zi”.

Trebuie remarcat faptul că algoritmul Las Vegas garantează un rezultat corect. Algoritmul rulează în timp finit, dar nedeterminist. Puteți specifica doar probabilitatea de a obține un rezultat într-un timp dat.

Un exemplu de algoritm legat de clasa Las Vegas este algoritmul de sortare Bogosort : datele de sortat sunt amestecate aleatoriu, iar apoi se verifică dacă sunt în ordinea corectă. În caz de eșec, amestecarea se repetă de mai multe ori până se ajunge la ordinea dorită.

Relația cu algoritmii Monte Carlo

Să fie un algoritm Las Vegas cu complexitatea timpului așteptat , unde este lungimea de intrare. Dacă ne oprim după pașii ( ), atunci obținem un algoritm Monte Carlo cu o probabilitate de eroare de . Pentru a demonstra teorema, considerați ca o intrare de lungime și - o variabilă aleatorie care descrie complexitatea timpului a . Apoi așteptarea matematică și conform inegalității lui Markov : . $\mathcal{A}$ $f(n)$ $n$ $\mathcal{A}$ $\alpha \cdot f(n)$ $0<\alpha<1$ ${\mathcal {B}}$ $1/\alpha$ $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 /\alfa$

Link -uri

Manual de algoritmi și teoria calculului , CRC Press LLC, 1999
„Algoritmul Las Vegas” / Dicționar de algoritmi și structuri de date , Paul E. Black, ed., US NIST . 17 iulie 2006.