Sesión 06 - Algoritmos de Retroceso

7/23/2019 Sesin 06 - Algoritmos de Retroceso

1/50

Algoritmos de retroceso

Robert Espinoza Domnguez


2/50

Retroceso o Backtracking

El backtracking(o mtodo de retrocesoo vueltaatrs) es una tcnica general de resolucin deproblemas, aplicable en problemas de

optimizacin,juegosy otros tipos.

El backtrackingrealiza una bsqueda exhaustivay sistemtica en el espacio de soluciones. Por ello,

suele resultar muy ineficiente.


3/50

Retroceso o Backtracking

Se puede entender como opuesto a losalgoritmos voraces o de avance rpido.

Voraz:aadir elementos a la solucin y no

deshacer ninguna decisin tomada.

Backtracking:aadir y quitar todos loselementos. Probar todas las combinaciones.


4/50

Caractersticas

Una solucinse puede expresar como una tupla:(x1, x2, ..., xn), satisfaciendo unas restriccionesP(x1, x2, ..., xn) y tal vez optimizando cierta funcinobjetivo.

En cada momento, el algoritmo se encontrar encierto nivel k, con una solucin parcial (x1, ..., xk). Si se puede aadir un nuevo elemento a la solucin

xk+1, se genera y se avanza al nivel k+1.

Si no, se prueban otros valores de xk. Si no existe ningn valor posible por probar,

entonces se retrocede al nivel anterior k-1.


5/50

Caractersticas

Se sigue hasta que la solucin parcial sea unasolucin completa del problema, o hasta que noqueden ms posibilidades por probar.

El resultado es equivalente a hacer un recorrido

en profundidaden el rbol de soluciones. Sinembargo este rbol es implcito, no se almacenaen ningn lugar.


6/50

Mtodo general.

Inicio

x1=0

x1=0x2=0

x1=0x2=0x3=0

x1=0x2=1

x1=0x2=0x3=1

x1=0x2=1x3=0

x1=0x2=1x3=1

x1=1x2=0

x1=1x2=0x3=0

x1=1x2=1

x1=1x2=0x3=1

x1=1x2=1x3=0

x1=1x2=1x3=1

x1=1


7/50

Caractersticas

Inicio

x1=0

x1=0x2=0

x1=0x2=0x3=0

x1=0x2=1

x1=0x2=0x3=1

x1=0x2=1x3=0

x1=0x2=1x3=1

x1=1x2=0

x1=1x2=0x3=0

x1=1x2=1

x1=1x2=0x3=1

x1=1x2=1x3=0

x1=1x2=1x3=1

x1=1


8/50

Caractersticas

Representacin simplificada del rbol.

1

2

3

4

6

5 7 8

10

11

13

12 14 15

9

0

0

0 1

01

1

0 10 10 1

1

x1

x2

x3


9/50

Ejemplo

Dado un conjunto de nmeros enteros{13, 11, 7}, encontrar si existe algn

subconjunto cuya suma seaexactamente 20.


10/50

EjemploPosibilidad 1

En cada nivel i decidir si el elemento i est o no en lasolucin. Representacin de la solucin: (x1, x2, x3),donde xi= (0, 1).

1

2

3

4

6

5 7 8

10

11

13

12 14 15

9

0

0

0

1

1

0 1

1

k = 1 (13)

0 1 0 1 0 1

0 7 11 18 13 20 24 31

k = 2 (11)

k = 3 (7)

Sumas

totales

rbol desoluciones 1


11/50

Cada nodo representa un paso del algoritmo, unasolucin parcial en cada momento dado.

El rbol indica un orden de ejecucin (recorrido enprofundidad) pero no se almacena en ningn lugar.

Una solucin es un nodo hoja con valor de suma 20. Posible mejora: En cada nodo llevamos el valor de la

suma hasta ese punto. Si el valor es mayor que 20,retroceder al nivel anterior



12/50


En cada nivel i decidir qu elemento se aade (1, 2 3) enla solucin. Representacin de la solucin: (s1, , s3),donde m n y si {1, 2, 3}.

1

2

3

4

5 7

6 8

21

3

3

2

k = 1

0

711

18

13

24

31

k = 2

k = 3

rbol de

soluciones 2

3

320


13/50

Cada nodo es una posible solucin. Ser vlida si lasuma es 20.

El recorrido es tambin en profundidad.

Necesitamos funciones para generar los nodos, para

descartar nodos y para saber si un nodo es solucin Cmo ser la eficiencia del algoritmo? Depende del

nmero de nodos.



14/50

rboles de retroceso (backtracking)

El rbol es simplemente una forma derepresentar la ejecucin del algoritmo.

Es implcito, no almacenado (nonecesariamente).

El recorrido es en profundidad, normalmente deizquierda a derecha.

La primera decisin para aplicar backtracking:

cmo es la forma del rbol? Preguntas relacionadas:Qu significa cada

valor de la tupla solucin (x1, ..., xn)? Cmo esla representacin de la solucin al problema?


15/50

5.1. rboles de retroceso (backtracking)

Tipos comunes de rboles de backtracking:

rboles binarios.

rboles n-arios.

rboles permutacionales.

rboles combinatorios.


16/50

rboles binarios

s= (x1, x

2, ..., x

n), con x

i{0, 1}

Tipo de problemas:elegir ciertos elementos de entre unconjunto, sin importar el orden de los elementos. Problema de la mochila 0/1. Encontrar un subconjunto de {12, 23, 1, 8, 33, 7, 22} que

sume exactamente 50.

1

2

3 4 6 7

5

0

0 01

1

1

x1

x2


17/50

rboles k-arios

s= (x1, x2, ..., xn), con xi{1,..,k}

Tipo de problemas:varias opciones para cada xi. Problema del cambio de monedas.

Problema de las nreinas.

1

2

3 5 11 13

10

1

1 13

3

3

x1

x2

4 127 9

6

1 3

8

2

2 2 2


18/50

rboles permutacionales

s = (x1, x

2, ..., x

n), con x

i{1,..,n} y x

i x

j

Tipo de problemas:los xino se pueden repetir. Generar todas las permutaciones de (1, ..., n). Asignar ntrabajos a npersonas, asignacin uno-a-uno.

1

2

3 5 12 14

11

1

3

13

3

2

x1

x2

4 13

7 9

6

1 3

8

2

2

23

6 10 15

1 2 1 x3


19/50

rboles combinatorios

s= (x1, x2, ..., xm), con mn, xi

{1,..,n} y xi< xi+1

Tipo de problemas:los mismos que con rboles binarios

Binario: (0, 1, 0, 1, 0, 0, 1)Combinatorio: (2, 4, 7)

1

2

3 5

8

1

3

3 x1

x2

4

7

6

3

2

2

3x3


20/50

Mtodo general.

Cuestiones a resolver antes de programar: Qu tipo de rbol es adecuado para el problema?

Cmo es la representacin de la solucin? Cmo es la tupla solucin? Qu indica cada xiy qu valores

puede tomar?

Cmo generar un recorrido segn ese rbol? Generar un nuevo nivel. Generar los hermanos de un nivel. Retroceder en el rbol.

Qu ramas se pueden descartar por no conducir asoluciones del problema? Poda por restricciones del problema. Poda segn el criterio de la funcin objetivo.


21/50

Mtodo general

Mtodo Clase.Backtracking (var s: TuplaSolucin)nivel1ssINICIALfinfalsoHacer

Generar (nivel, s)

Si Solucin (nivel, s)entoncesfinverdaderoSino Si Criterio (nivel, s)entonces

nivelnivel + 1Sino Mientras NO MasHermanos (nivel, s)hacer

Retroceder (nivel, s)fMientrasfSi

fSiMientras fin = falso

fMetodo


22/50

Mtodogeneral

Variables: s: Almacena la solucin parcial hasta cierto punto. sINICIAL: Valor de inicializacin. nivel: Indica el nivel actual en el que se encuentra el algoritmo. fin: Valdr verdaderocuando hayamos encontrado alguna

