PDF de programación - Tema 5. Backtracking - Parte I. Estructuras de Datos

Programa de teoría
Parte I. Estructuras de Datos.

1. Abstracciones y especificaciones.
2. Conjuntos y diccionarios.
3. Representación de conjuntos mediante árboles.
4. Grafos.

Parte II. Algorítmica.

1. Análisis de algoritmos.
2. Divide y vencerás.
3. Algoritmos voraces.
4. Programación dinámica.
5. Backtracking.
6. Ramificación y poda.

A.E.D.

Tema 5. Backtracking.

PARTE II: ALGORÍTMICA

Tema 5. Backtracking.

5.1. Método general.
5.2. Análisis de tiempos de ejecución.
5.3. Ejemplos de aplicación.

5.3.1. Problema de la mochila 0/1.
5.3.2. Problema de la asignación.
5.3.3. Resolución de juegos.

A.E.D.

Tema 5. Backtracking.

1

2

1

5.1. Método general.

• El backtracking (o método de retroceso o vuelta

atrás) es una técnica general de resolución de
problemas, aplicable en problemas de optimización,
juegos y otros tipos.

• El backtracking realiza una búsqueda exhaustiva y

sistemática en el espacio de soluciones. Por ello, suele
resultar muy ineficiente.

• Se puede entender como “opuesto” a avance rápido:

– Avance rápido: añadir elementos a la solución y no

deshacer ninguna decisión tomada.

– Backtracking: añadir y quitar todos los elementos.

Probar todas las combinaciones.

A.E.D.

Tema 5. Backtracking.

3

5.1. Método general.

• Una solución se puede expresar como una tupla:

(x1, x2, ..., xn), satisfaciendo unas restricciones y tal vez
optimizando cierta función objetivo.

• En cada momento, el algoritmo se encontrará en cierto

nivel k, con una solución parcial (x1, ..., xk).
– Si se puede añadir un nuevo elemento a la solución xk+1,

se genera y se avanza al nivel k+1.

– Si no, se prueban otros valores para xk.
– Si no existe ningún valor posible por probar, entonces se

retrocede al nivel anterior k-1.

– Se sigue hasta que la solución parcial sea una solución

completa del problema, o hasta que no queden más
posibilidades por probar.

A.E.D.

Tema 5. Backtracking.

4

2

5.1. Método general.

• El resultado es equivalente a hacer un recorrido en

profundidad en el árbol de soluciones.

Inicio

x1=0

x1=0
x2=1

x1=0
x2=0

x1=1

x1=1
x2=0

x1=1
x2=1

x1=0
x2=0
x3=0

x1=0
x2=0
x3=1

x1=0
x2=1
x3=0

x1=0
x2=1
x3=1

x1=1
x2=0
x3=0

x1=1
x2=0
x3=1

x1=1
x2=1
x3=0

x1=1
x2=1
x3=1

A.E.D.

Tema 5. Backtracking.

5

5.1. Método general.

• Representación simplificada del árbol.

x1

x2

x3

0

4

3

0

1

5

0

1

6

2

0

7

1

1

8

0

11

9

1

0

10

1

12

A.E.D.

Tema 5. Backtracking.

1

0

14

1

15

13

6

3

5.1. Método general.

• Árboles de backtracking:

– El árbol es simplemente una forma de representar la

ejecución del algoritmo.

– Es implícito, no almacenado (no necesariamente).
– El recorrido es en profundidad, normalmente de

– La primera decisión para aplicar backtracking: ¿cómo

izquierda a derecha.

es la forma del árbol?

– Preguntas relacionadas: ¿Qué significa cada valor

de la tupla solución (x1, ..., xn)? ¿Cómo es la
representación de la solución al problema?

A.E.D.

Tema 5. Backtracking.

5.1. Método general.

• Tipos comunes de árboles de backtracking:

– Árboles binarios.

– Árboles n-arios.

– Árboles permutacionales.

– Árboles combinatorios.

A.E.D.

Tema 5. Backtracking.

7

8

4

5.1. Método general.

