7.1. Método general.
CASO 1. Si a partir de un nodo siempre podemos obtener alguna solución válida, entonces podar un nodo i si:
CS (i) ? CI (j), para algún nodo j generado.
Ejemplo: problema de la mochila, utilizando un árbol binario.
- A partir de a, podemos encontrar un beneficio máximo de CS(a)=4.
- A partir de b, tenemos garantizado un beneficio mínimo de CI(b)=5.
- Podemos podar el nodo a, sin perder ninguna solución óptima.
-
CASO 2. Si a partir de un nodo puede que no lleguemos a una solución válida, entonces podemos podar un nodo i si:
CS (i) ? Beneficio (j), para algún j, solución final (factible).
Ejemplo: problema de las reinas. A partir de una solución parcial, no está garantizado que exista alguna solución.