solucin.

Funciones: Generar (nivel, s): Genera el siguiente hermano (o el primero)

para el nivelactual.

Solucin (nivel, s): Comprueba si la tupla (s[1], ..., s[nivel]) esuna solucin vlida para el problema.


23/50

Mtodo general

Criterio (nivel, s): Comprueba si a partir de (s[1], ..., s[nivel])se puede alcanzar una solucin vlida. En otro caso serechazarn todos los descendientes (poda).

MasHermanos (nivel, s): Devuelve verdaderosi hay mshermanos del nodo actual que todava no han sido

generados. Retroceder (nivel, s): Retrocede un nivel en el rbol de

soluciones. Disminuye en 1 el valor de nivel, y posiblementetendr que actualizar la solucin actual, quitando loselementos retrocedidos.

Adems, suele ser comn utilizar variables temporales conel valor actual (beneficio, peso, etc.) de la tupla solucin.


24/50

Mtodo general

Cmo seran estas funciones en los ejemplos anteriores? Otros posibles casosde problemas:

1. No est garantizado que exista una solucin, puede existiralguna o no.

2. Queremos obtener todas las soluciones, no slo una.3. El problema es de optimizacin. De todas las solucionesposibles queremos aquella que maximice (o minimice) unafuncin objetivo.


25/50

Depende del nmero de nodos generados y del tiemporequerido para cada nodo.

Por lo general el tiempo de cada nodo es constante.

Suponiendo que una solucin sea de la forma:

(x1, x2, , xn), en el peor caso se generarn todas lasposibles combinaciones para cada x1.

Si el nmero de posible de valores para cada xies mi,entonces se generan:

m1 nodos en el nivel 1m1 m2 nodos en el nivel 2

m1 m2 mn nodos en el nivel 3

Anlisis de tiempos de ejecucin


26/50

Ejemplo. Para el problema de la suma desubconjuntos mi = 2. El nmero de nodos generadoses:

t(n) = 2 + 22+ 23+ + 2n= 2n-1- 2

Ejemplo. Calcular todas las permutaciones de (1, 2,, n). En el primer nivel tenemos n posibilidades, en elsegundo nivel (n-1), , en el nivel n una posibilidad.

t(n) = n + n(n-1) + n(n-1)(n-2) + + n! O(n!)

En general tendremos tiempos con rdenes decomplejidad factoriales o exponenciales.

Anlisis de tiempos de ejecucin


27/50

Conclusiones

Backtracking:Recorrido exhaustivo y sistemtico en unrbol de soluciones.

Pasos para aplicarlo: Decidir la forma del rbol.

Establecer el esquema del algoritmo. Disear las funciones genricas del esquema.

Relativamente fcil disear algoritmos que encuentrensoluciones ptimas pero...

Los algoritmos de backtracking son muy ineficientes. Mejoras:mejorar los mecanismos de poda, incluir otros

tipos de recorridos (no solo en profundidad)Tcnica de Ramificacin y Poda.


28/50

Ejemplo. Subconjuntos de suma dada


29/50

Encontrar un subconjunto del

Conjunto T= {t1, t2, ..., tn} que

sume exactamente P.

Subconjuntos de suma dada


30/50

Variables:Representacin de la solucin con un rbol binario. s: array [1..n] de {-1, 0, 1}s[i] = 0el nmero i-simo no se utilizas[i] = 1el nmero i-simo s se utilizas[i] = -1valor de inicializacin (nmero i-simo

no estudiado) sINICIAL: (-1, -1, ..., -1) fin: Valdr verdaderocuando se haya encontrado

solucin. tact:Suma acumulada hasta ahora (inicialmente 0).



31/50

Funciones: Generar (nivel, s)s[nivel]s[nivel] + 1sis[nivel] =1 entoncestact:= tact + tnivel

Solucin (nivel, s)devolver(nivel = n) Y (tact = P)

