Estrategias de programación

En este artículo veremos las siguientes estrategias de programación:

• Divice y Vencerás.
• Algoritmos Voraces.
• Backtracking o Vuelta Atrás.
• Programación dinámica.
• Tabulación de subprogramas recursivos.

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):

• Una forma de dividir el problema en 2 o más subproblemas de talla menor.
• Una forma directa de resolver problemas triviales o menores de una cierta talla.
• Una forma de combinar las soluciones parciales para llegar a la sol completa.

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:

• Se distinguen 2 casos triviales con solución directa: arbol vacío (elem no encontrado) o raíz del arbol (soluc.).

• Cuando el elemento no se encuentra en el raíz, dividimos el arbol en 2 subárboles (izq y der) y aplicamos ABB sobre aquel que nos interese (al estar ordenado sólo debemos ir por una de las ramas).

• La combinación de resultados es trivial: la solución del subproblema es también la del problema global.

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)

• El caso trivial es un vector de longitud 1 (ya ordenado).
• Si es de mayor longitud, dividimos el vector en 2 partes iguales, cambiando de sitio los elementos para que en la primera parte todos sus elementos sean menores que cualquier elemento de la segunda. Pasamos a resolver cada una de estas partes con Quicksort.
• La combinación de ambas partes ordenadas da el resultado final.

c). Las torres de Hanoi:

• El caso trivial es cuando no hay agujas que mover.
• El problema de pasar n discos de inicial a final se puede dividir en el problema de pasar n-1 discos de inicial a auxiliar y luego pasar estos n-1 discos de auxiliar a final (con el mismo algoritmo).
• La solución para los n discos vendrá de combinar la solución de mover n-1 de inicial a auxiliar, de mover el último disco a final y de mover n-1 discos de auxiliar a final.

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:

• Seleccionar la moneda de mayor valor que no exceda la cantidad restante por devolver, agregar esta moneda a la lista de la solución, y sustraer la cantidad correspondiente a la cantidad que resta por devolver (hasta que sea 0).
• El óptimo local es, en cada etapa, devolver la moneda más grande que no supere la cantidad que queda.

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.

• Poda del árbol de vuelta atrás: Consiste en la eliminación de posibilidades (poda del árbol):
  • Exclusión previa: Tras un análisis previo, puede organizarse la búsqueda para que ignore situaciones infructuosas (ej: problema 8 reinas, cuando ponemos cada dama en una fila diferente).
  • Fusión de ramas: Cuando la búsqueda a partir de diferentes ramas lleve a la misma solución, podemos limitar la búsqueda (por ejemplo en problemas con simetría como el de las 8 reinas o el del PAV).
  • Ramificación y acotamiento: Cuando lo que se busca es una solución óptima, es posible reducir el árbol de búsqueda abandonando las ramas que se sepa con certeza que no llevan hacia soluciones óptimas. (por ejemplo en el problema del viajante podríamos tener una variable T que almacene el valor más óptimo hasta el momento, y abortar un camino en el mismo momento en que se rebase T).
• Reordenación de la búsqueda: Consiste en reorganizar las ramas del árbol de búsqueda de manera que se analicen 1º las situaciones con mejores expectativas. Permite por tanto resolver más rapidamente el problema.

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) &amp;&amp; (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]);
   }
}

<Volver a la sección de Tutoriales de Programación>