Download Backtracking

Algoritmos de Búsqueda
“Backtracking y Branch and Bound”
Antonio Paredes Risueño
Índice





Introducción
Backtracking
Backtracking en paralelo
Branch and Bound
Branch and Bound paralelo
Introducción



Los algoritmos de Backtracking y Branch and Bound se suelen
aplicar en la resolución de un gran número de problemas,
muy especialmente en los de optimización.
Estos algoritmos realizan una búsqueda exhaustiva y
sistemática en el espacio de soluciones del problema.
Suelen ser muy ineficientes.
Introducción


Se utilizan para resolver problemas para los que no existe un
algoritmo eficiente para resolverlos.
Mediante la programación paralela se intentará reducir el
tiempo de ejecución de estos algoritmos
Índice





Introducción
Backtracking
Backtracking en paralelo
Branch and Bound
Branch and Bound paralelo
Backtracking



Técnica general de resolución de problemas, que suele
aplicarse sobre todo a juegos y problemas de óptimización.
Realiza una búsqueda exhaustiva y sistemática en el espacio
de soluciones del problema.
La solución de un problema de backtracking se puede
expresar como una tupla (x1,x2,…,xn), que satisface una
restricciones R(x1,x2,…,xn) y a veces optimizando una función
objetivo.
Backtracking

En cada momento el algoritmo se encontrará en un cierto
nivel k, con una solución parcial (x1,x2,…,xk) (con k<=n).




Si puede añadirse un elemento xk+1 a la solución parcial se avanza
al nivel k+1.
Si no se prueban otros valores válidos para xk.
Si no existe ningún valor que sea válido por probar, se retrocede al
nivel anterior k-1.
Se continua con este proceso hasta que la solución parcial sea una
solución del problema o hasta que no queden más posibilidades por
probar (en el caso de que no se encuentre ninguna solución o se
busquen todas las soluciones del problema).
Backtracking

x1
x2
x3
En definitiva, el algoritmo realiza una búsqueda en
profundidad en el árbol de soluciones del problema.
Backtracking

En definitiva, el algoritmo realiza una búsqueda en
profundidad en el árbol de soluciones del problema.
1
x1
2
x2
x3
3
4
10
6
5
7
8
11
9
14
12
13
15
16
17
18
Backtracking. Complejidad



Por realizar una búsqueda exhaustiva en el espacio de
soluciones del problema, los algoritmos de backtracking son
bastante ineficientes.
En general, se tienen tiempos con órdenes de complejidad
factoriales o exponenciales.
Por esto, los algoritmos de backtracking se utilizan en
problemas para los que no existen un algoritmo eficiente
que los resuelva.
Backtracking. Ejemplo
Problema N-Reinas



El problema de las N-Reinas consiste en colocar n reinas en
un tablero de ajedrez de tamaño n*n de forma la reinas no se
amenacen según las normas del ajedrez. Se busca encontrar
una solución o todas las soluciones posibles.
Este problema puede resolverse utilizando un esquema de
backtracking.
Cualquier solución del problema estará formada por una
n-tupla (x1,x2,…,xn), dónde cada xi indica la columna donde
la reina de la fila i-ésima es colocada.
Backtracking. Ejemplo
Problema N-Reinas


Las restricciones para este problema consisten en que dos
reinas no pueden colocarse en la misma fila, ni en la misma
columna ni en la misma diagonal.
Por ejemplo, el problema de las 4-Reinas tiene dos posibles
soluciones: [2,4,1,3] y [3,1,4,2].
Backtracking. Ejemplo
Problema N-Reinas
Backtracking. Ejemplo
Problema N-Reinas
1
2
6
3
4
5
7
8
9
10
14
15
17
11
12
13
Soluciones
16
Índice





Introducción
Backtracking
Backtracking paralelo
Branch and Bound
Branch and Bound paralelo
Backtracking paralelo





Esquema no puramente paralelo, es un esquema utilizado en
programación secuencial que se intenta paralelizar.
Esto supone que la ganancia de tiempo no sea tan elevada
como se pudiera esperar a priori.
Se intenta distribuir el espacio de búsqueda entre los distintos
procesadores, de forma que cada uno busque la solución del
problema en un subespacio de soluciones distinto.
Así se exploran varias ramas del árbol de soluciones al mismo
tiempo por distintos procesadores.
Aumentan las posibilidades de encontrar la solución del
problema en menor tiempo.
Backtracking paralelo
Backtracking paralelo
P0
P1
Backtracking paralelo