Criterio (nivel, s)devolver(nivel


32/50

Retroceder (nivel, s)tact:= tacttnivel*s[nivel]s[nivel]:= -1nivel:= nivel1



33/50


Generar (nivel, s)siSolucin (nivel, s) entonces

finverdaderosinosiCriterio (nivel, s) entonces

nivelnivel + 1

sinomientrasNOT MasHermanos (nivel, s) hacerRetroceder (nivel, s)

finsiMientrasfin = falso

Fin Mtodo



34/50


Variacionesdel esquema general:

1) Y si no es seguro que exista una solucin?

2) Y si queremos almacenar todas las soluciones(no slo una)?

3) Y si el problema es de optimizacin (maximizar ominimizar)?


35/50

Subconjuntos de suma dada - Caso 1

Puede que no exista ninguna solucin.


Generar (nivel, s)siSolucin (nivel, s) entonces

fintruesinosiCriterio (nivel, s) entonces

nivel

nivel + 1sinomientrasNOT MasHermanos (nivel, s)

hacerRetroceder (nivel, s)finsi

Mientras fin = falsoFin= falso Y (nivel > 0)

Y (nivel > 0)

Para poder generar todo elrbol de backtracking


36/50


Queremos almacenar todas las soluciones.

Mtodo Clase.Backtracking (var s: TuplaSolucin)nivel1ssINICIALfinfalso

HacerGenerar (nivel, s)siSolucin (nivel, s) entonces


nivelnivel + 1sino

mientrasNOT MasHermanos (nivel, s)hacerRetroceder (nivel, s)

finsiMientrasfin = falsonivel >0

Y (nivel > 0)

Almacenar (nivel, s)siCriterio (nivel, s) entonces

En algunos problemas los nodosintermedios pueden ser soluciones O bien, retroceder despus de encontraruna solucin


37/50


Problema de optimizacin (maximizacin).

Mtodo Clase.Backtracking (var s: TuplaSolucin)nivel1ssINICIALfinfalso

HacerGenerar (nivel, s)siSolucin (nivel, s) entonces


nivelnivel + 1sino

mientrasNOT MasHermanos (nivel, s)hacerRetroceder (nivel, s)

finsiMientrasfin = falsoNivel > 0

Y (nivel>0)

voa Valor(s); soa ssiCriterio (nivel, s) entonces

voa -; soa

voa: valor ptimo actual

soa:solucin ptima actual

y Valor(s) > voaentonces


38/50

Problema de la mochila 0/1


39/50


Los objetos no se pueden partir (se cogen enteros onada).

Datos del problema: n: nmero de objetos disponibles.

M: capacidad de la mochila. p = (p1,p2, ..., pn) pesos de los objetos.

b = (b1,b2, ..., bn) beneficios de los objetos.

Formulacin matemtica:Maximizar xi bisujeto a la restriccin xi pi M, y xi{0,1}

i=1..n i=1..n


40/50


Caractersticas del problema Es un problema de optimizacin (maximizacin)

Slo nos interesa una solucin, la ptima

Existir al menos una solucin (no incluir ningn objeto)


41/50


Ejemplo:n = 4; M = 7

b = (2, 3, 4, 5)p = (1, 2, 3, 4)

Qu solucin devuelve el algoritmo voraz para el problema

de la mochila? Qu solucin devuelve el algoritmo voraz adaptado al caso

0/1 (o se coge un objeto entero o no)? Cul es la solucin ptima?

4 kg

3 kg

2 kg

1 kg7 Kg.

PVP 5 PVP 4 PVP 2PVP 3


42/50


Ejemplo:n = 2; M = 100

b = (2, 190)p = (1, 100)

Qu solucin devuelve el algoritmo voraz para elproblema de la mochila? Qu solucin devuelve el algoritmo voraz adaptado al

caso 0/1 (o se coge un objeto entero o no)?

Cul es la solucin ptima?

100 Kg.

100 kg

1 kgPVP 190PVP 2


43/50

Problema de la mochila 0/1.

