Ramificacion y poda
3
Algoritmo De Branch and Bound (Ramificaci´on y Poda). Jes´ us Enrique Bahena Ortiz 1. Resumen El presente art´ ıculo se ha desarrollado con la finalidad de mostrar la resoluci´ on de un problema pr´ actico de optimizaci´ on, a trav´ es del Algoritmo de Ramificaci´ on y Poda (Branch and Bound). Se plantea como tarea a resolver un caso de optimzacion de 4 individuos y 4 tareas a trav´ es del algoritmo de Ramificaci´ on y Poda utilizando las unidades de tiempo en que son ejecuta- das las tareas mencionadas por cada individuo. Palabras clave:Algoritmo, ramificaci´ on, poda, op- timizaci´ on. 2. Introducci´ on El algoritmo de Ramificaci´ on y poda (conocido tambi´ en como Ramificaci´ on y cota o ”Branch and Bound”por su significado en ingles) es una manera de combinar el ahorro de espacio de b´ usqueda en profun- didad con informaci´ on heur´ ıstica. Es particularmente aplicable cuando existen muchos caminos hacia un ob- jetivo y se desea una trayectoria ´ optima. La idea princi- pal del algoritmo de b´ usqueda de Ramificaci´ on y poda es mantener el camino de costo m´ as bajo hacia una meta encontrada demasiado lejos. Supongamos que el costo es obligado. Si la b´ usqueda encuentra o arroja un camino tal que costo (p)+ h(p) ≥ que se estable- ci´ o, el camino o puede ser podado. Si un camino no podado hacia la meta es encontrado, debe ser mejor que el camino m´ as optimo. Esta nueva soluci´ on es al- macenada y el costo establecido se coloca a esta nueva soluci´ on, as´ ı sucesivamente se continua con la b´ usqueda hasta encontrar una nueva soluci´ on. La b´ usqueda del Algoritmo de Branch and Bound genera una secuencia de mejores soluciones. Una vez que se ha encontrado una soluci´ on, continua buscando una mejor. El algo- ritmo de Branch and Bound es t´ ıpicamente utilizado en b´ usquedas de profundidad. El algoritmo recuerda el camino de menor costo encontrado y devuelve este camino cuando finalice la b´ usqueda. Terminolog´ ıa Nodo vivo: Aquel que no ha sido podado y que puede ser ramificado. Nodo muerto: Nodo del que no se van a generar m´ as hijos, porque: • Se llega a una soluci´ on. • No genera nuevas soluciones factibles. • No genera mejores soluciones que la mejor conocida hasta el momento. Nodo en curso (o en expansi´ on: Aquel que se se- lecciona para ramificarlo. Algoritmo (Generalidades) Cada arista de grafo (´ arbol) tendr´ a asociado un coste. RP utiliza cotas para podar aquellas ramas del ´ arbol que no conducen a la soluci´ on ´ optima. En cada nodo se calcula una cota del valor de las soluciones que se encontraran generando. suceso- res. Si la cota indica que las soluciones a encontrar son peores que la mejor que tenemos no se sigue explorando esa rama (proceso de poda La cota se utiliza para seleccionar el camino m´ as prometedor. Etapas de Algoritmo de Ramificaci´ on y Poda Selecci´ on: extrae un nodo del conjunto de nodos vivos - depende de la estrategia de b´ usqueda em- pleada. Ramificaci´ on: se construyen los posibles nodos hi- jos del nodo seleccionado en el paso anterior. Poda: se eliminan algunos de los nodos creados en la etapa anterior. La poda contribuye a reducir en lo posible el es- pacio de b´ usqueda, atenuando la complejidad. Los nodos no podados pasan a formar parte del conjunto de nodos vivos. Se repiten las 3 etapas hasta que finaliza el algo- ritmo. El algoritmo se detiene cuando: encuentra la so- luci´ on, se agota el conjunto de nodos vivos. 3. Planteamiento del Problema Dadas n tareas y n personas, asignar a cada per- sona una tarea; minimizando el coste de la asignaci´ on total. Para resolver el problema, se tiene una matriz de tarifas que determina el coste de asignar a cada perso- na una tarea. 1
-
Upload
whaleejaa-wha -
Category
Technology
-
view
208 -
download
0
Transcript of Ramificacion y poda
Algoritmo De Branch and Bound (Ramificacion y Poda).
Jesus Enrique Bahena Ortiz
1. Resumen
El presente artıculo se ha desarrollado con la finalidadde mostrar la resolucion de un problema practico deoptimizacion, a traves del Algoritmo de Ramificaciony Poda (Branch and Bound). Se plantea como tareaa resolver un caso de optimzacion de 4 individuos y 4tareas a traves del algoritmo de Ramificacion y Podautilizando las unidades de tiempo en que son ejecuta-das las tareas mencionadas por cada individuo.
Palabras clave:Algoritmo, ramificacion, poda, op-timizacion.
2. Introduccion
El algoritmo de Ramificacion y poda (conocidotambien como Ramificacion y cota o ”Branch andBound”por su significado en ingles) es una manera decombinar el ahorro de espacio de busqueda en profun-didad con informacion heurıstica. Es particularmenteaplicable cuando existen muchos caminos hacia un ob-jetivo y se desea una trayectoria optima. La idea princi-pal del algoritmo de busqueda de Ramificacion y podaes mantener el camino de costo mas bajo hacia unameta encontrada demasiado lejos. Supongamos que elcosto es obligado. Si la busqueda encuentra o arrojaun camino tal que costo (p) + h(p) ≥ que se estable-cio, el camino o puede ser podado. Si un camino nopodado hacia la meta es encontrado, debe ser mejorque el camino mas optimo. Esta nueva solucion es al-macenada y el costo establecido se coloca a esta nuevasolucion, ası sucesivamente se continua con la busquedahasta encontrar una nueva solucion. La busqueda delAlgoritmo de Branch and Bound genera una secuenciade mejores soluciones. Una vez que se ha encontradouna solucion, continua buscando una mejor. El algo-ritmo de Branch and Bound es tıpicamente utilizadoen busquedas de profundidad. El algoritmo recuerdael camino de menor costo encontrado y devuelve estecamino cuando finalice la busqueda.
Terminologıa
Nodo vivo: Aquel que no ha sido podado y quepuede ser ramificado.
Nodo muerto: Nodo del que no se van a generarmas hijos, porque:
• Se llega a una solucion.
• No genera nuevas soluciones factibles.
• No genera mejores soluciones que la mejorconocida hasta el momento.
Nodo en curso (o en expansion: Aquel que se se-lecciona para ramificarlo.
Algoritmo (Generalidades)
Cada arista de grafo (arbol) tendra asociado uncoste.
RP utiliza cotas para podar aquellas ramas delarbol que no conducen a la solucion optima.
En cada nodo se calcula una cota del valor de lassoluciones que se encontraran generando. suceso-res.
Si la cota indica que las soluciones a encontrarson peores que la mejor que tenemos no se sigueexplorando esa rama (proceso de poda
La cota se utiliza para seleccionar el camino masprometedor.
Etapas de Algoritmo de Ramificacion y Poda
Seleccion: extrae un nodo del conjunto de nodosvivos - depende de la estrategia de busqueda em-pleada.
Ramificacion: se construyen los posibles nodos hi-jos del nodo seleccionado en el paso anterior.
Poda: se eliminan algunos de los nodos creadosen la etapa anterior.
La poda contribuye a reducir en lo posible el es-pacio de busqueda, atenuando la complejidad.
Los nodos no podados pasan a formar parte delconjunto de nodos vivos.
Se repiten las 3 etapas hasta que finaliza el algo-ritmo.
El algoritmo se detiene cuando: encuentra la so-lucion, se agota el conjunto de nodos vivos.
3. Planteamiento del Problema
Dadas n tareas y n personas, asignar a cada per-sona una tarea; minimizando el coste de la asignaciontotal.
Para resolver el problema, se tiene una matriz detarifas que determina el coste de asignar a cada perso-na una tarea.
1
Figura 1 Matriz de tarifas
4. Desarrollo y Experimentacion
En primer lugar, se necesita obtener una cota su-perior del coste. Se obtendra a partir de una primerasolucion. Para este ejemplo, se tomaran los elementosde la diagonal principal: a1, b2, c3, d4.
11 + 15 + 19 + 28 = 73
Solucion optima ≤ Cota calculada
Se empieza asignando el agente a a las diferentestareas. Cabe recordar que la cota superior establecidaes de 73.
Se selecciona el menor valor para cada tarea peroque no se encuentre en la columna del primer elementoelegido.
a1 = 11 + 13 + 17 + 14 = 55
a2 = 12 + 13 + 11 + 17 = 53
a3 = 18 + 14 + 11 + 14 = 55
a4 = 40 + 13 + 11 + 14 = 78
Figura 1 Inicio del arbol
Se observa que 78 ≥ cota superior, por lo tanto estarama no se explorara, debido a que no se encuentra uncamino optimo en ella.
A continuacion se explorara el nodo mas promete-dor: cota 53 (a2)
Cota superior:73
b1 = 12 + 14 + 19 + 20 = 65
b3 = 12 + 13 + 11 + 17 = 53
b4 = 12 + 22 + 11 + 17 = 62
Figura 2. Primera ramificacion
Se observa que el nodo mas prometedor es de lacota de 53, por lo que sera el nodo que se explorara.
c1, d4 = 12 + 13 + 11 + 28 = 64
c4, d1 = 12 + 22 + 23 + 17 = 65
Figura 3. Primera Solucion encontrada
La solucion encontrada sera nuestra nueva cota su-perior:64
Como consecuencia, se descarta el nodo (a2,b1) queexcede la nueva cota superior.
Despues, se procede a continuar con la cota mas pro-metedora.
a1, cuenta con la cota mas prometedora despues dea2 y se continua la exploracion a partir de el. Cotasuperior: 64
Figura 3. Exploracion a partir de nodo a1
a1, b3, c2, d4 = 11 + 13 + 71 + 28 = 69
a1, b3, c4, d2 = 11 + 13 + 23 + 14 = 61
La solucion encontrada sera la nueva cota superior:61. Como consecuencia, se descarta el nodo (a2,b4)
Continuando con la exploracion, a3 cuenta con la cotamas prometedora despues de a1 y a2 por lo que seprocede a realizar la exploracion a partir de el.
2
Figura 3. Exploracion a partir de nodo a3
a3, b1 = 18 + 14 + 17 + 14 = 63a3, b2 = 18 + 15 + 11 + 17 = 61a3, b4 = 18 + 22 + 11 + 14 = 65
Ninguna solucion encontrada es menor a nuestra cotasuperior establecida de 61. Por lo que se ha encontradouna solucion optima, reduciendo el coste de una explo-racion completa.
Se partio de una solucion inicial, la exploracion del
arbol de busqueda se realiza examinando el nodo masprometedor en cada momento.
5. Conclusion
La sencillez del Algoritmo de Warshall la hace unaherramienta muy simple de utilizar y encontrar los di-ferente caminos entre un par de nodos en un grafo,siendo de gran utilidad en la teoria de grafos.
Referencias
[1] Matematicas Discretas, Schawm, Seymour lips-chutz, Marc Lipson, 3a Edicion..
[2] Algoritmo de warshall, Josue Coloma,https://www.youtube.com/watch?v=UIAX9Lj85Is
3
