¿Qué es un algoritmo aleatorio?


La aleatoriedad y análisis probabilístico son temas que se involucran en muchas áreas de las ciencias de la computación incluyendo al diseño de algoritmos, se pueden considerar algoritmos aleatorizados o aleatorios a aquellos tradicionales que se enfrentan a entradas generadas aleatoriamente y en otro caso algoritmos que se comportan al azar, es decir el medio ofrece la misma entrada pero podemos permitir que tome decisiones al azar ya una vez que procesa la entrada; al permitir una asignación al azar el modelo se vuelve más potente, así que los problemas que pueden no haber sido resueltos mediante algoritmos deterministas eficientes aún pueden ser susceptibles de algoritmos aleatorios.

Los algoritmos aleatorizados a diferencia de los convencionales tienen una entrada adicional que son los números aleatorios y que se obtienen durante la ejecución, es decir, se usa algún grado de aleatoreidad como parte de su lógica; es importante decir que este tipo de algoritmos son la base esencial de la simulación.

Realizan operaciones o toman decisiones distintas de forma aleatoria, se pueden utilizar cuando no es posible explorar todas las posibilidades o resulta ser costosa.

Por ejemplo, supongamos tenemos dos puertas y detrás de una de ellas hay un premio y en la otra no hay nada, nuestro interés está en descubrir ese premio, un algoritmo determinista abriría una puerta y luego la siguiente, en el peor de los casos las dos puertas serían abiertas. Con un algoritmo aleatorio existe la misma posibilidad que tenemos cuando lanzamos una moneda al aire, es posible que en nuestro primer intento podamos abrir la puerta correcta y obtener el premio sin necesidad de abrir la siguiente.

Aplicando esta misma idea en el problema de encontrar el número 5 en una matriz (M) de N elementos, donde:

M = [3, 4, 1, 5, 2]

Podemos resolver para este ejemplo de dos maneras, uno es seleccionar aleatoriamente un elemento de los N definidos, o en todo caso posicionarnos en el primer elemento e incrementar en 1 hasta encontrarlo.

De manera aleatoria donde en el mejor de los casos lo encontraremos en el primer elemento aleatorio seleccionado, en el peor de los casos en el mismo número de iteraciones que si incrementamos, lo que aleatorizar nuestro algoritmo mejora sus posibilidades.

Anuncios

Acerca de silvercorp

Blog personal de Ye§i creado el 18/Ag/06 enfocado al diseño gráfico, tecnología y programación.

Publicado el agosto 20, 2013 en Programación. Añade a favoritos el enlace permanente. 1 comentario.

  1. me parece que el peor de los casos del algoritmo aleatorio seria que lo haga a las 5 vez… el caso de ir incrementando lo encuentra a la 4 vez nada mas.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: