En este artículo veremos las siguientes estrategias de programación:
Es el esquema algorítmico más popular y el más utilizado de todos. "Si un problema es demasiado difícil para resolverlo directamente, hay que dividirlo en partes más pequeñas que sean más fáciles de resolver, uniendo todas las soluciones parciales para obtener la solución final". Así pues, el problema se descompone en n subproblemas más pequeños que una vez resueltos se combinan para obtener la solución del problema completo. El caso más interesante es aquel en que los n subproblemas son en esencia idénticos al problema original, y es donde la recursividad juega un papel muy importante (busqueda binaria, ABB, quicksort, etc.).
Se distinguen 3 partes en un algoritmo DV (Divide y Vencerás):
void DV( tipo_datos D, tipo_solucion *S ) { tipo_dato d1, d2, ..., dn; tipo_solucion s1, s2, ..., sn; if( se puede resolver directamente D ) *S = Solucion directa else { (d1,d2,dn...) = dividir(D); DV(d1, &s1 ); (etc.) DV(dn, &sn); *S = combinar( s1,s2,sn); } }
Problemas que se ajustan a este esquema:
a). Busqueda binaria
Ejemplo: Arbol Binario de Búsqueda:
b). Ordenación por partición (QuickSort):
Algoritmo de QuickSort para ordenar vectores:
if( V es de tamaño 1) V ya está ordenado. else { Dividir V en 2 bloques A y B, (con todos los elementos de A < B) } Ordenar A y B usando QuickSort Devolver V ya ordenado (concatenación A-B)
c). Las torres de Hanoi:
La estrategia de estos algoritmos es básicamente iterativa. Funcionan por etapas. En cada etapa se toma la decisión que parece mejor, sin tener en cuenta las consecuencias futuras. Es decir, para cada una de las etapas se busca el mínimo local en esa etapa, pensando que todos los mínimos locales nos lleven al mínimo global.
void Voraz( tipo_datos D, tipo_solucion *S) { Generar la parte inicial de la solución *S (y las condiciones iniciales) while( D sin procesar del todo ) { Extraer el óptimo local T de D Procesar T (reduciéndose D). Incorporar T a la solución *S } }
Problemas que se ajustan a este esquema:
a). El problema del cambio:
Consideremos el problema de dar el cambio, que consiste en:
b). El problema de la mochila continua:
Se desea llenar una mochila de volumen V. Para ello se dispone de n objetos en cantidades limitadas de volúmenes v1,v2,vn y cuyos valores por unidad de volumen son p1,p2,pn. Se puede seleccionar una cantidad ci (real) con tal de que ci ⇐ vi y ci ⇐ Vr, siendo Vr el volumen de la mochila todavía libre. El problema consiste en determinar las cantidades c1,c2,cn que llenan la mochila, es decir, que Sum(ci)=V maximizando el valor de Sum(ci·pi) total.
Puede solucionarse fácilmente mediante una estrategia voraz en que se seleccione sucesivamente el objeto de mayor valor por unidad de volumen que quede, y en la máxima cantidad posible, hasta agotar el mismo o llenar la mochila, repitiendolo hasta el llenado o hasta que no queden más objetos.
c). El problema de la mochila discreta:
(cuando no podemos aportar cantidades contínuas de cada objeto):
Ahora disponemos de n-clases de objetos. Para cada clase i de objetos, disponemos de ni piezas indivisibles (nº natural), que ocupa cada una de ellas un volumen vi y cuyo valor por pieza es pi. El objetivo es el mismo que el anterior: maximizar el valor de los objetos introducidos en la mochila, es decir, conseguir que Sum(ci·pi) sea máximo, siendo ci⇐ni, y teniendo en cuenta que Sum(ci·vi)⇐ V.
Para este caso, la solución de la mochila continua obtiene una solución que no tiene porqué ser la mejor.
d). Árbol de extensión mínima (algoritmo de Prim):
Problema del cálculo del árbol de extensión mínima en un grafo no dirigido con peso: "Dado un grafo no dirigido con peso, hay que encontrar un conjunto de arcos que conecten todos los vértices de manera que la suma de sus pesos sea mínima".
Algoritmo de PRIM:
Empieza con el arco de menor coste.
Mientras no esté completa la red que conecta todos los nodos:
Selecciona un nuevo tramo.
Fin Mientras
En cada nuevo paso, se selecciona el tramo de menor peso siempre y cuando tenga como extremo uno de los vértices cubiertos ya, y de acceso a un nuevo vértice no cubierto hasta ahora.
e). El problema del agente viajante (PAV):
Se pretende, sobre un grafo no dirigido con pesos en sus arcos, encontrar un ciclo simple que incluya todos los vértices (ciclo de Hamilton) y en donde la suma de los pesos de las aristas sea un mínimo. Utilizando una estrategia voraz podemos encontrar una solución incluso para un gran número de ciudades, pudiendo no ser la más óptima para el problema, pero si mucho menos costosa computacionalmente que explorar todas las posibilidades.
Los algoritmos de vuelta atrás (backtracking) hacen una búsqueda sistemática de todas als posibilidades, sin dejar ninguna por considerar. Cuando intenta una solución que no lleva a ningún sitio, retrocede deshaciendo el último paso, e intentando una nueva variante desde esa posición (es normalmente de naturaleza recursiva).
Esta técnica ofrece un método para resolver problemas tratando de completar una o varias soluciones por etapas. En cada paso se intenta extender una solución parcial de todos los modos posibles, y si ninguno resulta satisfactorio se produce la vuelta atrás hasta el último punto donde quedaban alternativas por explorar. Es una mejora de la búsqueda completa de soluciones y una alternativa a los algoritmos voraces.
Problemas que se ajustan a este esquema:
a). El problema del cambio:
Supongamos que el cajero sólo tiene billetes de 2000, 5000 y 10000 y nos debe dar 21.000 pts. Con una estrategia voraz nunca llegaría a la solución correcta (daría 2 de 10.000 y no podría dar el resto), mientras que con backtracking podemos ir dando billetes (empezando por el mayor valor posible) y si llegamos a una combinación sin solución, volvemos atrás intentándolo con el segundo billete más grande, y así sucesivamente.
b). El problema de las 8 reinas:
"Sobre un tablero de ajedrez hay que colocar 8 reinas de forma que ninguna de ellas se amenace." Como cada reina estará en una fila diferente, podemos representar la solución con un vector de columnas donde están situadas las según la fila. Para resolverlo se situaría la dama sobre la primera fila y se colocaría la segunda dama en un lugar donde no amenace a las demás. Si no encontramos solución parcial, volvemos un paso atrás y nos replanteamos la solución de la etapa anterior (una nueva posición).
Void Reinas8( int i, int S[9], int *halladaSol) { int col=0; *halladaSol = 0; while(! (*halladaSol) || col != 8 ) col = col +1; if( puede situarse la dama i en la posición [i,col] sin estar amenazada por las anteriores) S[i] = col; if( i == 8 ) *halladaSol = 1; else Reinas8(i+1, S, halladaSol ); }
c). El problema del agente viajante (PAV):
Podemos intentar todas las combinaciones posibles, obteniendo un árbol completo donde los nodos terminales serían las ciudades de partida, y asociados a los mismos los kilómetros asociados al camino desde el raíz a ese nodo.
La idea de la técnica de "dividir y vencer" es llevada al extremo en la programación dinámica. Si en el proceso de resolución del problema resolvemos un subproblema, almacenamos la solución, por si esta puede ser necesaria de nuevo para la resolución del problema. Estas soluciones parciales de todos los subproblemas se almacenan en una tabla, sin tener en cuenta si va a ser realmente necesarias posteriormente en la solución total.
Con el uso de esta tabla se evitan hacer cálculos idénticos reiteradamente, mejorando así la eficiencia en la obtención de la solución. También sirve para convertir ciertas funciones recursivas en iterativas.
Ejemplo: Cálculo de los 100 primeros nºs primos, donde almacenamos cada primo encontrado en una tabla y dividimos cada nuevo número sólo por los que hay en la tabla (y no por todos los menores que él) para saber si es primo:
void primos( int n ) { int tabla[N]; int i, j, nprimos = 0; for( i=2; i<=n; i++ ) { j = 0; while( (j<nprimos) && (i % tabla[j]!=0 ) j++; if( j == nprimos ) { tabla[nprimos] = 1; nprimos++; printf("..."); } } }
En ocasiones una función recursiva genera llamadas repetidas en el transcurso de la búsqueda de una solución, como en el caso de la función de Fibonacci. Para evitar pérdida de cálculo computacional, guardamos en una tabla cada solución parcial obtenida en el proceso de cálculo de la solución final. Comenzaremos la tabla desde los términos 0 y 1 hasta llegar a n (inversamente al cálculo normal). Siguiendo este orden evitamos la recusión creando una versión interativa de la función.
int Fib( int n ) { int i, tabla[N]; if( n<=1 ) return( 1 ); else { tabla[0] = tabla[1] = 1; for( i = 2; i<=n; i++ ) tabla[i] = tabla[i-2] + tabla[i-1]; return(tabla[n]); } }