Aplicacin de backtracking (proceso metdico):1) Determinar cmo es la forma del rbol de

backtracking cmo es la representacin de lasolucin.

2) Elegir el esquema de algoritmo adecuado,adaptndolo en caso necesario.

3) Disear las funciones genricas para la aplicacinconcreta: segn la forma del rbol y las

caractersticas del problema.4) Posibles mejoras: usar variables locales con valores

acumulados, hacer ms podas del rbol, etc.


44/50


1. Representacin de la solucin.

Con un rbol binario: s= (x1, x2, ..., xn), con xi{0,1} xi= 0No se coge el objeto i xi= 1S se coge el objeto i x

i= -1Objeto ino estudiado

En cada nivel ise pruebala posibilidad de incluiro no el objeto i

Las solucionesestn en nivel n

1

2

3 6 10 13

9

0

0 01

1

1

x1

x2

4 5

0 1

7 8 11 12 14 15

1 11

000x3


45/50


1. Representacin de la solucin. Tambin es posible usar un rbol combinatorio:

s= (x1, x2, ..., xm), con m n, xi{1,..,n} y xi< xi+1 xiNmero de objeto escogido mNmero total de objetos escogidos

Las soluciones estn en cualquier nivel

1

2

3 5

8

1

3

3 x1

x2

4

7

6

3

2

2

3x3


46/50


2. Elegir el esquema de algoritmo: caso optimizacin.

Mtodo Clase.Backtracking (var s: array [1..n] de entero)nivel1; ssINICIALvoa-; soapact0; bact0

HacerGenerar (nivel, s)siSolucin (nivel, s) AND (bact > voa) entonces

voabact; soassiCriterio (nivel, s) entonces

nivelnivel + 1

sinomientrasNOT MasHermanos (nivel, s) AND (nivel>0)

hacerRetroceder (nivel, s)finsi

Mientrasnivel > 0

Fin Mtodo

pact: Peso actual

bact:Beneficio actual


47/50


sis[nivel] = 1 entoncespactpact + p[nivel]bactbact + b[nivel]

finsi

3) Funciones genricas del esquema. Generar (nivel, s)Probar primero 0 y luego 1

s[nivel]s[nivel] + 1pactpact + p[nivel]*s[nivel]bactbact + b[nivel]*s[nivel]

Solucin (nivel, s)devolver(nivel =n) Y (pact M)

Criterio (nivel, s)devolver(nivel < n) Y (pact M)

MasHermanos (nivel, s)

devolvers[nivel] < 1 Retroceder (nivel, s)

pactpactp[nivel]*s[nivel]bactbactb[nivel]*s[nivel]s[nivel]-1nivelnivel1


48/50


Ejemplo:n = 4; M = 7;b = (2, 3, 4, 5)p = (1, 2, 3, 4)

1

2

3 10 18 25

17

0

0 01

1

1

x1

x2

4 7

0 1

11 14 19 22 26 29

1 11

000x3

5 6 9 13 21 24 288 12 15 20 23 27 30 31

x40 0000 0001 1 1 11 1 1 1

pact: 0

bact: 0

4

5

7

9

9

12

8

11

7

10

10

14

16


49/50


El algoritmo resuelve el problema, encontrandola solucin ptima pero es muy ineficiente.

Cunto es el orden de complejidad? Nmero de nodos generados = 2n+11

El algoritmo es del orden O(2n)

Problema adicional:en el ejemplo, segeneran todos los nodos posibles, no hay

ninguna poda. La funcin Criterioes siemprecierta (excepto para algunos nodos hoja).


50/50


Solucin:Intentar eliminar algunos nodos delrbol de soluciones con una funcin Criterioms restrictiva.

Incluir una poda segn el criterio de optimizacin. Poda segn el criterio de peso:si el peso actual

es mayor que M podar el nodo.

Poda segn el criterio de optimizacin:si elbeneficio actual no puede mejorar el voapodar elnodo.

Sesión 06 - Algoritmos de Retroceso

Documents

Transcript of Sesión 06 - Algoritmos de Retroceso