• Árboles binarios: s= (x1, x2, ..., xn), con xi ∈ {0, 1}

x1

x2

0

3

2

0

1

4

1

1

5

0

6

1

7

• Tipo de problemas: elegir ciertos elementos de entre

un conjunto, 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.

A.E.D.

Tema 5. Backtracking.

9

5.1. Método general.

• Árboles k-arios: s= (x1, x2, ..., xn), con xi ∈ {1,..,k}

x1

1

x2

1

3

2

2

4

3

5

2

1

6

8

1

2

7

3

10

2

12

1

11

3

13

3

9

• Tipo de problemas: varias opciones para cada xi.

– Problema del cambio de monedas.
– Problema de las n reinas.
A.E.D.

Tema 5. Backtracking.

10

5

5.1. Método general.

• Árboles permutacionales: s= (x1, x2, ..., xn), con

xi ∈ {1,..,n} y xi ≠ xj
1

2

1

6

3

x1

3

9

1

12

1

2

10

13

11

2

x2

14
1

15

x3

2

2

3

5

2

6

1

3

7

8

3

3

4

• Tipo de problemas: los xi no se pueden repetir.

– Generar todas las permutaciones de (1, ..., n).
– Asignar n trabajos a n personas, asignación uno-a-uno.

A.E.D.

Tema 5. Backtracking.

11

5.1. Método general.

• Árboles combinatorios: s= (x1, x2, ..., xm), con

m≤n, xi ∈ {1,..,n} y xi < xi+1

1

2

3

5

2

3

1

6

7

2

3

3

4

3

8

x1

x2

x3

• Tipo de problemas: los mismos que con árb. binarios.

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

A.E.D.

Tema 5. Backtracking.

12

6

5.1. Método general.

Cuestiones a resolver antes de programar:

• ¿Qué tipo de árbol es adecuado para el problema?

¿Cómo es la representación de la solución?
¿Cómo es la tupla solución? ¿Qué indica cada xi y

qué valores puede tomar?

• ¿Cómo generar un recorrido según ese árbol?

Generar un nuevo nivel.
Generar los hermanos de un nivel.
Retroceder en el árbol.

• ¿Qué ramas se pueden descartar por no conducir a

soluciones del problema?
Poda por restricciones del problema.
Poda según el criterio de la función objetivo.

A.E.D.

Tema 5. Backtracking.

13

5.1. Método general.

• Esquema general (no recursivo). Problema de satisfacción

de restricciones: buscamos cualquier solución que cumpla
cierta propiedad, y se supone que existe alguna.
Backtracking (var s: TuplaSolución)

nivel:= 1
s:= sINICIAL
fin:= false
repetir

Generar (nivel, s)
si Solución (nivel, s) entonces

fin:= true

sino si Criterio (nivel, s) entonces

nivel:= nivel + 1

sino mientras NOT MasHermanos (nivel, s) hacer

Retroceder (nivel, s)

hasta fin

A.E.D.

Tema 5. Backtracking.

14

7

5.1. Método general.

• Variables:

– s: Almacena la solución parcial hasta cierto punto.
– sINICIAL: Valor de inicialización.
– nivel: Indica el nivel actual en el que se encuentra el

– fin: Valdrá true cuando hayamos encontrado alguna

algoritmo.

solución.

• Funciones:

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

primero, para el nivel actual.

– Solución (nivel, s): Comprueba si la tupla (s[1], ...,

s[nivel]) es una solución válida para el problema.

A.E.D.

Tema 5. Backtracking.

15

5.1. Método general.

• Funciones:

– Criterio (nivel, s): Comprueba si a partir de (s[1], ...,

s[nivel]) se puede alcanzar una solución válida. En otro
caso se rechazarán todos los descendientes (poda).
– MasHermanos (nivel, s): Devuelve true si hay más
hermanos del nodo actual que todavía no han sido
generados.

– Retroceder (nivel, s): Retrocede un nivel en el árbol de

soluciones. Disminuye en 1 el valor de nivel, y
posiblemente tendrá que actualizar la solución actual,
quitando los elementos retrocedidos.