Un factor crítico a la hora de formular un algoritmo de
backtracking en paralelo es cómo se realizará la distribución
del espacio de búsqueda entre los distintos procesadores.
Dos alternativas:


Asignación estática
Asignación dinámica
Backtracking Paralelo
Asignación estática





Un procesador expande el nodo raíz y genera varios nodos.
A cada procesador se le asigna un número de estos nodos.
Así se divide el espacio de búsqueda global entre los distintos
procesadores.
Cada procesador comienza a buscar la solución en el espacio
de búsqueda que le corresponda, siguiendo el proceso normal
de backtracking.
No se necesitan comunicaciones entre procesos.
Backtracking Paralelo
Asignación estática



Problema: No se sabe a priori si se divide el espacio de
búsqueda equitativamente entre los distintos
procesadores.
Puede haber desequilibrio entre la carga de trabajo de los
procesadores.
A un procesador puede que se le asigne poco trabajo y
este la mayor parte de tiempo inactivo.
Backtracking Paralelo
Asignación estática
P0
P1
Backtracking Paralelo
Asignación estática
P0
P1
Backtracking Paralelo
Asignación dinámica



Cada procesador trabaja en una parte del espacio de
búsqueda.
Cuando un procesador termina de trabajar, solicita más
trabajo a otro procesador que tiene más trabajo.
Proceso:



Cada procesador dispone una pila en su espacio local para
guardar nodos no expandidos.
Cuando un procesador expande un nodo, los nuevos nodos
que se crean se introducen en la pila.
Cuando la pila de un procesador esta vacía, el procesador
solicita nodos de la pila de otro procesador.
Backtracking Paralelo
Asignación dinámica



Al principio, el espacio total de búsqueda es asignado a un
procesador y a los demás procesadores no se les asigna
ningún trabajo.
Ese procesador será el encargado de distribuir inicialmente
el trabajo cuando los demás procesadores se lo soliciten.
A los procesos que envían trabajo se les denomina
donadores y a los que lo solicitan y lo reciben se les
denomina receptores.
Backtracking Paralelo
Asignación dinámica

Un procesador puede estar en 2 estados:



Activo: Esta realizando algún trabajo.
Inactivo: Al procesador no le queda ningún nodo por explorar
en su pila y esta solicitando trabajo a otros procesadores.
Estado inactivo:



El procesador selecciona un procesador donador y le envía una
petición de trabajo.
Si recibe trabajo del donador, se activa y comienza a trabajar.
Si recibe un mensaje de reject (el procesador donador esta
inactivo), selecciona a otro procesador donador para enviarle
una petición de trabajo.
Backtracking Paralelo
Asignación dinámica

Estado inactivo:

Este proceso se repite hasta que el procesador recibe trabajo
del donador o hasta que todos los procesadores entran en
estado inactivo.
Backtracking Paralelo
Asignación dinámica

Estado activo:




El procesador realiza una cantidad de trabajo fijo (expande un
nº determinado de nodos).
Cuando termina de realizar el trabajo, chequea si existen
peticiones de trabajo a cargo de los demás procesadores.
Si recibe alguna petición de trabajo, el procesador donador
particiona en dos partes su pila de nodos, y envía una parte al
procesador que realizo la petición.
Cuando el procesador ha recorrido todo su espacio de
búsqueda (su pila esta vacía), entra en estado inactivo.
Backtracking Paralelo
Asignación dinámica
Servicio pendiente de
recibir mensajes
Procesador
Activo
Procesador
Inactivo
Termina el
trabajo
disponible
Realizar una cantidad
de trabajo fija
Seleccionar un
procesador y solicitarle
trabajo
Comienza a
trabajar
Servicio pendiente de
recibir mensajes
No existe trabajo
disponible
Enviar una petición
Backtracking Paralelo
Asignación dinámica


Cuando un procesador encuentra la solución, envía un
mensaje de broadcast a todos procesadores para estos
paren la búsqueda.
Si no se recibe este mensaje, el algoritmo terminará cuando
todos los procesos estén en estado inactivo.
Backtracking Paralelo

Los algoritmos paralelos de búsqueda en un árbol de
soluciones tienen 2 características fundamentales que
determinan su rendimiento:


