7.1. Método general.

Esquema general. Problema de minimización, suponiendo el caso en que existe solución a partir de cualquier nodo.

RamificacionYPoda (NodoRaiz: tipo_nodo; var s: tipo_solucion);

LNV:= {NodoRaiz};

C:= CS (NodoRaiz);

s:= ?;

Mientras LNV ? ? hacer

x:= Seleccionar (LNV); { Según un criterio FIFO, LIFO, LC-FIFO ó LC-LIFO }

LNV:= LNV - {x};

Si CI (x) < C entonces { Si no se cumple se poda x }

Para cada y hijo de x hacer

Si y es una solución final mejor que s entonces

s:= y;

C:= min (C, Coste (y) );

Sino si y no es solución final y (CI(y) < C) entonces

LNV:= LNV + {y};

C:= min (C, CS (y) );

FinPara;

FinMientras;

Diapositiva anterior Diapositiva siguiente Ir a la primera diapositiva Ver versión gráfica