Ramificació i poda

Archiu:Branch&bound.jpg

El método de disseny d'algoritmes ramificació i poda (també cridat ramificació i acotación) és una variant del backtracking millorat substancialment. El terme (de l'anglés, Branch and Bound) s'aplica majoritàriament per a resoldre qüestions o problemes d'optimisació.

La tècnica de ramificació i poda se sol interpretar com un arbre de solucions, a on cada branca conduïx a una possible solució posterior a l'actual. La característica d'esta tècnica sobre atres anteriors (i a la que deu el seu nom) és que l'algoritme s'encarrega de detectar en quina ramificació les solucions donades ya no estan sent òptimes, per a «podar» eixa branca de l'arbre i no continuar malgastant recursos i processos en casos que s'allunten de la solució òptima.

Descripció General

La nostra meta serà trobar el valor mínim d'una funció f(x) (un eixemple pot ser el cost de manufacturación d'un determinat producte) a on fixem x rancs sobre un determinat conjunt S de possibles solucions. Un procediment de ramificació i poda requerix dos ferramentes.

La primera és la d'un procediment d'expansió, que donat un conjunt fix S de candidats, torna dos o més conjunts més menuts $S_1$ , $S_2$ , … , $S_n$ l'unió dels quals cobrix S. Note's que el mínim de f(x) sobre S és min{ $v_1$, $v_2$, … } a on cada $v_i$ és el mínim de f(x) en $S_i$. Este pas és anomenat ramificació; com la seua aplicació és recursiva, esta definirà una estructura d'arbre els nodos del qual seran subconjunts de S.

L'idea clau de l'algoritme de ramificació i poda és: si la menor branca per a algun arbre nodo(conjunt de candidats) A és major que la branca pare per a un atre nodo B, llavors A deu ser descartada en seguritat de la busca. Este pas és cridat poda, i usualment és implementat mantenint una variable global m que grava el mínim nodo pare vist entre totes les subregiones examinades fins a llavors. Qualsevol nodo el nodo del qual fill és major que m pot ser descartat. La recursión per a quan el conjunt candidat S és reduït a un sol element, o també quan el nodo pare per al conjunt S coincidix en el nodo fill. De qualsevol forma, qualsevol element de S va a ser el mínim d'una funció dins de S.

Pseudocódigo

El pseudocódigo de l'algoritme de Ramificació i poda és el següent:

Funció RyP {
 P = Fills(x,k)
 while ( no vacio(P) )
    x(k) = extraure(P)
    if esFactible(x,k) i G(x,k) < optimo
        si esSolucion(x)
             Almagasenar(x)
        else
             RyP(x,k+1)

A on:

• G(x) és la funció d'estimació de l'algoritme.
• P és la pila de possibles solucions.
• esFactible és la funció que considera si la proposta és vàlida.
• esSolución és la funció que comprova si se satisfà l'objectiu.
• òptim és el valor de la funció a optimisar evaluat sobre la millor solució trobada fins al moment.
• NOTA: Usem un menor que (<) per als problemes de minimisació i un major que (>) per a problemes de maximización.

Subdivisió Efectiva

L'eficiència d'este método depén fonamentalment del procediment d'expansió de nodos, o de l'estimació dels nodos pares i fills. És millor elegir un método d'expansió que proveïxca que no es solapen els subconjunts per a aforrar-nos problemes de duplicació de branques.

Idealment, el procediment es deté quan tots els nodos de l'arbre de busca estan podats o resolts. En eixe punt, totes les subregiones no podades, tindran un nodo pare i fill iguals a una funció global mínima. En la pràctica el procediment a sovint termina quan finalisa un temps donat, fins al punt en que el mínim de nodos fills i el màxim de nodos pares sobre totes les seccions no podades definixen un ranc de valors que contenen el mínim global. Alternativament, sense superar un temps restringit, l'algoritme deu terminar quan un criteri d'error, tal que (max-min)/(max+min), cau baix un valor específic.

L'eficiència del método depén especialment de l'efectivitat dels algoritmes de ramificació i poda usats. Una mala elecció pot dur-nos a una repetida ramificació, sense poda, fins que les subregiones es convertixquen en molt menudes. En eixe cas el método seria reduït a una exhaustiva enumeració del domini, que és a sovint impracticablemente llarga. No hi ha un algoritme de poda universal que treballe per a tots els problemes, pero existix una chicoteta esperança de que alguna volta es trobe algun. Fins a llavors necessitarem implementar cada u per separat per a cada aplicació informàtica, en l'algoritme de ramificació i poda especialment dissenyats per a ell.

Els métodos de ramificació i poda deuen ser classificats de manera concorde als métodos de poda, i a les maneres de creació/classificació dels arbres de busca.

L'estratègia de disseny de ramificació i poda és molt similar al de regrés arrere (backtracking), a on l'estat de l'arbre és usat per a resoldre un problema. Les diferències són que el método de ramificació i poda no nos llimiten a cap forma particular d'obtindre un arbre transverso, i és usat solament per a problemes d'optimisació. Este método naturalment du a una forma d'implementació paralela i distribuïda, com podem vore per eixemple en el Problema del Viajante de Comerç.

Estratègies de Poda

El nostre objectiu principal serà eliminar aquells nodos que no duguen a solucions bones. Podem utilisar dos estratègies bàsiques. Supongam un problema d'maximización a on s'han recorregut varis nodos i=1,…,n. estimant per a cada u la cota superior CS(xi) i inferior CI($x_i$).

Estratègia 1

Si a partir d'un nodo $x_i$ es pot obtindre una solució vàlida, llavors es podrà podar dit nodo si la cota superior CS($x_i$) és menor o igual que la cota inferior CI($x_j$) per a algun nodo j generat en l'arbre.

Per eixemple: Supongam el problema de la mochila, el qual es va a desenrollar en la secció d'eixemples, a on utilisem un arbre binario. Llavors:

Si a partir de $x_i$ es pot trobar un benefici màxim de CS($x_i$) = 4 i a partir de $x_j$, es té assegurat un benefici mínim de CI($x_j$) = 5, açò nos durà a la conclusió de que es pot podar el nodo $x_i$ sense que pergam cap possible solució òptima.

Estratègia 2

Si s'obté una possible solució vàlida per al problema en un benefici $B_j$, llavors es podran podar aquells nodos $x_i$ la cota superior dels quals CS($x_i$) siga menor o igual que el benefici que es pot obtindre $B_j$ (este procés seria similar per a la cota inferior).

Estratègies de Ramificació

Com es comenta en l'introducció d'este apartat, l'expansió de l'arbre en les distintes estratègies està condicionada per la busca de la solució òptima. Per açò tots els nodos d'un nivell deuen ser expandits abans d'alcançar un nou nivell, cosa que és llògica ya que per a poder elegir la branca de l'arbre que va a ser explorada, es deuen conéixer totes les branques possibles.

Tots estos nodos que es van generant i que no han segut explorats s'almagasenen en lo que es denomina Llista de Nodos Vius (a partir d'ara LNV), nodos pendents d'expandir per l'algoritme.

La LNV conté tots els nodos que han segut generats pero que no han segut explorats encara. Segons com estiguen almagasenats els nodos en la llista, el recorregut de l'arbre serà d'un o un atre tipo, donant lloc a les tres estratègies que es detallen a continuació.

Estratègia FIFO

En l'estratègia FIFO (First In First Out), la LNV serà una coa, donant lloc a un recorregut en esgambi de l'arbre.

Archiu:ArbolF caps block 16

En la figura 1 es pot observar que es comença introduint en la LNV el nodo A. Traem el nodo de la coa i s'expandix generant els nodos B i C que són introduïts en la LNV. Seguidament es trau el primer nodo que és el B i es torna a expandir generant els nodos D i I que s'introduïxen en la LNV. Este procés es repetix mentres que quede algun element en la coa.

Estratègia LIFO

En l'estratègia LIFO (Last In First Out), la LNV serà una pila, produint un recorregut en profunditat de l'arbre.

Archiu:EstratL caps block 24

En la figura 2 es mostra l'orde de generació dels nodos en una estratègia LIFO. El procés que se seguix en la LNV és similar al de l'estratègia FIFO, pero en lloc d'utilisar una coa, s'utilisa una pila.

Estratègia de Menor Cost o LC

En utilisar les estratègies FIFO i LIFO es realisa lo que es denomina una busca “a cegues”, ya que expandixen sense tindre en conte els beneficis que es poden alcançar des de cada nodo. Si l'expansió es realisara en funció dels beneficis que cada nodo reporta (en una “visió de futur”), es podria conseguir en la majoria dels casos una millora substancial.

És aixina com naix l'estratègia de Menor Cost o LC (Least cost), selecciona per a expandir entre tots els nodos de la LNV aquell que tinga major benefici (o menor cost). Per lo tant ya no estem parlant d'un alvanç “a cegues”.

Açò nos pot dur a la situació de que varis nodos puguen ser expandits al mateix temps. De donar-se el cas, és necessari dispondre d'un mecanisme que solucione este conflicte:

-Estratègia LC-FIFO: Elegix de la LNV el nodo que tinga major benefici i en cas d'empat es tria el primer que es va introduir.

-Estratègia LC-LIFO: Elegix de la LNV el nodo que tinga major benefici i en cas d'empat es tria l'últim que es va introduir.