La estrategia utilizada para dividir el trabajo de un procesador
cuando éste recibe una petición de trabajo.
El esquema usado para determinar el procesador donador
cuando un procesador entra en estado inactivo.
Estrategia de División del trabajo




Cuando un procesador donador recibe una petición de
trabajo de otro procesador y tiene nodos su pila, el
procesador donador divide su pila en dos y una de ellas se
envía al proceso que realizo la petición.
Si se envía poco trabajo, el receptor rápidamente pasa a
estar en estado inactivo.
Si se envía demasiado trabajo, el donador entrará
rápidamente en estado inactivo.
Lo ideal sería dividir la pila en dos partes iguales de modo
que el espacio de búsqueda representado por cada una sea
el mismo.
Backtracking Paralelo
Estrategia división de trabajo




A este método se le llama “División por la mitad”.
Pero la dificultad reside en estimar el tamaño que tendrán
los subarboles asociados a cada uno de los nodos que se
encuentran en la pila.
Normalmente los nodos cercanos al fondo de la pila (nodos
con profundidad cercana al nodo raíz del procesador) tienen
más posibilidades de generar árboles de mayor tamaño.
Los nodos más cercanos al tope de la pila (nodos que están
a mayor profundidad) tienen más posibilidades de generar
árboles de menor tamaño.
Backtracking Paralelo
Estrategia división de trabajo



Para evitar mandar cantidades pequeñas de trabajo, los
nodos de la pila que están más allá de una determinada
profundidad no son enviados.
A esta profundidad se le llama “cota de profundidad”.
Algunas estrategias posible para la división del trabajo son:




Enviar nodos cercanos al fondo de la pila
Enviar nodos cercanos a la cota de profundidad.
Enviar la mitad de los nodos que están entre el fondo de la
pila y la cota de profundidad.
La idoneidad de una estrategia u otra dependerá de la
naturalidad del espacio de búsqueda.
Backtracking Paralelo
Estrategia división de trabajo
1
2
4
Pila
3
5
3
5
7
6
8
10
12
13
7
11
9
11
14
9
Cota de
profundidad
13
14
Backtracking Paralelo
Esquemas de balanceo de carga


Los esquemas de balanceo de carga se utilizan para decidir
que procesador donador se elige cuando un procesador
entra en estado inactivo.
Algunos esquemas posibles son los siguientes:



Round Robin Asíncrono
Round Robin Global
Selección aleatoria
Round Robin Asíncrono




Cada procesador mantiene una variable local llamada
“target”.
Cuando un procesador termina de trabajar, usa el valor de
su variable “target” para determinar el procesador donador
al que enviar la petición de trabajo.
Cada vez que se envía una petición, se incrementa en una
unidad el valor de la variable “target” del procesador:
target = ((target+1) modulo p)
El valor inicial de target será:
target0 = ((nº procesador+1) modulo p)
Round Robin Global




Existe una única variable “target” almacenada en el
procesador P0.
Cuando un procesador necesita trabajo, solicita y recibe el
valor de la variable target de P0.
Una vez que se sabe cual es el procesador donador, el
procesador le envía una petición de trabajo.
Luego, P0 incrementa la variable target antes de responder a
otra petición.
target = ((target+1) modulo p)
Round Robin Global


Este esquema garantiza que sucesivas peticiones de trabajo
se distribuyen uniformemente entre todos los procesadores.
La desventaja principal de este esquema es que el
procesador P0 debe gestionar todas las peticiones de acceso
a la variable target, y esto puede convertirse en un cuello
de botella.
Selección aleatoria




Es el esquema más simple de todos
Cuando un procesador entra en estado inactivo, se elige un
procesador al azar.
Cada procesador tiene la misma probabilidad de ser
seleccionado como donador.
Así se asegura que las peticiones se distribuyan
uniformemente.
Backtracking Paralelo
Detección de terminación



Cuando un procesador encuentra una solución del problema
se envía un mensaje de broadcast a todos los procesadores
para indicarle que terminen.
Pero cuando no se encuentra ninguna solución. ¿Cómo
detectar cuando termina el proceso de búsqueda?
A continuación se describen dos algoritmos para detectar la
terminación de la búsqueda.


Algoritmo de terminación de Dijkstra´s.
Algoritmo de terminación basado en árbol.
Algoritmo de terminación de Dijkstra´s




