7.3. Ejemplos de aplicación.
Diseño del algoritmo de ramificación y poda:
- Definir una representación de la solución. A partir de un nodo, cómo se obtienen sus descendientes.
- Dar una manera de calcular el valor de las cotas y la estimación del beneficio.
- Definir la estrategia de ramificación y de poda.
Representación de la solución:
- Mediante un árbol binario: (s1, s2, ..., sn), con si = (0, 1).
Hijos de un nodo (s1, s2, ..., sk): (s1, ..., sk, 0) y (s1, ..., sk, 1).
- Mediante un árbol combinatorio: (s1, s2, ..., sm) donde m?n y
si ? {1, 2, ..., n}.
Hijos de un nodo (s1, .., sk):
(s1, .., sk, sk+1), (s1, ..., sk, sk+2), ..., (s1, ..., sk, n)
7.3.1. Problema de la mochila 0/1.