Ramificacion Y Poda

Algoritmo e Acotación y Ramificación
Uno de las dificultades que suele plantear la técnica de Ramificación y Poda es la implementación de los algoritmos que se obtienen. Para subsanar este problema presentamos una estructura general de tales algoritmos, basada en tres módulos principales:
1. De un lado dispondremos del módulo que contiene el esquema de funcionamiento general de este tipo dealgoritmos.
2. Por otro se encuentra el módulo que maneja la estructura de datos en donde se almacenan los nodos que se van generando, y que puede tratarse de una pila, una cola o un montículo (según se siga una estrategia LIFO, FIFO o LC).
3. Finalmente, necesitamos un módulo que describa e implemente las estructuras de datos que conforman los nodos.
MODULE Esquema;
FROM IO IMPORT WrStr,WrCard, WrLn;
FROM Estruc IMPORT Estructura,Crear,Anadir,Extraer,EsVacia,
Tamano,Destruir;
FROM Nodos IMPORT nodo,NodoInicial,MAXHIJOS,Expandir,EsAceptable,
EsSolucion,h,Eliminar,NoHaySolucion,Imprimir,PonerCota;
VAR numgenerados, (* numero total de nodos generados *)
numanalizados, (* numero total de nodos analizados *)
numpodados:CARDINAL; (*numero total de nodos podados *)
PROCEDURE RyP_una():nodo; (* encuentra la primera solucion *)
VAR E:Estructura; (* estructura para almacenar los nodos *)
n:nodo; (* nodo vivo en curso *)
hijos:ARRAY [1..MAXHIJOS] OF nodo; (* hijos de un nodo *)
numhijos,i,j:CARDINAL;
BEGIN
E:=Crear(); (* inicializamos las estructuras *)
n:=NodoInicial(); Anadir(E,n,h(n)); (*h esla funcion de coste*)
WHILE NOT EsVacia(E) DO
n:=Extraer(E); INC(numanalizados);
numhijos:=Expandir(n,hijos); INC(numgenerados,numhijos);
Eliminar(n);
FOR i:=1 TO numhijos DO
IF EsAceptable(hijos[i]) THEN
IF EsSolucion(hijos[i]) THEN (* Eureka! *)
FOR j:=1 TO numhijos DO (*eliminamos resto de hijos*)
IF i<>j THEN Eliminar(hijos[j]) END;END;
Destruir(E);
RETURN hijos[i] (* devolvemos la solución *)
ELSE
Anadir(E,hijos[i],h(hijos[i]))
END;
ELSE
Eliminar(hijos[i]); INC(numpodados)
END;
END;
END;
Destruir(E);
RETURN NoHaySolucion();
END RyP_una;
(* programa principal del esquema *)
VAR n:nodo;
BEGIN
numgenerados:=0; numanalizados:=0; numpodados:=0;n:=RyP_una();
WrStr("Nodos Generados: "); WrCard(numgenerados,4); WrLn();
WrStr("Nodos Analizados: "); WrCard(numanalizados,4); WrLn();
WrStr("Nodos Podados: "); WrCard(numpodados,4); WrLn();
END Esquema.

Como podemos ver, además de encontrar una solución, el programa calcula tres datos, el número de nodos generados, el número de nodos analizados, y el número de nodos podados,los cuales permiten analizar el algoritmo y poder comparar distintas estrategias y funciones LC.

a) El primero de ellos (numgenerados) nos da información sobre el trabajo que ha tenido que realizar el algoritmo hasta encontrar la solución. Mientras más pequeño sea este valor, menos parte del árbol de expansión habrá tenido que construir, y por tanto más rápido será el proceso.

b) Elsegundo valor (numanalizados) nos indica el número de nodos que el algoritmo ha tenido que analizar, para lo cual es necesario extraerlos de la estructura y comprobar si han de ser podados y, si no, expandirlos. Éste es el valor más importante de los tres, pues indica el número de nodos del árbol de expansión que se recorren efectivamente. En consecuencia, es deseable que este valor sea pequeño.c) Por último, el número de nodos podados nos da una indicación de la efectividad de la función de poda y las restricciones impuestas al problema. Mientras mayor sea este valor, más trabajo ahorramos al algoritmo.

Disponer de esta forma fácil y modular de cambiar las estrategias de selección de los nodos vivos (mediante el módulo “Estruc”) junto con los valores de estos tres parámetros nos...