DICCIONARIO DE INFORMÁTICA Y TECNOLOGÍA
  ¿Qué significa algoritmo aleatorizado? - Información sobre algoritmo aleatorizado

Definición de algoritmo aleatorizado (algoritmo probabilista)

Leandro Alegsa (Contacto) 2018-07-17

Envíanos un mensaje


Enviar
Anuncios

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.


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.





¿Mejoramos la definición?
Puntos: 0 (0 votos)







Respondemos tus consultas o comentarios a continuación:


¿Dudas? ¿necesita más información? Escriba y responderemos a tu email: clic aquí



 




  Diccionario de informática
  Búsqueda por letras:

A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z - 0,9
 
Búsqueda por categorías
:

Almacenamiento - Aplicaciones - Audio - Compresión - Desarrollo web - Discos ópticos - Inteligencia Artificial - Memorias - Microprocesadores - Seguridad informática - Sistemas de archivos - Terminología de programación - UNIX - Windows - ver categorías

 
Búsqueda por palabras:






Preguntas

No hay ningún comentario todavía

Todos los derechos reservados © 1998 - 2018 - ALEGSA - Santa Fe, Argentina.
Políticas del sitio web - Contacto - Publicidad