Page 154 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 154
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
estrategia de menor coste o lc
Al utilizar las estrategias FIFO y LIFO se realiza lo que se denomina una búsqueda “a ciegas”, ya que
expanden sin tener en cuenta los beneficios que se pueden conseguir desde cada nodo. Si la ex-
pansión se realizara en función de los beneficios que cada nodo reporta (con una “visión de futuro”),
se podría conseguir en la mayoría de los casos una mejora sustancial.
Es así como nace la estrategia de menor coste o LC (least cost), la cual selecciona, para expandir
entre todos los nodos de la LNV, a aquel que tenga mayor beneficio (o menor coste). Por tanto, ya
no se habla de un avance “a ciegas”.
Esto nos puede llevar a la situación de que varios nodos puedan ser expandidos al mismo tiempo.
De darse el caso, es necesario disponer de un mecanismo que solucione este conflicto:
• Estrategia LC-FIFO: Elige de la LNV el nodo que tenga mayor beneficio; en
caso de empate, se escoge el primero que se introdujo.
• Estrategia LC-LIFO: Elige de la LNV el nodo que tenga mayor beneficio; en
caso de empate, se escoge el último que se introdujo.
ramificación y poda “relajado”
Una variante del método de ramificación y poda más eficiente se puede obtener “relajando” el pro-
blema, es decir, eliminando algunas de las restricciones para hacerlo más permisivo.
Cualquier solución válida del problema original será solución válida para el problema “relajado”, pero
no tiene por qué ocurrir al contrario. Si conseguimos resolver esta versión del problema de forma
óptima, y entonces si la solución obtenida es válida para el problema original, esto querrá decir que
es óptima también para dicho problema.
La verdadera utilidad de este proceso reside en la utilización de un método eficiente que nos resuelva
el problema relajado. Uno de los métodos más conocidos es el de ramificación y corte (branch and
cut).
ramificación y corte
Ramificación y corte es un método de optimización combinatoria para resolver problemas de ente-
ros lineales, los cuales son problemas de programación lineal donde algunas o todas las incógnitas
están restringidas a valores enteros. Se trata de un híbrido de ramificación y poda con métodos de
148
