Algorisme de Las Vegas

L' algorisme de Las Vegas és un algorisme de computació de caràcter aleatori que no és aproximat: és a dir, o dona el resultat correcte, o informa que ha fallat.

Característiques

Aquest algorisme no especula amb el resultat sinó que especula amb els recursos a utilitzar en la computació d'aquest.

Els algorismes de Las Vegas van ser presentats per László Babai el 1979, per determinar si dos grafs finits són isomorfs, com una versió més potent del mètode de Monte Carlo, i igual que en aquest, la probabilitat de trobar una solució correcta augmenta amb el temps emprat en obtenir-la i el nombre de mostreig utilitzat. L'algorisme de Las Vegas s'utilitza sobretot en problemes de complexitat NP, que serien intractables amb mètodes deterministes.

Hi ha un risc de no trobar solució, ja que es fan eleccions de rutes aleatòries que poden no dur enlloc. L'objectiu és minimitzar la probabilitat de no trobar la solució, prenent decisions aleatòries amb intel·ligència, però minimitzant també temps d'execució a aplicar-se sobre l'espai d'informació aleatòria.

La classe de complexitat dels problemes de decisió d'aquest algorisme amb execució polinòmica és ZPP.

$ZPP=RP*no-RP$

El seu esquema d'implementació s'assembla al dels algorismes de Monte Carlo, però es diferencien d'ells en que inclouen una variable Booliana per saber si s'ha trobat la solució correcta.

Enllaços externs

• (anglès) Algorithms and Theory of Computation Handbook , CRC Press LLC, 1999, "Las Vegas algorithm", a Dictionary of Algorithms and Data Structures