La figura 13.2 muestra esto con una división (ramificación) en subproblemas, mediante un árbol (definido en la sección 10.2) con ramas (arcos) desde todos los nodos (correspondientes al problema completo que contiene todas las soluciones factibles) a los dos nodos correspondientes a los dos subproblemas. Este árbol que hará *crecer sus ramas* en cada interación se conoce como el árbol de soluciones (o árbol de enumeración) para el algortimo. La variable que se usa para hacer la ramificación en una iteración al asignarle valores (como con x1) se llama variable de ramificación.
Más adelante se verá que uno de estos subproblemas se puede vencer (sondear) de inmediato, mientas que el otro requiere una nueva división en subproblemas más pequeños estableciendo x2 = 0 o x2 = 1, etc.
No hay comentarios.:
Publicar un comentario