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

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Por ejemplo, supongamos el problema de la mochila en el cual se busca una ganancia maximima,
donde utilizamos un árbol binario. Entonces, si a partir de x se puede encontrar un beneficio máximo
i
de CS (x) = 4 y a partir de x se tiene asegurado un beneficio mínimo de CI (x) = 5, esto nos llevará a
i j j
la conclusión de que se puede podar el nodo x sin que perdamos ninguna posible solución óptima.
i

estrategia 2

Si se obtiene una posible solución válida para el problema con un beneficio B, entonces se podrán
j
podar aquellos nodos x cuya cota superior CS (x) sea menor o igual que el beneficio que se puede
i i
obtener B (este proceso sería similar para la cota inferior).
j

estrategias de ramificación

Como se comentó en la introducción de este apartado, la expansión del árbol con las distintas es-
trategias está condicionada por la búsqueda de la solución óptima. Debido a esto, todos los nodos
de un nivel deben ser expandidos antes de alcanzar un nuevo nivel, lo cual es lógico, ya que para
poder elegir la rama del árbol que va a ser explorada se deben conocer todas las ramas posibles.

Todos estos nodos que se van generando y que no han sido explorados se almacenan en lo que se
denomina lista de nodos vivos (a partir de ahora LNV), nodos pendientes de expandir por el algorit-
mo. La LNV contiene todos los nodos que han sido generados, pero que no han sido explorados
todavía. Según como estén almacenados los nodos en la lista, el recorrido del árbol será de uno u
otro tipo, lo cual da lugar a las tres estrategias que se detallan a continuación.

estrategia fIfo

En la estrategia FIFO (first in first out), la LNV será una cola, lo cual da lugar a un recorrido en anchura
del árbol.

146