Los procesadores se organizan en un anillo lógico y se irán
pasando un token.
Un procesador puede estar en dos estados: blanco o negro.
Un token también puede estar en dos estados: blanco o
negro.
Inicialmente todos los procesadores están en estado blanco.
Algoritmo de terminación de Dijkstra´s

El algoritmo es el siguiente:





Cuando P0 esta inactivo, el procesador crea un token y envía
un token blanco al procesador P1.
Si el procesador Pi envía trabajo al procesador Pj (i>j), el
procesador Pi cambia a estado negro.
Si el procesador Pi tiene el token y esta inactivo, pasa el token
al Pi+1. Si Pi está en estado negro, el color del token se
establecerá a negro antes de pasarlo a Pi+1. Si Pi esta en
estado blanco, el token se pasa sin cambiarlo.
Cuando Pi pasa el token a Pi+1 pasa a estado blanco.
El algoritmo termina cuando a P0 le llega un token blanco.
Algoritmo de terminación basado en árbol





Se asocia un peso a cada procesador.
Inicialmente, P0 tiene todo el trabajo y se le asocia un peso
de 1.
Cuando Pi particiona y manda trabajo a otro procesador, Pi
se queda con la mitad del peso y la otra mitad se la envía al
otro procesador.
Cuando un procesador termina su trabajo, se devuelve el
peso al procesador del que se recibió el trabajo.
El algoritmo termina cuando el peso del procesador P0
vuelve a ser 1.
Algoritmo de terminación basado en árbol
w0=0.5
w1=0.5
Algoritmo de terminación basado en árbol
w0=0.5
w1=0.5
w0=0.5
w1=0.25
w2=0.25
Algoritmo de terminación basado en árbol
w0=0.5
w1=0.5
w0=0.5
w1=0.25
w2=0.25
w0=0.25
w1=0.25
w2=0.25
w3=0.25
Algoritmo de terminación basado en árbol
w0=0.5
w0=0.5
w1=0.5
w1=0.25
w2=0.25
w0=0.25
w1=0.5
w3=0.25
w0=0.25
w1=0.25
w2=0.25
w3=0.25
Algoritmo de terminación basado en árbol
w0=0.5
w0=0.5
w1=0.5
w1=0.25
w2=0.25
w0=0.25
w1=0.5
w1=0.25
w2=0.25
w0=0.5
w3=0.25
w0=0.25
w1=0.5
w3=0.25
Algoritmo de terminación basado en árbol
w0=0.5
w0=0.5
w1=0.5
w1=0.25
w2=0.25
w0=0.25
w1=0.5
w1=0.25
w2=0.25
w0=0.5
w3=0.25
w0=0.25
w1=0.5
w0=1
w3=0.25
Índice





Introducción
Backtracking
Backtracking paralelo
Branch and Bound
Branch and Bound paralelo
Branch and Bound




Técnica similar a Backtracking
Suele utilizarse en problemas de optimización.
Este esquema puede verse como una mejora del esquema de
backtracking.
Al igual que en backtracking, el algoritmo realiza una
búsqueda sistemática en un árbol de soluciones.
Branch and Bound

Pero Branch and Bound añade dos características nuevas:



Estrategia de ramificación: La búsqueda se guiará por
estimaciones de beneficio que se harán en cada nodo.
Estrategia de poda: Para eliminar nodos que no lleven a a la
solución óptima. Estimación de cotas de beneficio en cada
nodo.
Para cada nodo tendremos la siguiente información:


Cota inferior (CI) y cota superior (CS) de beneficio que se
puede obtener a partir del nodo. Determinan cuando se puede
realizar una poda.
Estimación del beneficio que se puede encontrar a partir del
nodo. Ayuda a decidir el orden de evaluación de los nodos.
Estrategia de poda

Suponemos un problema de maximización. Se han recorrido
varios nodos y ha estimado la cota inferior y superior de cada
uno de ellos.
1
3
9
2
3
2
15
4
5
12
25
Estrategia de poda

El nodo 2 puede podarse, ya que el nodo 5 tiene una cota
inferior mayor que la cota superior del nodo 2.
1
3
9
x
2
2
3
15
4
5
12
25
Estrategia de ramificación



Se pueden utilizar distintas estrategias para recorrer el árbol
de soluciones. Puede recorrerse en profundidad, en anchura,
según el beneficio estimado,…
Se utiliza una lista de nodos vivos (contiene nodos generados
y aún no explorados).
Algoritmo:



