Análisis y diseño de algoritmos
Esquemas algorítmicos
Academia Newton
Los esquemas de diseño de algoritmos empleados para facilitar el desarrollo de
programas son:
1. Fuerza bruta.
2. Divide y vencerás.
3. Algoritmos voraces o ávidos.
4. Ramificación y poda.
5. Programación dinámica.
6. Algoritmos heurísticos y aproximados.
Divide y vencerás
Para resolver un problema con este esquema se necesita:
1. Descomponer el problema en k subproblemas del mismo tipo y de menor
tamaño.
2. Resolver independientemente todos los subproblemas (directamente o
aplicando “Divide y vencerás”).
3. Combinar las soluciones parecidas obtenidas para construir la solución del
problema original.
Ventajas
1. Claros, legibles y simples.
2. El tamaño en cada paso se reduce por lo tanto tenemos tiempos de ejecución
buenos (polinómicos o logarítmicos), es decir, como cada vez el tamaño del
problema es menor, se tardará cada vez menos, pero el total es la suma.
3. Se pueden transformar “fácilmente” en iterativos (mejora la complejidad espacial y
temporal).
Inconvenientes:
1. Por ser recursivos: tiempo de ejecución y complejidad espacial.
1
Para que el esquema sea eficiente:
1. Los problemas han de ser independientes entre sí.
2. La división en subproblemas debe ser equilibrada, no es necesario que sea
exactamente el mismo tamaño, pero sí lo más parecido posible.
Problema del umbral: averiguar cuando tenemos el caso base.
Esquema general
función divideYVenceras ( X : problema ) : solución
inicio
si esCasoBase ( X ) e ntonces
s ← ResuelveCasoBase ( x )
si no
a ←dividir ( X, subproblema )
para i desde 1 hasta a hacer
solParcial [ i ] ←divideYVenceras ( subproblema [ i ] )
fin para
s ←combinar ( solParcial )
finsi
retorna s
fin
Ecuación de recurrencia
donde,
a es el número de subproblemas.
n/b es el tamaño real de cada problema
cnk es el coste de dividir y combinar
Ejemplos:
2
Búsqueda binaria O(log n)
boolean busqueda ( vector A, int iz, int der, tipoElemento x ) {
int mitad;
if ( iz > der )
return false;
else {
mitad = ( iz + der ) / 2
if ( A[ mitad ] == X )
return true;
else {
if ( A[ mitad ] > X )
return ( busqueda ( A, iz, mitad-1, x ) );
else
return ( busqueda ( A, mitad+1, de, x ) );
}
}
}
Ordenación rápida (Caso mejor: O(n), Caso medio: O(nlogn), Caso peor O(n2))
void orden (Tipovector v, int izq, int der) {
int i, j;
TipoElemento pivote, aux;
if (izq < der) {
i = izq;
j = der;
pivote = v[(izq+der)/2];
do {
while ( v[ i ] < pivote ) i++;
while ( v[ j ] > pivote ) j--;
if ( i < j ) {
aux = v[ i ];
v[ i ] = v[ j ];
v[ j ] = aux;
}
} while ( i < j );
}
void quicksort (tipoVector v) {
orden (v, 0, n-1);
}
3
Multiplicación de enteros grandes
Queremos multiplicar dos números muy grandes de n cifras.
Coste del algoritmo clásico O(n2)
1. Se descomponen ambos números en dos mitades de igual tamaño
w = 105w + x s=n/2
v = 105y + z 0<= x,z <= 105
2. Por tanto w, x, y, z tienen n/2 cifras
3. El resultado es w =1025 wy + 105(wz + xy) +xz
función multiplica ( w, v: entero ): entero
inicio
si ( w ^ v ) son pequeños entonces
return ( multiplicacionClasica( w, v ) );
si no
s ⇠ n/2;
w ⇠ u/105;
y ⇠ v/105;
x ⇠ w % 105;
z ⇠ v % 105;
return (multiplica ( w, y ) 1025 + multiplica ( w, z ) + multiplica ( x, y ) 105 +
multiplica ( x, z ) )
finsi
finsi
fin
Coste:
1. Sumas, multiplicaciones, divisiones y módulos por potencias de 10 ➝O(n)
2. T(n) = 4( T(n/2) + O(n) ) ➝ T(n) ∊ O(n2)
Algoritmo de karatsuba y Ofman T(n) ∊ O(n1,58)
Calculamos “wy”, “wz + xy” y “xz” con menos de cuatro productos. Solo es eficiente si la
longitud del número es menor o igual a 500 dígitos
v = (w+x)(y+z) = wy + ( wz + xy ) + xz
función multiplicarKO ( w, v: entero ): entero
inicio
si u ^ v son pequeños entonces
return ( multiplicacionClasica( w,v ) )
si no
s = n/2;
w = w/105;
y = v/105;
r = multiplicaKO ( w + x, y + z );
p = multiplicaKO ( w, y );
q = multiplicaKO ( x, z );
return (p * 1025 + ( r - p - q ) * 105 +q );
finsi
fin
4
Otros ejemplos de divide y vencerás
1. Multiplicación de matrices cuadradas: algoritmo de Stressen O(n2.811)
2. Ordenación por fusión (Mergesort O(nlogn))
3. Búsqueda de la mediana (en general, problema de la selección)
4. Problema de la organización de torneos
5. Fibonacci NO ES NADA EFICIENTE, NO USAR DIVIDE Y VENCERAS!!!
Voraces
Suelen utilizarse para resolver problemas de optimización, no asociar con solución
óptima (mejor solución).
Los algoritmos voraces construyen la solución en etapas tratando siempre de tomar la
solución óptima para cada etapa. Tomo una decisión a continuación, elijo la opción más
óptima, luego tomo otra decisión, elijo la solución más óptima.
PROBLEMA DEL ENFOQUE MIOPE: como vamos escogiendo la solución óptima en cada
etapa, puede ser que haya elegido mal y me quede al final con un mal resultado.
Ejemplo:
Cogiendo siempre el menor:
1. Si cogemos el 2 y nos quedamos con el 8, no obtenemos el
mínimo global, sería una mala solución.
2. Si hubiésemos cogido el 4 nos quedamos con el 1, pero como no
puedo ver la etapa siguiente, no puedo saberlo.
NUNCA SE VUELVE A RECONSIDERAR UNA DECISIÓN TOMADA.
Elementos que deben identificarse antes:
1. Saber qué hay que optimizar.
2. Saber los c andidatos, elementos que van a formar parte de la solución.
3. Función de selección: función que coge el óptimo local.
4. Factible: comprueba si la solución vale o no.
5. Función solución: nos dice cuando hemos hecho la solución óptima.
6. Función objetivo: si encuentra solución la trata si no, no.
Este método no da siempre la solución exacta (por el enfoque miope).
5
Ventajas:
1. Fáciles de inventar e implementar.
2. Cuando funcionan suelen ser más eficientes, es decir, si encuentran la solución
óptima.
Inconvenientes:
1. Por el enfoque miope puede ser que no encuentre la solución.
Principio de optimalidad: en una secuencia óptima de decisiones, toda subsecuencia ha
de ser óptima también.
Esquema general:
función voraz ( C: Conjunto ): Conjunto
inicio
s Ø//en el conjunto S se construye la solución
mientras ( no solución(S)) y (C≠Ø) ) hacer
x seleccionar(C)
C C - {x}
si factible ( S U {x} ) entonces
S S U {x}
finsi
finmientras
si solución (S) entonces
retorna S
si no
retorna no hay solución
finsi
fin
Backtracking
Se caracteriza por:
1. Se usa para resolver problemas donde la solución se puede expresar como una
secuencia de decisiones generando todas las secuencias de forma sistemática
y organizada.
2. Método de prueba y error, hace un recorrido en profundidad del espacio o árbol de
búsqueda, s i el camino se ha acabado o no puede continuar, retrocede.
3. Si existe solución la encuentra
4. Coste exponencial en el caso peor
5. Puede buscar una solución cualquiera, todas las soluciones, la mejor de todas
las soluciones.
6. Ejemplos de backtracking:
a. Hamiltonian
b. Coloreado de grafos
c. Recorrido del caballo de ajedrez
d. El problema de la mochila 0-1
6
Esquema general:
función vueltaAtras (etapa): boolean
inicio
éxito falso
iniciarOpciones
repetir
seleccionarNuevaOpción
si aceptable e ntonces
anotarOpción
si soluciónCompleta e ntonces
éxito cierto
si no
vueltaAtras ( etapaSiguiente )
si NO éxito entonces
cancelar anotación
finsi
finsi
finsi
hasta ( éxito o últimaOpción )
retorna éxito
fin
Ramificación y poda (Branch and Bound)
Similar a los esquemas con backtracking, pero se podan los caminos que se sabe que no
van a mejorar la solución actual.
1. Nodo vivo: nodo del espacio de soluciones del que no se han generado aún todos
sus hijos.
2. Nodo muerto: nodo del que no se van a generar más hijos porque o no hay más o
no dará una solución mejor que la solución en curso
3. Nodo en curso o en expansión: nodo del que se están generando hijos. Se
generan todos los hijos del nodo en curso antes de que cualquier otro nodo vivo
pase a ser el nuevo nodo en curso. ( No hay retroceso.)
Es necesario almacenar una lista de nodos vivos. Existen distintas estrategias para
elegir el siguiente nodo dentro de la lista de nodos vivos: FIFO, LIFO, Cola de Prioridad,
con función de estimación.
Ramificación y poda utiliza cálculos auxiliares para decidir en cada momento y una cola
de prioridad para almacenar los nodos que se han generado pero no han sido
examinados aún (gestión de nodos vivos), expandiendo en cada momento el nodo vivo
“más prometedor”
La solución es expresable en forma de tupla.
El nodo más prometedor será aquel nodo vivo que tenga un coste estimado mínimo. Si
el coste estimado no es menor que el coste de la mejor solución obtenida hasta el
momento, eso significa que no merece la pena seguir explorando la rama del árbol.
Tipos de costes:
1. Coste-estimado(X): cota inferior al coste de la mejor solución alcanzable desde X.
7
2. Coste-real(X): coste de dicha mejor solución (se calcula recorriendo el subárbol).
3. Coste-optimista(X): cota inferior al coste de la mejor solución alcanzable desde X.
4. Coste-pesimista(X): cota superior del coste de la mejor solución alcanzable desde X
Por tanto, dichas c
otas cumplen: coste-optimista(X) coste-real(X) coste-pesimista(X)
Programación dinámica
Esquema caracterizado por aumentar considerablemente la eficiencia de numerosos
procedimientos recursivos. Este esquema guarda resultados intermedios para que se
puedan reutilizar y así, poder acelerar el cómputo (“memorización”).
Características:
1. Se emplea para problemas de optimización resueltos mediante una secuencia de
decisiones.
2. Se producen varias secuencias de decisiones y solo al final se sabe cual es la
mejor de ellas.
3. Supone una alternativa a divide y vencerás cuando cuando los subproblemas
no son independientes entre sí.
4. Basado en el Principio de optimalidad de Bellman (“En una secuencia de
decisiones óptima toda subsecuencia ha de ser óptima”).
5. Resuelven problemas de tamaño creciente almacenando en una tabla las
soluciones óptimas de esos subproblemas para facilitar la solución de los
problemas mayores.
6. En programación dinámica se evita calcular dos veces un mismo resultado, por
lo que se necesita una tabla de resultados conocidos.
7. La programación dinámica es una técnica ascendente que comienza por los
subcasos más pequeños y sencillos.
Esquema general:
1. La solución se construye como una sucesión de decisiones verificando que estas
cumplen el principio de óptimo.
2. Definición recursiva de la solución.
3. Cálculo del valor de la solución óptima mediante una tabla donde se almacenan las
soluciones parciales a reutilizar.
4. Construcción de la solución óptima a través de la información almacenada en la
tabla.
Ejemplos
1. Fibonacci Divide y vencerás → O(2n) Prog. Dinámica → O(n)
int fib (int n, int T[max]) {
T[1] = T[2] = 1;
j=3
mientras(j =< n) {
T[n] = T[n-1]+T(n-2);
j++;
}
return T[n];
}
2. Warshall, Floyd
3. El problema del cambio: se puede resolver también con un voraz pero solo
funciona en un número limitado de casos.
