TÉCNICAS DE DISEÑO DE ALGORITMOS
Karim Guevara Puente de la Vega
Agenda
Problemas
Fuerza Bruta
Recursividad
Divide y Vencerás
Programación Dinámica
Problemas
De Decisión:
¿183287 es primo?
¿Cuál es el mínimo de la secuencia [7,8,32]?
De optimización:
Hallar el camino más corto
entre Buenos Aires y
Beijing
Ordenar la secuencia:
[1,9,34,-2,6,28]
Elegir o proponer una solución.
Fuerza Bruta
Probar todas las opciones.
Se recorre todo el universo de soluciones posibles.
for cand in generarCandidatos()
if esSolucion(cand)
return cand;
Recursividad
Cuando el problema se puede resolver a través de otros sub
problemas del mismo tipo y estructura.
P.e. calcular xn
public static float elevar (float x, int n) {
if ( n == 0){
return 1;
else
return x * elevar(x, n-1);
}
public static float elevar (float x, int n) {
if ( n == 0){
return 1;
elseif (n es impar )
return x * elevar(x, n-1);
else return elevar(x*x, n/2);
}
Recursividad
Torres de Hanoi
public class TorresDeHanoi {
static void Hanoi( int n, int a, int b, int c ) {
if( n>0 ) {
Hanoi( n-1, a, c, b );
System.out.println( a + " --> " + c );
Hanoi( n-1, b, a, c );
}
}
public static void main( String[] args ) {
Hanoi(Integer.parseInt(args[0]), 1, 2, 3 );
}
}
Recursividad
No todo problema de naturaleza recursiva debe ser resuelto
con un algoritmo recursivo.
Tales programas son fácilmente transformables en una versión
no recursiva.
P.e. cuando no usar recursividad: cálculo de los números de
Fibonacci
public static int Fibonacci(int n){
if (n < 2)
return n;
else
return Fibonacci(n-1) + Fibonacci(n-2);
}
El programa es extremadamente ineficiente.
Recursividad
Versión iterativa
int FibonacciIterativo(int n)
{
int f = 0, i = 1;
for(j = 1; j <= n; j++){
f = f + i;
i = f - i;
}
return f;
}
El programa tiene una complejidad O(n) y de espacio O(1).
Recursividad
Usa una pila para almacenar los datos usados en cada
llamada a un procedimiento que aún no termino.
Todos los datos no globales van a la pila registrando el
estado actual del cálculo
Cuando una activación anterior prosigue, los datos de la pila
son recuperados
Recursividad
Debemos evitar el uso de recursividad cuando existe solución
obvia por iteración
Comparación de versiones recursivas e iterativas:
N 20 30 50 100
Recursiva 1 seg 2 min 21 días 109 años
Iterativa 1/3 mseg ½ mseg ¾ mseg 1.5 mseg
Divide y Vencerás (Divide para Reinar)
Consiste en dividir el problema en partes menores, encontrar
soluciones para las partes y combinarlas en una solución
global.
DV(x){
if (x es suficientemente pequeño) {
return algoritmo_específico(x);
}
else {
descomponer x en {xi, …, xk}
for i = 1 to k
yi ← DV(xi)
y ← recombinar (yi, …, yk)
return y;
}
}
Divide y Vencerás (Divide para Reinar)
P.e.: Multiplicación de número grandes X, Y de n dígitos
Método tradicional : O(n2)
Divide y reinarás?....
X = Xi * 10n/2 + Xd
Y = Yi * 10n/2 + Yd
X * Y = (Xi * 10n/2 + Xd) * (Yi * 10n/2 + Yd)
X * Y = Xi * Yi * 10n + (Xi * Yd + Xd * Yi) *
10n/2 + Xd * Yd
Multiplicación de enteros grandes
P.e.: A = 0981 B=1234
Divide y Venceras
Multplicar Desplazar Resultado
1) 09 12 4 108....
2) 09 34 2 306..
3) 81 12 2 972..
4) 81 34 0 2754
1210554
Dados A*B, A es el multiplicando y B el multiplicador:
n/2 digitosizq(A) * n/2 digitosizq(B) y desplazar_Izq(n digitosB)
n/2 digitosizq(A) * n/2 digitosder(B) y desplazar_Izq(n/2 digitosB)
n/2 digitosder(B) * n/2 digitosizq(A) y desplazar_Izq(n/2 digitosB)
n/2 digitosder(B) * n/2 digitosder(B)
Sumar
Multiplicación de enteros grandes
P.e.: dados X=12345678 y Y=24680135, determinar X*Y
Dividir
X = 12345678 = xi * 104 + xd xi=1234 xd=5678
Y = 24680135 = yi * 104 + yd yi=2468 yd=0135
Combinar
X * Y = (Xi * 104 + Xd) * (Yi *104 + Yd)
= Xi * Yi * 108 + (Xi * Yd + Xd * Yi) *104 + Xd * Yd
Multiplicación de enteros grandes
función multiplica (X,Y,n) {
if (P es pequeño) {
return X*Y;
}else{
Obtener xi, xd, yi, yd; // DIVIDIR
z1 = multiplica (xi, yi, n/2);
z2 = multiplica (xi, yd, n/2);
z3 = multiplica (xd, yi, n/2);
z4 = multiplica (xd, yd, n/2);
aux = suma(z2,z3); // COMBINAR
z1 = desplaza_izq(z1,n);
aux = desplaza_izq(aux,n/2);
z = suma(z1,aux);
z = suma(z,z4);
return z;
}
}
Multiplicación de enteros grandes
función multiplica (X,Y,n) { eficiencia
if (P es pequeño) { O(1)
return X*Y; O(1)
}else{
Obtener xi, xd, yi, yd; O(n)
z1 = multiplica (xi, yi, n/2); T(n/2)
z2 = multiplica (xi, yd, n/2); T(n/2)
z3 = multiplica (xd, yi, n/2); T(n/2)
z4 = multiplica (xd, yd, n/2); T(n/2)
aux = suma(z2,z3); O(n)
z1 = desplaza_izq(z1,n); O(n)
aux = desplaza_izq(aux,n/2); O(n)
z = suma(z1,aux); O(n)
z = suma(z,z4); O(n)
return z; O(1)
}
}
Multiplicación de enteros grandes
Tiempo de ejecución:
El cuello de botella esta en el numero de multiplicaciones de
tamaño n/2.
¿Se podrá mejorar la eficiencia…..?
Reducir el numero de multiplicaciones necesario…
Multiplicación de enteros grandes
r = (Xi + Xd) * ( Yi + Yd) = Xi*Yi * (Xi*Yd + Xd*Yi) + Xd*Yd
p = Xi * Yi
q = Xd * Yd
X * Y = Xi * Yi * 10n + (Xi * Yd + Xd * Yi) * 10n/2 + Xd * Yd
X*Y = p*10n + (r-p-q)*10n/2 + q
Entonces podemos realizar una multiplicación de tamaño n a
partir de 3 multiplicaciones de tamaño n/2.
Multiplicación de enteros grandes
función multiplicaDV (X,Y,n){
if (P es pequeño) {
return X*Y;
} else {
Obtener xi, xd, yi, yd; // DIVIDIR
s1 = suma(xi,xd);
s2 = suma(yi,yd);
p = multiplicaDV (xi, yi, n/2);
q = multiplicaDV (xd, yd, n/2);
r = multiplicaDV (s1, s2, n/2);
aux = suma(r,-p,-q); // COMBINAR
aux = desplaza_izq(aux,n/2);
p = desplaza_izq(p,n);
z = suma(p,aux,q);
return z;
}
}
Multiplicación de enteros grandes
función multiplicaDV (X,Y,n){ eficiencia
if (P es pequeño) { O(1)
return X*Y; O(1)
} else {
Obtener xi, xd, yi, yd; O(n)
s1 = suma(xi,xd); O(n)
s2 = suma(yi,yd); O(n)
p = multiplicaDV (xi, yi, n/2); T(n/2)
q = multiplicaDV (xd, yd, n/2); T(n/2)
r = multiplicaDV (s1, s2, n/2); T(n/2)
aux = suma(r,-p,-q); O(n)
aux = desplaza_izq(aux,n/2); O(n)
p = desplaza_izq(p,n); O(n)
z = suma(p,aux,q); O(n)
return z; O(1)
}
}
Multiplicación de enteros grandes
Divide y Vencerás
Aspectos de diseño
Algoritmo recursivo
División del problema en subproblemas y combinación eficiente
de las soluciones parciales.
• Los subproblemas deben tener, aproximadamente, el mismo tamaño
Algoritmo específico
Para resolver problemas de tamaño pequeño
Determinación del umbral.
Para decidir cuándo finalizar la descomposición recursiva del
problema y aplicar el algoritmo específico
Programación Dinámica
A veces la simple recursividad no es eficiente.
P.e. Números de Fibonacci
fn = fn-1 + fn-2 (n ≥ 2)
f0 = 0
f1 = 1
La definición de la recurrencia conduce inmediatamente a una
solución recursiva
public static int F(int n){
if (n<= 1) return n;
else
return F(n-1)+F(n-2);
}
T(n) = T(n-1) + T(n-2) + 1 n ≥ 2
T(n) = 1 n < 2 O(2n)
Programación Dinámica
Calcula la solución para todos los subproblemas, partiendo
de los subproblemas menores para los mayores,
almacenando los resultados en una tabla.
Una vez que un subproblema es resuelto, la respuesta es
almacenada en una tabla y nunca más es recalculado.
public static int F(int n, int []fib){
if (n<= 1) return 1;
fib[0] = 0;
fin[1] = 1;
for( int j=2; j<=n; ++j )
fib[j] = fib[j-1] + fib[j-2];
return fib[n]; O(n)
}
Programación Dinámica
Calcula la solución para todos los subproblemas, partiendo
de los subproblemas menores para los mayores,
almacenando los resultados en una tabla.
Una vez que un subproblema es resuelto, la respuesta es
almacenada en una tabla y nunca más es recalculado.
public static int F(int n, int []fib){
if (n<= 1) return 1;
fib[0] = 0;
fin[1] = 1;
for( int j=2; j<=n; ++j )
fib[j] = fib[j-1] + fib[j-2];
return fib[n]; O(n)
}
Programación Dinámica
Calcula la solución para todos los subproblemas, partiendo
de los subproblemas menores para los mayores,
almacenando los resultados en una tabla.
Una vez que un subproblema es resuelto, la respuesta es
almacenada en una tabla y nunca más es recalculado.
public static int F(int n, int []fib){
public static int F(int n, int []fib){
if (n<= 1) return 1;
if (n<= 1) return 1;
fib[0] = 0;
if (fib[n-1] ==-1)
fin[1] = 1;
fib[n-1] = F(n-1,fib);
for( int j=2; j<=n; ++j )
if (fib[n-2] ==-1)
fib[j] = fib[j-1] + fib[j-2];
fib[n-2] = F(n-2,fib); O(n)
return fib[n];
fib[n] = fib[n-1] + fib[n-2];
}
return fib[n];
}
Programación Dinámica
P.e. Problema de la mochila
Objeto Peso Valor
Se dispone:
1 1 15
Capacidad mochila = 8
2 5 10
3 3 9
4 4 5
Problema de la mochila
Wi representa el peso del objeto i
Ci es el costo del objeto i
M es la capacidad de la mochila
n es el número de objetos.
B[i,w] es el máximo valor obtenido cuando se seleccionan
objetos de 1 a i y cuyo peso máximo no sobrepasa la
capacidad de la mochila, donde 0 ≤ i ≤ n y 0 ≤ w ≤ M
B[i,w] = max(B[i-1,w],C[i] + B[i-1, w-W[i]]
Problema de la mochila
i/w 0 1 2 3 4 5 6 7 8
Objeto Peso Valor
0 0 0 0 0 0 0 0 0 0
1 1 15
1 0
2 5 10
2 0
3 3 9 3 0
4 4 5 4 0
B[i,w] = max(B[i-1,w],C[i] + B[i-1, w-W[i]]
Para i, w > 0:
si w-Wi < 0 Entonces
B[i,w] = B[i-1,w]
sino
B[i,w] = max(B[i-1,w],C[i] + B[i-1, w-W[i]]
Ejemplo- Problema de la mochila
Para i = 1 y w = 1, el peso y costo del objeto 1 son W1 = 1 y C1 = 15.
Como w – W1 = 0 entonces:
B[1,1] = max (B[0,1], C1 + B[0,0]) = max (0,15+0) = 15
.......
Para i = 3 y w = 4, el peso y el costo del objeto 3 son W3 = 3 y C3 = 9.
Como w – W3 = 1 > 0 entonces:
B[3,4] = max (B[2,4], C3 + B[2,1]) = max (15, 9+15) = 24
Ejemplo- Problema de la mochila
public static ProgDin(int []W, int []C, int n, int M) {
int [][] B = new int [n+1] [M+1]
for(int i=0; i<=n; i++)
B[i][0] = 0;
for(int i=0; i<=M; i++)
B[0][i] = 0;
for(int i=1; i<=n; i++)
for(int w=1; w<=M; w++)
if( w – W[i] < 0 )
B[i][w] = B[i-1][w];
else
if( B[i-1][w] > (C[i] + B[i-1][w-W[i]]) )
B[i][w] = B[i-1][w];
else
B[i][w] = C[i] + B[i-1][w-W[i]];
return B;
}
Problema de la mochila – ítems seleccionados
Hacer k = capacidad máxima mochila (k=8)
i=n
Si B[4,8] ≠ B[3,8]: // B[i,k] ≠ B[i-1,k]
ítem 4 debe estar en la mochila
reducir la capacidad menos el peso del ítem 4
k = k – W4 = 8 - 4 = 4
probar el ítem anterior
i = i – 1 = 4 – 1 = 3
Problema de la mochila – ítems seleccionados
Como B[3,4] B[2,4] entonces el item 3 en la mochila.
k = k – W3 = 4 – 3 = 1
Problema de la mochila – ítems seleccionados
Si B[2,1] = B[1,1] entonces el item 2 no entra en la mochila.
i = i – 1 = 2 – 1 = 1
Problema de la mochila – ítems seleccionados
Los valores de B[1,1] B[0,1] entonces el item 1entra a la
mochila.
k = k – W1 = 1 – 1 = 0
Problema de la mochila – ítems seleccionados
Entonces la combinación de objetos que maximizan el robo
es:
Problema de la mochila
Para encontrar los items que fueron seleccionados hacemos
uso del algoritmo Backtrace
public static boolean[] ObjSel(int []W, int [][]B, int n, int M){
boolean X[] = new boolean[n];
int i = n; int k = M;
while (i > 0 && k > 0 ){
if ( B[i][k] != B[i-1][k] ){
X[i-1] = true; //{item i esta en la mochila};
k = k - W[i-1];
}
else
X[i-1] = false;
i--;
}
return X;
}
Pasos del diseño del algoritmo
El diseño de un algoritmo de Programación Dinámica consta
de los siguientes pasos:
Planteamiento de la solución como una sucesión de decisiones y
verificación de que ésta cumple el principio de óptimo.
Definición recursiva de la solución.
Cálculo del valor de la solución óptima mediante una tabla en
donde se almacenan soluciones a problemas parciales para
reutilizar los cálculos.
Construcción de la solución óptima haciendo uso de la
información contenida en la tabla anterior.
