Los algoritmos probabilísticos, al tener que tomar en cuenta decisiones con aleatoriedad involucrada, son algoritmos que pueden a veces fallar y tomar más recursos de lo normal, o bien, por pura casualidad se toma el camino con los mejores resultados y sabio uso de los recursos del computador.
Entre los tantos tipos de algoritmos que existen, están los que se basan en pura probabilidad. Estos algoritmos tienen que ver con el manejo de aleatoriedad y tratar de alcanzar de forma no determinista una solución al problema. Entre ellos, también, existen tipos de algoritmos probabilísticos los cuales tienen, cada uno, distinto tipo de acercamientos a la solución de un problema.
Estos son algoritmos que podrían ayudar a obtener respuestas suficientemente buenas sin consumir los recursos que hubiera necesitado un algoritmo determinista:
-
Probabilista Numérico:
Solución aproximada al cálculo de valores del conjunto I (números irracionales).
Este tipo de algoritmo ayuda a encontrar un valor suficientemente aproximado al valor de la variable que queremos utilizar. La precisión va a aumentar conforme el algoritmo se ejecute y podrá garantizar un resultado cercanamente apropiado.
-
Probabilista Las Vegas:
Su respuesta siempre es correcta, pero existen algunos casos en que puede decidir no responder. Esto se debe a que el algoritmo a veces no sabe como proseguir, entonces no da una respuesta.
En el problema de las 8 reinas, por ejemplo, en lugar de ir analizando todas las posiciones con backtracking, se puede generar aleatoriamente la posición de un subconjunto de todas las posibles. Naturalmente, puede no llegarse a una respuesta.
-
Probabilista Monte Carlo:
Siempre van a dar una respuesta, pero esta puede ser equivocada.
Toma una decisión aleatoria, pero esto no significa que se obtenga el resultado esperado. Este es mayoritariamente utilizado cuando no se puede determinar un mecanismo Las Vegas para una respuesta.
-
Probabilistas SherWood:
Estos algoritmos siempre dan una respuesta y siempre es correcta. Se utilizan para tomar una decisión en un conjunto de datos donde queremos hacer una eliminación de candidatos buenos y malos.
QuickSort, por ejemplo, elige el valor de más a la derecha o izquierda como pivote. Una posibilidad para que el algoritmo no sea determinístico y tal vez obtenga mejor resultado, es elegir el pivote de forma aleatoria. Existe una probabilidad de que caiga en el valor medio, y esto nos llevaría a obtener una mejor respuesta. Debido a que no importa quien se elija como pivote, siempre se llega a una respuesta.
Dependiendo del problema y si se puede aplicar un algoritmo probabilístico a este, hay que saber cuál de ellos encaja mejor y utilizarlo para tratar de llegar a una respuesta.
En algunos casos, hay alternativas aleatorias que nos pueden ayudar a obtener respuestas suficientemente correctas en escenarios particulares: puede ser equivocada o no. Es posible que se tenga un acercamiento aleatorio a un problema y genere una ganancia mayor a la respuesta exacta.
Referencias
Brassard, G., & Bratley, P. (2000). Fundamentos de Algoritmia. Upper Saddle River, NJ, Estados Unidos: Prentice Hall.
Campos, J. (2017). Algoritmos Probabilistas. https://webdiis.unizar.es/asignaturas/EDA/ea/slides/8-Algoritmos%20probabilistas.pdf
Academic. (s. f.). Algoritmo probabilista. Recuperado 12 de diciembre de 2020, de https://esacademic.com/dic.nsf/eswiki/65691