Ramificación y poda

Este esquema algorítmico se utiliza en problemas en los que buscamos la optimización en la solución que queremos encontrar.

Estos algoritmos de ramificación y poda son menos eficientes que los algoritmos voraces por lo que su aplicación está indicada solamente cuando no se pueda resolver el problema con algoritmos voraces.

Al igual que en los algoritmos de vuelta a atrás se exploran todas las alternativas que permiten llegar a la solución pero ahora en lugar de cortar la exploración de los caminos que no llevan a una solución, se evita la de aquellos que llegan a unas soluciones peores que otras ya que aquí lo que perseguimos es la optimización.

Por regla general la ramificación y poda la podemos encuadrar cómo un esquema para explorar un grafo dirigido implícito. En este caso se busca la solución óptima del problema que tenemos entre manos y vamos explorando los nodos de acuerdo a la función que se quiere optimizar estableciendo así preferencias entre los nodos que nos quedan por visitar. La búsqueda se va dirigiendo por el nodo más prometedor por lo que requiere una cola de prioridad para gestionar los nodos. Una vez que se selecciona un nodo se procede con una fase de ramificación en las que se generan las soluciones parciales a dicho nodo, a continuación se podan (eliminan) las ramas que no pueden llegar a una solución y aquellas que no pueden llegar a una solución mejor. Por ello en cada nodo vamos calculando una cota optimista del posible valor de las soluciones que se pueden construir a partir de él y que nos permitirá ver si se puede encontrar una solución mejor o no por lo que no tendría sentido seguir mirando y se realizaría la poda.

Problemas típicos que se resuelven con este tipo de algoritmos son la asignación de tareas, selección de tareas, distancia de edición, etc.

Si queréis que profundicemos más en este tipo de algoritmos no dudéis en ponerlo en los comentarios.

;)