Ramificación y poda

Este esquema se utiliza en aquellos problemas en los que se trata de optimizar uno o más criterios para alcanzar la solución. Se puede aplicar en los mismos casos que el esquema voraz pero es menos eficiente que éste. Este esquema explora todos los caminos que permiten llegar a una solución, podando aquellas ramas que no pueden alcanzarla, y además evitando aquellas ramas que sólo podrán alcanzar una solución peor que las que ya se han encontrado.

Las ideas principales de este esquema son:

• Se realiza la exploración del grafo implícito de un problema, buscando la solución óptima del problema.
• Los nodos no se recorren siguiendo el orden de generación, sino que se recorren por orden de prioridad según la función de optimización. Para ello se puede utilizar una cola de prioridad almacenada en un montículo.
• Una vez seleccionado un nodo para explorar, se ramifica generando distintas soluciones parciales, podando aquellas ramas que no pueden alcanzar una solución ni mejorar la solución actual encontrada.
• En cada nodo se calcula una cota optimista de las posibles soluciones que se pueden alcanzar a partir de él.
• Por lo tanto, se realizan dos podas: poda por factibilidad y poda por cota.

A continuación se muestran algunos ejemplos. Puedes acceder a ellos desde el menú superior.

Ejemplos de ramificación y poda

Asignación de Tareas: Pastelería

El problema de asignación de tareas particularizado para una pastelería parte de \(n\) pasteleros que son capaces de preparar \(m\) tipos diferentes de pasteles pero con distintos niveles de destreza. Este algoritmo asigna los próximos \(n\) pedidos, uno para cada pastelero, de la forma más eficiente posible, minimizando el coste total de todos los pedidos.

Problema del Viajante de Comercio

Este problema es similar al problema de los ciclos Hamiltonianos, es decir, dado un grafo, se trata de encontrar un camino que recorra cada nodo exactamente una vez y que termine en el nodo inicial. Pero en este caso la diferencia está en que las aristas tienen asignado un valor y se trata de encontrar el camino de coste mínimo.