Page 150 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 150
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
conjunto candidato S es reducido a un solo elemento, o también cuando el nodo
padre para el conjunto S coincide con el nodo hijo. De cualquier forma, cualquier
elemento de S va a ser el mínimo de una función sin S.
El pseudocódigo del algoritmo 7.1 de ramificación y poda es el siguiente:
Algoritmo 7.1. Pseudocódigo de ramificación y poda
donde
• G(x,k) es la función de estimación del algoritmo.
• P es la pila de posibles soluciones.
• esFactible(x,k) es la función que considera si la propuesta es válida.
• esSolución es la función que comprueba si se satisface el objetivo.
• Óptimo es el valor de la función a optimizar evaluado sobre la mejor solución
encontrada hasta el momento.
Subdivisión efectiva
La eficiencia de este método depende fundamentalmente del procedimiento de expansión de nodos
o de la estimación de los nodos padres e hijos. Es mejor elegir un método de expansión que provea
que no se solapen los subconjuntos para ahorrarnos problemas de duplicación de ramas.
144
