Un algoritmo tipo Las Vegas es un algoritmo de computación de carácter aleatorio (random) que no es aproximado: es decir, da el resultado correcto o informa que ha fallado.
Características
Un algoritmo de este tipo no especula con el resultado sino que especula con los recursos a utilizar en su computación.
De la misma manera que el método de Montecarlo, la probabilidad de encontrar una solución correcta aumenta con el tiempo empleado en obtenerla y el número de muestreos utilizado. Un algoritmo tipo Las Vegas se utiliza sobre todo en problemas NP-completos, que serían intratables con métodos determinísticos.
Existe un riesgo de no encontrar solución debido a que se hacen elecciones de rutas aleatorias que pueden no llevar a ningún sitio. El objetivo es minimizar la probabilidad de no encontrar la solución, tomando decisiones aleatorias con inteligencia, pero minimizando también el tiempo de ejecución al aplicarse sobre el espacio de información aleatoria.
La clase de complejidad de los problemas de decisión de estos algoritmos con ejecución polinómica es ZPP.
Su esquema de implementación se parece al de los algoritmos de Montecarlo, pero se diferencian de ellos en que incluyen una variable booleana para saber si se ha encontrado la solución correcta.
Referencias
Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999, "Las Vegas algorithm", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 July 2006. (accessed TODAY) Available from: [1]
Datos:Q1241487
Abril 20, 2022
algoritmo, vegas, algoritmo, tipo, vegas, algoritmo, computación, carácter, aleatorio, random, aproximado, decir, resultado, correcto, informa, fallado, características, editarun, algoritmo, este, tipo, especula, resultado, sino, especula, recursos, utilizar, . Un algoritmo tipo Las Vegas es un algoritmo de computacion de caracter aleatorio random que no es aproximado es decir da el resultado correcto o informa que ha fallado Caracteristicas EditarUn algoritmo de este tipo no especula con el resultado sino que especula con los recursos a utilizar en su computacion De la misma manera que el metodo de Montecarlo la probabilidad de encontrar una solucion correcta aumenta con el tiempo empleado en obtenerla y el numero de muestreos utilizado Un algoritmo tipo Las Vegas se utiliza sobre todo en problemas NP completos que serian intratables con metodos deterministicos Existe un riesgo de no encontrar solucion debido a que se hacen elecciones de rutas aleatorias que pueden no llevar a ningun sitio El objetivo es minimizar la probabilidad de no encontrar la solucion tomando decisiones aleatorias con inteligencia pero minimizando tambien el tiempo de ejecucion al aplicarse sobre el espacio de informacion aleatoria La clase de complejidad de los problemas de decision de estos algoritmos con ejecucion polinomica es ZPP Z P P R P n o R P displaystyle ZPP RP no RP Su esquema de implementacion se parece al de los algoritmos de Montecarlo pero se diferencian de ellos en que incluyen una variable booleana para saber si se ha encontrado la solucion correcta Referencias EditarAlgorithms and Theory of Computation Handbook CRC Press LLC 1999 Las Vegas algorithm in Dictionary of Algorithms and Data Structures online Paul E Black ed U S National Institute of Standards and Technology 17 July 2006 accessed TODAY Available from 1 Datos Q1241487 Obtenido de https es wikipedia org w index php title Algoritmo de Las Vegas amp oldid 128334871, wikipedia, wiki, leyendo, leer, libro, biblioteca,
