Definición de algoritmo aleatorizado (algoritmo probabilista)
Un algoritmo aleatorizado (del inglés randomized algorithm) es un algoritmo que toma, como una de sus entradas, una secuencia de números aleatorios para tomar algunas de sus decisiones. En otras palabras, es un algoritmo que emplea un grado de aleatoriedad como parte de su lógica.
El algoritmo generalmente utiliza bits uniformemente aleatorios como una entrada auxiliar para guiar su comportamiento, con la esperanza de lograr un buen rendimiento en el "caso promedio" sobre todas las opciones posibles de bits aleatorios.
Uno tiene que distinguir entre los algoritmos que usan la entrada aleatoria para que siempre terminen con la respuesta correcta, pero donde el tiempo de ejecución esperado es finito (algoritmos de Las Vegas, cuyo ejemplo es Quicksort), y los algoritmos que tienen una posibilidad de producir un resultado incorrecto (algoritmos de Monte Carlo, ejemplo de lo cual es el algoritmo de Monte Carlo para MFAS) o no puede producir un resultado ya sea señalizando una falla o no terminando.
En el segundo caso, el rendimiento aleatorio y la salida aleatoria, el término "algoritmo" para un procedimiento es algo cuestionable. En el caso de salida aleatoria, ya no es formalmente efectivo. Sin embargo, en algunos casos, los algoritmos probabilísticos son los únicos medios prácticos para resolver un problema.
En la práctica común, los algoritmos aleatorizados se aproximan utilizando un generador de números pseudoaleatorios en lugar de una verdadera fuente de bits aleatorios; tal implementación puede desviarse del comportamiento teórico esperado.
Los algoritmos aleatorizados han ganado popularidad en el campo de la informática debido a su capacidad para resolver problemas complejos de manera eficiente. Además, su naturaleza aleatoria les permite adaptarse a diferentes situaciones y encontrar soluciones óptimas en una amplia gama de escenarios.
Sin embargo, es importante tener en cuenta que la aleatoriedad introducida en estos algoritmos puede generar resultados diferentes en cada ejecución. Esto puede ser un inconveniente cuando se necesita obtener siempre la misma respuesta o cuando se requiere reproducibilidad en los resultados.
A pesar de esto, los algoritmos aleatorizados se utilizan en diversas áreas, como optimización combinatoria, aprendizaje automático y criptografía. En estas disciplinas, la aleatoriedad proporciona una forma eficiente de explorar y buscar soluciones en espacios de búsqueda de gran tamaño.
Es necesario destacar que, si bien los algoritmos aleatorizados pueden mejorar el rendimiento y la eficiencia en muchos casos, también existen situaciones en las que pueden ser superados por algoritmos deterministas. Por lo tanto, es importante evaluar cuidadosamente las ventajas y desventajas de utilizar un enfoque aleatorizado en cada problema en particular.
En resumen, los algoritmos aleatorizados son una herramienta poderosa en el campo de la informática, que utiliza la aleatoriedad como parte de su lógica para encontrar soluciones eficientes. Aunque pueden ser impredecibles en su resultado, su flexibilidad y capacidad de adaptación los convierten en una opción valiosa en muchas aplicaciones.
Ejemplo de algoritmo aleatorizado
Un ejemplo clásico es Quicksort u ordenamiento rápido. Quicksort aplica recursivamente los siguientes tres pasos hasta que alcanza las particiones degeneradas:
- Elija un valor de pivote dentro de la partición.
- Separe los datos en dos nuevas particiones: valores más pequeños o iguales al pivote, y valores más grandes que el pivote.
- Aplique Quicksort recursivamente a las dos particiones creadas en el paso anterior.
* He omitido los detalles complicados para conservar la esencia.
Observe cómo el paso 1 no dice cómo seleccionar el pivote. Solo dice elegir uno. Puede ser cualquier valor que ya esté en la partición.
Podría, por ejemplo, simplemente elegir el primer valor en la partición. Si sus datos de entrada están en un orden arbitrario y sin sentido, ese valor es una opción tan buena como cualquiera. En promedio, aproximadamente la mitad de los datos terminará en un lado, y aproximadamente la mitad en el otro lado.
Pero, si su entrada ya está ordenada, o casi ordenada, eso termina siendo una elección horrible, ya que las particiones que cree en el paso 2 serán muy desequilibradas.
La diferencia entre los dos extremos es grande. Aquí es donde entra la aleatorización.
Puedes evitar elegir consistentemente pivotes malos eligiendo tu pivote aleatoriamente. No cambia la corrección del algoritmo. Pero se resiste consistentemente a elegir pivotes pobres.
Este no es el único enfoque para mejorar Quicksort, pero es el enfoque de algoritmo aleatorizado.
Hay otras maneras de aleatorizar algoritmos.
En cualquier lugar donde tenga una opción arbitraria, puede usar la aleatorización para hacer esa elección en ausencia de un mejor método algorítmico para hacerla. O, tal vez use una heurística la mayor parte del tiempo, y ocasionalmente tome una decisión aleatoria para evitar el comportamiento patológico debido a deficiencias en la heurística.
Un lugar relacionado en el que he utilizado la aleatorización está en problemas de optimización. A menudo, la búsqueda de una solución óptima quedará estancada en un mínimo local. Lo que esto significa es que el algoritmo ha encontrado un resultado que no es óptimo (el mínimo global), pero está atascado cerca de un resultado subóptimo. La aleatorización puede ayudar a sacar el algoritmo de ese mínimo local para ayudarlo a encontrar algo más cercano al mínimo global.
Resumen: algoritmo aleatorizado
Los algoritmos aleatorizados toman decisiones basadas en números aleatorios para lograr un buen rendimiento. Pueden terminar con la respuesta correcta en un tiempo finito (algoritmos de Las Vegas) o pueden producir un resultado incorrecto o no terminar (algoritmos de Monte Carlo). Aunque su efectividad puede ser cuestionable, a veces son la única forma práctica de resolver un problema. En la práctica, se utilizan generadores de números pseudoaleatorios en lugar de fuentes de bits aleatorios.
¿Qué ventajas tiene utilizar un algoritmo aleatorizado?
La principal ventaja de utilizar un algoritmo aleatorizado es que puede ofrecer soluciones más eficientes o incluso mejores en términos de calidad de salida. Al introducir aleatoriedad en el proceso de toma de decisiones, se pueden explorar diferentes caminos y tomar decisiones más rápidas o más óptimas en comparación con los algoritmos deterministas tradicionales.
¿Cuándo es conveniente utilizar un algoritmo aleatorizado?
Se utiliza un algoritmo aleatorizado cuando se enfrenta a problemas complejos en los que no existe un enfoque determinista óptimo conocido o cuando los algoritmos deterministas no son lo suficientemente eficientes. Además, los algoritmos aleatorizados son útiles en problemas de optimización, en los que se busca encontrar la mejor solución posible dentro de un conjunto de posibilidades.
¿Qué se entiende por "grado de aleatoriedad" en un algoritmo aleatorizado?
El grado de aleatoriedad se refiere a la cantidad de decisiones que toma el algoritmo basándose en números aleatorios. Esto puede variar desde algoritmos que utilizan solamente un pequeño número de decisiones aleatorias hasta aquellos que dependen en gran medida de la aleatoriedad. Un mayor grado de aleatoriedad generalmente significa una mayor exploración de posibilidades y, potencialmente, mejores resultados, pero también puede aumentar el tiempo de ejecución.
¿Qué papel juega la secuencia de números aleatorios en un algoritmo aleatorizado?
La secuencia de números aleatorios proporcionada como entrada al algoritmo es esencial para la toma de decisiones aleatorias. Estos números son utilizados por el algoritmo para seleccionar opciones, tomar decisiones o generar variables aleatorias necesarias para resolver el problema en cuestión. La calidad de la secuencia de números aleatorios puede afectar directamente la calidad y la eficiencia del algoritmo aleatorizado.
¿Existe alguna desventaja al utilizar algoritmos aleatorizados?
Una desventaja común de los algoritmos aleatorizados es que su salida puede variar entre diferentes ejecuciones debido a la aleatoriedad introducida. Esto puede dificultar la verificación y la replicación de los resultados. Además, la utilización de aleatoriedad en un algoritmo puede aumentar la complejidad del diseño y la implementación, así como el tiempo de ejecución.
¿Cuál es la diferencia entre un algoritmo aleatorizado y un algoritmo probabilístico?
La diferencia radica en la forma en que se utiliza la aleatoriedad. En un algoritmo aleatorizado, la aleatoriedad se utiliza como parte de la lógica para tomar decisiones específicas durante la ejecución. Por otro lado, un algoritmo probabilístico utiliza probabilidades o distribuciones de probabilidad para calcular directamente el resultado. Los algoritmos probabilísticos suelen ser más precisos, pero también pueden ser más costosos computacionalmente.
Autor: Leandro Alegsa
Actualizado: 09-07-2023
¿Cómo citar este artículo?
Alegsa, Leandro. (2023). Definición de algoritmo aleatorizado. Recuperado de https://www.alegsa.com.ar/Dic/algoritmo_aleatorizado.php