Sacar un nodo de la lista de nodos vivos
Generar sus descendientes
Si no se podan, se introducen en la lista de nodos vivos.
Estrategia de ramificación

¿Qué criterio se utiliza para seleccionar el nodo que se saca
de la lista de nodos vivos?



Estrategia FIFO
Estrategia LIFO
Estrategia del menor costo
Complejidad

El tiempo de ejecución depende:





Número de nodos recorridos.
Tiempo gastado en cada nodo.
En el caso promedio se suelen obtener mejoras respecto al
algoritmo de backtracking.
Pero en el pero caso, el tiempo puede ser peor.
Se debe buscar un compromiso entre la exactitud de las cotas
y el tiempo utilizado en calcularlas.
Conclusiones


En general, el esquema de branch and bound suele obtener
mejores resultados que el de backtracking.
Sigue siendo muy ineficiente.
Índice





Introducción
Backtracking
Backtracking paralelo
Branch and Bound
Branch and Bound parelelo
Branch and Bound paralelo




Al igual que sucedía con backtracking, no es un esquema
puramente paralelo.
En el proceso secuencial, se necesita información global
para poder hacer la poda de nodos.
Se puede paralelizar distintos tipos de niveles.
Tipos de niveles:

Búsqueda paralela ejecutando el algoritmo con distintos
parámetros sobre el espacio global de búsqueda en varios
procesadores. Cálculo de cotas, de estimaciones, y criterio selec.
Branch and Bound paralelo

Tipos de nivel.


Se paralelizan partes del algoritmo.
La estructura del algoritmo no cambia.
Por ejemplo, se expanden en paralelo los nodos.
Se divide el espacio de búsqueda entre los procesadores.
De la lista de nodos vivos se asignan nodos distintos a cada
procesador.
La distribución del trabajo puede ser estática o dinámica, del
mismo modo que sucedía con backtracking.
Asignación estática


A cada procesador se le asigna un número fijo de nodos de la
lista de nodos vivos.
Los procesos pueden comunicarse la cotas o no.

Si no se comunican las cotas:



Si se comunican las cotas:



Se necesitan pocas comunicaciones entre procesos.
Puede que se estudien nodos que se podían haber podado.
Se evita que los procesadores estudien nodos innecesarios.
Se necesitan bastantes comunicaciones entre los procesos.
Además, al asignar los nodos estáticamente puede darse un
desbalanceo de carga de trabajo entre los procesadores.
Asignación dinámica




Puede utilizarse una bolsa de tareas para asignar los nodos
a los procesos de forma dinámica, como se hacía con
backtracking.
Pero ahora tenemos la opción de comunicar las cotas.
Los procesadores toman los nodos y los exploran y
depositan los descendientes de los nodos explorados en la
bolsa de trabajo.
Existen dos estrategias para depositar los nodos: inmediata
o pospuesta.
Asignación dinámica

Actualización inmediata



Cuando se generan los descendientes de un nodo se introducen
de inmediato en la bolsa.
Muchas comunicaciones.
Actualización pospuesta


Cuando se generan los descendientes de un nodo no se
introducen de inmediato en la bolsa, se sigue generado
descendientes a partir de estos. Cada cierto tiempo se
introducen en la bolsa.
Ventajas: Pueden podarse algunos nodos y no se accede tanto a
la bolsa de tareas.
Asignación dinámica

Sistema de memoria compartida


Se tiene una estructura centralizada de donde los
procesadores toman e introducen tareas.
Sistema de memoria distribuida




Se tienen bolsas de trabajo en uno o en varios procesadores.
Las peticiones y el depósito de los trabajos conllevan
comunicaciones.
Se descentraliza la bolsa de tareas.
Actualización inmediata o pospuesta.
Asignación dinámica

Comunicación de cotas:
 Si se comunican las cotas con mucha frecuencia, se podrán
podar más nodos pero puede pederse eficiencia al realizar
tantas comunicaciones.
 Si no se comunican con mucha frecuencia, no se podarán
tantos nodos pero no habrá tantas comunicaciones.
Asignación dinámica

Una única bolsa de trabajos



Varias bolsas de trabajos


Mayor contención.
La bolsa puede convertirse en un cuello de botella.
Aumenta el desbalanceo de las tareas
Se trata de buscar un compromiso entre el desbalanceo y la
contención.