Page 151 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Idealmente, el procedimiento se detiene cuando todos los nodos del árbol de búsqueda están po-
dados o resueltos. En ese punto, todas las subregiones no podadas tendrán un nodo padre e hijo
iguales a una función global mínima. En la práctica, el procedimiento a menudo termina cuando fina-
liza un tiempo dado, hasta el punto en que el mínimo de nodos hijos y el máximo de nodos padres
sobre todas las secciones no podadas definen un rango de valores que contienen el mínimo global.
Alternativamente, sin superar un tiempo restringido, el algoritmo debe terminar cuando un criterio de
error, tal que el max o min cae bajo un valor específico.

La eficiencia del método depende especialmente de la efectividad de los algoritmos de ramificación
y poda usados. Una mala elección puede llevar a una ramificación repetida, hasta que las subre-
giones se conviertan en muy pequeñas. En ese caso, el método sería reducido a una exhaustiva
enumeración del dominio, que es a menudo impracticablemente larga. No hay un algoritmo de poda
universal que trabaje para todos los problemas, pero existe una pequeña esperanza de que alguna
vez se encuentre alguno. Hasta entonces, se necesitará implementar cada uno por separado para
cada aplicación informática, con el algoritmo de ramificación y poda especialmente diseñado para él.

Los métodos de ramificación y poda deben ser clasificados según los métodos de poda y las ma-
neras de creación/clasificación de los árboles de búsqueda. La estrategia de diseño de ramificación
y poda es muy similar al de vuelta atrás (backtracking), donde el estado del árbol es usado para
resolver un problema. Las diferencias son que el método de ramificación y poda no nos limitan a
ninguna forma particular de obtener un árbol transverso, y es usado solamente para problemas de
optimización.

eStrategIaS de poda

Nuestro objetivo principal será eliminar aquellos nodos que no lleven a soluciones buenas. Podemos
utilizar dos estrategias básicas. Supongamos un problema de maximización donde se han recorrido
varios nodos i = 1,…, n, estimando para cada uno la cota superior CS(xi) e inferior CI(x). Vamos a
i
trabajar sobre un problema sobre el cual se quiere maximizar el valor (si fuese un problema de mini-
mización, entonces se aplicaría la estrategia equivalente).

estrategia 1

Si a partir de un nodo x se puede obtener una solución válida, entonces se podrá podar dicho nodo
i
si la cota superior CS (x) es menor o igual que la cota inferior CI (x) para algún nodo j generado en
i j
el árbol.

145