El Algoritmo probabilista
Definición
Un algoritmo probabilista (o probabilístico) es un algoritmo que basa su resultado en la toma de algunas decisiones al azar, de tal forma que, en promedio, obtiene una buena solución al problema planteado para cualquier distribución de los datos de entrada. Es decir, al contrario que un algoritmo determinista, a partir de unos mismos datos se pueden obtener distintas soluciones y, en algunos casos, soluciones erróneas.
Tipos de algoritmos probabilísticos
Existen varios tipos de algoritmos probabilísticos dependiendo de su funcionamiento, pudiéndose distinguir:
- Algoritmos numéricos, que proporcionan una solución aproximada del problema.
- Algoritmos de Montecarlo, que pueden dar la respuesta correcta o respuesta erróneas (con probabilidad baja).
- Algoritmos de Las Vegas, que nunca dan una respuesta incorrecta: o bien dan la respuesta correcta o informan del fallo.
Consideraciones
Se puede optar por la elección aleatoria si se tiene un problema cuya elección óptima es demasiado costosa frente a la decisión aleatoria. Un algoritmo probabilista puede comportarse de distinta forma aplicando la misma entrada.
- A un algoritmo determinista nunca se le permite que no termine: hacer una división por 0, entrar en un bucle infinito, etc.
- Si existe más de una solución para unos datos dados, un algoritmo determinista siempre encuentra la misma solución (a no ser que se programe para encontrar varias o todas).
- Un algoritmo probabilista puede encontrar soluciones diferentes ejecutándose varias veces con los mismos datos.
- A un algoritmo determinista no se le permite que calcule una solución incorrecta para ningún dato.
- Un algoritmo probabilista puede equivocarse siempre que esto ocurra con una probabilidad pequeña para cada dato de entrada.
- Repitiendo la ejecución un número suficiente de veces para el mismo dato, puede aumentarse tanto como se quiera el grado de confianza en obtener la solución correcta.
- El análisis de la eficiencia de un algoritmo determinista es, en determinadas ocasiones, difícil.
- El análisis de los algoritmos probabilistas es, a menudo, muy difícil.
