Las Vegas (algoritm)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 24 juli 2019; verifiering kräver 1 redigering .

Las Vegas är en typ av probabilistisk algoritm (se även Monte Carlo Algorithms ).

Tanken bakom Las Vegas-algoritmen är följande. Om vi har en viss probabilistisk algoritm som ger det korrekta resultatet med en viss sannolikhet, och det är möjligt att algoritmiskt kontrollera resultatet av algoritmen för korrekthet (säg, med hjälp av algoritmen ), då kan vi exekvera algoritmen tills kontrollen fastställer att resultatet är korrekt. $A$ $A$ $K$ $A$

Kör algoritmen med resultatet tills det är sant.

A

r

K(r)

Namnet på denna princip gavs å ena sidan som en anspelning på Monte Carlo - metoden . Å andra sidan anspelar detta namn på "kasinovinnande metoden", som liknar processen för algoritmen - "om jag spelar igen och igen kommer jag definitivt att vinna någon gång."

Det bör noteras att Las Vegas-algoritmen garanterar ett korrekt resultat. Algoritmen körs i ändlig men icke-deterministisk tid. Du kan bara ange sannolikheten för att få ett resultat under en given tid.

Ett exempel på en algoritm relaterad till Las Vegas-klassen är Bogosort- sorteringsalgoritmen : data som ska sorteras blandas slumpmässigt och sedan kontrolleras om de är i rätt ordning. I händelse av fel upprepas blandningen många gånger tills önskad ordning uppnås.

Relation med Monte Carlo-algoritmer

Låt vara en Las Vegas-algoritm med förväntad tidskomplexitet , där är ingångslängden. Om vi slutar efter stegen ( ), får vi en Monte Carlo-algoritm med en felsannolikhet på . För att bevisa satsen, betrakta som en indata av längd och - en slumpmässig variabel som beskriver tidskomplexiteten för . Sedan den matematiska förväntan och enligt Markov ojämlikhet : . $\mathcal{A}$ $f(n)$ $n$ $\mathcal{A}$ $\alpha \cdot f(n)$ $0<\alfa<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 /\alfa$

Länkar

Algorithms and Theory of Computation Handbook , CRC Press LLC, 1999
"Las Vegas algorithm" / Dictionary of Algorithms and Data Structures , Paul E. Black, red., US NIST . 17 juli 2006.