Tema 6 - Ramificación y Poda

Introducción

ℹ️

Estos algoritmos son una versión mejorada de los de backtracking. Esta vez, a la vez que recorremos las posibles opciones (como en backtracking) también podremos tomar la decisión de dejar de recorrer un camino que sabemos que no contendrá la solución y cuales serán los camino más prometedores

📖

Los algoritmos de B&B (Branch and Bound) son aplicables a los problemas cuya solución pueda expresarse como una n-tupla

Estrategia general

🧠

¿Cómo determino los caminos que debo recorrer?

Para ello introduciremos un concepto llamado cotas el cual nos servirá para tomar dos decisiones.

La primera decisión será determinar que caminos descartaremos ya que es imposible que contengan la solución

La segunda decisión nos servirá para elejir, en el momento en el que tenemos varios caminos, cual es el más prometedor, por lo tanto ese será el que exploraremos primero

💡

En backtracking, recorríamos siempre todos los caminos, aunque por lógica hubiera algunos infactibles. Además, utilizabamos un algoritmo definido para determinar en que orden recorrer los sub-caminos sin tener en cuenta ningún criterio inteligente para elejir una opción sobre obra. Por ejemplo, en el laberinto, siempre recorríamos el laberinto siguiendo este orden (abajo, derecha, arriba, izquierda) cuando con unos sencillos cálculos, podríamos haber elejido un mejor criterio en cada caso

🚧

Cotas

Las cotas son información que calcularemos en base a unos criteros que dependerán del problema, para tratar de predecir si un camino es prometedor, o si por el contrario, es imposible que contenga la solución.

Cota inferior / Mejor cota / Cota optimista
Este valor, es la información que usaremos para determinar si un camino es prometedor
⚠️ El calculo de esta cota es una estimación, por lo que es posible que el camino no fuera tan prometedor como esperabamos. Este valor siempre será optimista por lo que el valor hallado deberá garantizar que no hay otro camino mejor, pero sí que podría ser infactible
💡
Esta cota realmente no va a servir para podar sino para tomar una decisión

Cota superior / Peor cota / Mejor solución
Este valor, también podremos referirnos a el como la mejor solución actual, por lo que si encontramos un camino cuya cota inferior es superior a este valor, sabremos que no vale la pena recorrerlo

💡

Hay que tener en cuenta, que para este algoritmo debemos tener una solución inicial, esta puede ser la peor que se nos ocurra, pero tiene que ser factible

💡

Al contrario que en backtracking, que usa la recursividad para recorrer los caminos, y volver hacia atrás, B&B utiliza una cola de prioridad en base a la mejor cota para recorrer primero los caminos más prometedores

📔

Terminología

Nodo vivo
Aquél que no ha sido podado y que todavía puede ser ramificado (todos los que estén en la cola de prioridad)

Nodo muerto
Aquél que ya no puede generar más hijos por los siguientes motivos
El nodo ya es una solución
A partir de el, el resto de nodos no son factibles
A partir de el, el resto de nodos no generarán mejores soluciones

Nodo en curso/expansión
Aquél que se selecciona para ramificarlo (el primero de la cola de prioridad, o tambíen podemos decir, el último que salió de la cola)

Esquema de la técnica

🏗️

Esquema

Selección
Esta es la función que se aplicará para determinar la prioridad en la cola de un nodo, osea la función que determmina cual es el siguiente nodo en curso/expansión

Cálculo de cotas
Esta es la función que contine el calculo de la cota optimista. Este es el paso posterior a la generación de los nodos hijos, y el paso anterior a la función de poda

Poda
Este es el paso en el que se decartan los hijos cuyas cotas optimistas no son factibles

Ramificación
Este es el paso de añadir los hijos a la cola de prioridad según como de prometedoras son sus cotas optimistas

🏁

Finalización del algoritmo

Tenemos dos opciones para acabar el algoritmo

Cuando se acaba la cola de prioridad, la solución optima será la cota superior (la mejor solución encontrada)

Cuando superamos un umbral de calidad (margen de error). Esta condición hace que no se garantice una solución óptima, pero sí suficientemente buena

🚧

Para empezar a podar es necesario tener una solución inicial o cota general

💡

Este esquema se suele combinar con un algoritmo voraz tanto para hallar la solución inicial, como para el cálculo de la cota optimista

Código

ℹ️

Ejemplo del código de B&B para el problema de la asinación de tareas. En este problema tenemos

n

personas y

m

tareas (en este ejemplo,

n=m

). Cada persona debe hacer una tarea diferente, cada persona tarda un tiempo determinado en hacer cada tarea. El objetivo es minimizar e tiempo total que emplea cada persona en su tarea

💡

Este es el esquema general, no hemos implementado muchas funciones ya que estas dependen del tipo de problema, pero todos ellos seguiran un esquema similar a este

import heapq

def branch_and_bound(costs_matrix):
		n = len(costs_matrix)    # Cantidad de empleados
		m = len(costs_matrix[0]) # Cantidad de tareas

		initial_sol = [None] * n  # Asignación actual de tareas (nodo en curso)
		best_sol = list(range(n))  # Asignación inicial (solución inicial: cada empleado ha sido asignado la misma tarea que se identificador: 1=>1, 2=>2, etc.)
		pq = []  # Creamos la list (las caracteristicas de cola de prioridad se realizaran en cada inserción/extracción)
		heapq.heappush(pq, initial_sol) # Encolamos el elemento inicial (el estado de la solución en el momento en el que se encola el nodo en curso)
		
		# Mientras que en la cola de prioridad haya nodos vivos
		while pq:
			exp_node = heapq.heappop(pq)  # Extraemos un nodo de la cola de prioridad (nodo en expansión)

			# Si el nodo actual es una solución (nodo muerto)
			if isSol(exp_node):
				# Si la solución es mejor que la actual
				if calc_cost(exp_node) < calc_cost(best_sol):
					best_sol = deepcopy(exp_node)
			# Si el nodo actual todavía esta vivo
			else:
				# Realizamos la poda del nodo actual (las condiciones pueden haber cambiado desde que se añadió a la cola, hasta ahora que ha salido, las cotas pueden haberse movido)
				if optimistic_cost(exp_node) < calc_cost(best_sol):
					# Generamos los siguientes nodos dereivados del actual
					for child_sol in calc_childs(exp_node):
						if not is_feasible(child_sol): continue # Poda por criterio de viabilidad como solución
						if optimistic_cost(child_sol) > calc_cost(best_sol): continue	# Poda por criterio de optimalidad (puede contener soluciones, pero no mejores que la actual)
						# Si no se ha podado, entonces se añadirá a la cola de prioridad
						heapq.heappush(pq, child_sol)
						
		# Devolver solución obtenida (distribución de tareas), junto con el coste total
		return best_sol, calc_cost(best_sol)