• Además, suele ser común utilizar variables temporales

con el valor actual (beneficio, peso, etc.) de la tupla
solución.

A.E.D.

Tema 5. Backtracking.

16

8

5.1. Método general.

• Ejemplo de problema: Encontrar un subconjunto del

conjunto T= {t1, t2, ..., tn} que sume exactamente P.

• Variables:

– Representación de la solución con un árbol binario.
– s: array [1..n] de {-1, 0, 1}

• s[i] = 0 el número i-ésimo no se utiliza
• s[i] = 1 el número i-ésimo sí se utiliza
• s[i] = -1 valor de inicialización (número i-ésimo

no estudiado)

– sINICIAL: (-1, -1, ..., -1)
– fin: Valdrá true cuando se haya encontrado solución.
– tact: Suma acumulada hasta ahora (inicialmente 0).

A.E.D.

Tema 5. Backtracking.

17

5.1. Método general.

Funciones:
• Generar (nivel, s)

s[nivel]:= s[nivel] + 1
si s[nivel]==1 entonces tact:= tact + tnivel

• Solución (nivel, s)

devolver (nivel==n) Y (tact==P)

• Criterio (nivel, s)

devolver (nivel<n) Y (tact≤P)

• MasHermanos (nivel, s)

devolver s[nivel] < 1
• Retroceder (nivel, s)

tact:= tact – tnivel*s[nivel]
s[nivel]:= -1
nivel:= nivel – 1

A.E.D.

Tema 5. Backtracking.

18

9

5.1. Método general.

• Algoritmo: ¡el mismo que el esquema general!

Backtracking (var s: TuplaSolución)

nivel:= 1
s:= sINICIAL
fin:= false
repetir

sino

finsi
hasta fin

Generar (nivel, s)
si Solución (nivel, s) entonces

fin:= true

sino si Criterio (nivel, s) entonces

nivel:= nivel + 1

mientras NOT MasHermanos (nivel, s) hacer

Retroceder (nivel, s)

A.E.D.

Tema 5. Backtracking.

19

5.1. Método general.

Variaciones del esquema general:

1) ¿Y si no es seguro que exista una solución?

2) ¿Y si queremos almacenar todas las soluciones (no

sólo una)?

3) ¿Y si el problema es de optimización (maximizar o

minimizar)?

A.E.D.

Tema 5. Backtracking.

20

10

5.1. Método general.

• Caso 1) Puede que no exista ninguna solución.

Backtracking (var s: TuplaSolución)

Para poder generar

todo el árbol de
backtracking

Generar (nivel, s)
si Solución (nivel, s) entonces

fin:= true

sino si Criterio (nivel, s) entonces

nivel:= nivel + 1

nivel:= 1
s:= sINICIAL
fin:= false
repetir

sino

finsi

mientras NOT MasHermanos (nivel, s)

AND (nivel>0)

hacer Retroceder (nivel, s)

hasta finfin OR (nivel==0)

A.E.D.

Tema 5. Backtracking.

21

5.1. Método general.

• Caso 2) Queremos almacenar todas las soluciones.

Backtracking (var s: TuplaSolución)

nivel:= 1
s:= sINICIAL
fin:= false
repetir

• En algunos problemas los nodos
intermedios pueden ser soluciones
• O bien, retroceder después de
encontrar una solución

Generar (nivel, s)
si Solución (nivel, s) entonces

Almacenar (nivel, s)
fin:= true

si Criterio (nivel, s) entonces
sino si Criterio (nivel, s) entonces

nivel:= nivel + 1

mientras NOT MasHermanos (nivel, s)

AND (nivel>0)

hacer Retroceder (nivel, s)

sino

finsi

hasta finnivel==0

A.E.D.

Tema 5. Backtracking.

22

11

5.1. Método general.

• Caso 3) Problema de optimización (maximización).

Backtracking (var s: TuplaSolución)

nivel:= 1
s:= sINICIAL
fin:= false
voa:= -∞; soa:= Ø
repetir

voa: valor óptimo actual
soa: solución óptima actual

Generar