Análisis y Diseño de Algoritmos
Algoritmos Probabilísticos
Análisis y Diseño de Algoritmos
En muchos casos, al introducir
elecciones aleatorias en un algoritmo se
pueden obtener mejores rendimientos
que al aplicar el algoritmo determinístico
puro.
Análisis y Diseño de Algoritmos
En general podemos decir que una medida de desempeño para los
algoritmos aleatorios es la esperanza del tiempo de ejecución para una
instancia I del tamaño de la entrada.( I<=n).
Análisis y Diseño de Algoritmos
Cuatro tipos :
1.
Algoritmos NUMERICOS – usa la probabilidad , solución aproximada a base de probar.
2.
MONTECARLO – no nos valen soluciones aproximadas , solo las exactos el algoritmo nos da respuestas que a
veces son correcta , incorrectas o no sabemos.
Respuesta verdadera y falsas
3.
LAS VEGAS – se diferencia de la de MONTECARLO en que las respuestas que dan son siempre verdaderas o no
hay respuesta.
4.
SHERWOOD – problemas en que sabemos que tienen una complejidad diferente en función de cómo entren los
datos de entrada.
Pueden estar los datos ordenados en el caso mejor o peor.
Intercambio los datos de manera que quedan en el caso.
Análisis y Diseño de Algoritmos
Análisis y Diseño de Algoritmos
Análisis y Diseño de Algoritmos
Análisis y Diseño de Algoritmos
Análisis y Diseño de Algoritmos
3. Las Vegas
Un algoritmo tipo Las Vegas siempre entrega la
respuesta correcta, pero no garantiza el tiempo
total de ejecución, aunque con alta probabilidad
éste será bajo.
Análisis y Diseño de Algoritmos
Ej. : ocho reinas
Reinas ( V ( ) : booleano )
Inicio
col  diag 45  diag 135  { 0 }
k0;
repetir
nb  0
desde i  1 hasta 8 hacer
si ( i  col ) && ( 1-k  diag 45 ) && ( i + h  diag 135 ) entonces
nb  nb + 1
si ( uniforme ( 1 , nb ) = = 1 ) entonces
ji
fin si
fin si
fin desde
si nb > 0 entonces
intento [ k + 1 ]  j
col  col  { j } / * ocupada la columna * /
diag 45  diag 45  { j – k } / * ocupada la diag 45º * /
diag 135  diag 135  { j + k } / * ocupada la diag 135 * /
k  k + 1 / * siguiente reina * /
fin si
hasta ( nb = 0 ) || ( k == 8 )
return ( nb > 0 )
fin
Análisis y Diseño de Algoritmos

Tres conjuntos :
- col – columnas ocupadas
- diag 45 – diagonal 45º ocupados
- diag 135 - diagonal 135º ocupados

k – reinas colocadas en el tablero

nb – número de posiciones libres en la fila considerado.

La posición i pertenece a una col ocupada y a una diagonal de 45 grados ( todos
los elementos tienen el mismo valor la resta de la fila y de la columna ) , sino esta libre
la casilla.
nb lo incremento en 1.
Coloco la reina , si el número uniforme ( entre 1 y el número de casillas libres )
responde uno entonces la reina j  i y sigo buscando una casilla libre.
La primera reina se coloca en la primera fila ( entre 1 y 1 )
Análisis y Diseño de Algoritmos
Análisis y Diseño de Algoritmos
4. Montecarlos
Un algoritmo tipo Montecarlo asegura un tiempo fijo
de ejecución, pero no está garantizado que la
respuesta sea correcta, aunque lo puede ser con
alta probabilidad.
Análisis y Diseño de Algoritmos
Ej. : encontrar el elemento mayoritario de un array , es el elemento que se repite en
más de la mitad de las posiciones del array.
if { i  [ 1 .. n ] / T [ i ] = x }  n / 2
mayoritario ( T [ 1 .. n ] , x ) : booleano
k0
desde j  1 hasta n hacer
si T [ j ]  x entonces
k ++
fin si
fin desde
devolver ( k  n / 2 )
fin
Análisis y Diseño de Algoritmos
Función que dado un array nos diga si un elemento es mayoritario
buscarM1 ( T [ 1 .. n ] ) : elemento
inicio
desde i  1 hasta n hacer
si mayoritario ( T , i ) entonces
devolver i
fin si
fin desde
fin
Si esta recorre la mitad del array , si no hay recorre todo el array
Análisis y Diseño de Algoritmos
buscarM2 ( T [ 1 .. n ] ) : elemento
Inicio
x  T [ uniforme ( 1 .. n ) ]
si mayoritario ( T , x ) entonces
devolver x
fin si
fin
50% de posibilidad de acertar , algoritmo 0,5 correcto.
buscarMC ( T [ 1 .. n ] )
devolver T [ uniforme ( 1 .. n ) ]
50% o 0,5 correcto , Tasa de error = 1 / 2
Análisis y Diseño de Algoritmos
Mejorándolo
buscarMC2 ( T [ 1 .. n ] )
inicio
si no mayoritario ( T [ uniforme ( 1 .. n ) ] ) entonces
Devolver T [ uniforme ( 1 .. n ) ]
fin si
fin
Busco dos veces , 75% o 0.75 de que sea correcto , Tasa de Error = 1 / 4
-kPuedo fijar la tasa de error repitiendo x veces el algoritmo
E>2
E – tasa de error
k – número de veces en repetir la búsqueda log2 ( 1 / E )
Análisis y Diseño de Algoritmos
buscarMC3 ( T [ 1 .. n ] , E : real ) : elemento
inicio
k  log2 ( 1 / E ) / * k – tasa de error * /
desde i  1 hasta k hacer / * lo hago hasta k * /
x  T [ uniforme ( 1 .. n ) ]
si mayoritario ( T , x ) entonces
devolver x
fin si
fin desde
devolver x
fin
O ( n log2 ( 1 / E ) )
Descargar

Algoritmo Probabilisticos