PDF de programación - Programación II - Tema 9. Vuelta atrás

Programación II
Bloque temático 1. Lenguajes de programación
Bloque temático 2. Metodología de programación
Bloque temático 3. Esquemas algorítmicos

Tema 4. Introducción a los Algoritmos
Tema 5. Algoritmos voraces, heurísticos y aproximados
Tema 6. Divide y Vencerás
Tema 7. Ordenación
Tema 8. Programación dinámica

Tema 9. Vuelta atrás

Tema 10.Ramificación y poda
Tema 11.Introducción a los Algoritmos Genéticos
Tema 12.Elección del esquema algorítmico

Programación II

Tema 9. Vuelta atrás

Tema 9. Vuelta atrás

© Mario Aldea Rivas

09/05/11



1



Introducción a la Vuelta Atrás

9.1.
9.2. Eficiencia de los algoritmos VA
9.3. Problema de la mochila con Vuelta Atrás
9.4. Las N Reinas
9.5. Laberinto
9.6. Bibliografía

© Mario Aldea Rivas

09/05/11

2

9.1 Introducción a la Vuelta Atrás

Programación II

Tema 9. Vuelta atrás

9.1 Introducción a la Vuelta Atrás
Los algoritmos de “Vuelta Atrás” (Backtracking) realizan una
exploración sistemática de las posibles soluciones del problema
Vuelta Atrás suele utilizarse para resolver problemas complejos

• en los que la única forma de encontrar la solución es

analizando todas las posibilidades
- ritmo de crecimiento exponencial

• constituye una forma sistemática de recorrer todo el espacio de

soluciones

En general, podremos utilizar Vuelta Atrás para problemas:
• con solución representada por una n-tupla {x1,x2,...,xn}
• en los que cada una de las componentes xi de ese vector es
elegida en cada etapa de entre un conjunto finito de valores
(y1,y2,...,yv)

Programación II

© Mario Aldea Rivas

09/05/11

3

Tema 9. Vuelta atrás

9.1 Introducción a la Vuelta Atrás
Introducción a la Vuelta Atrás (cont.)

El algoritmo va obteniendo soluciones parciales:

• normalmente el espacio de soluciones parciales es un árbol

- árbol de búsqueda de las soluciones

• el algoritmo realiza un recorrido en profundidad del árbol
• cuando desde un nodo no se puede seguir buscando la

solución se produce una vuelta atrás

Problema del cambio:
monedas:{v1=1,v2=2,v3=3}
cCambiar=4

2
{1}

{}1

3

{1,1}

11
{1,2}

15

{1,3}

4

{1,1,1}

8

{1,1,2}

10

{1,1,3}

16

{1,3,1}

9

{1,1,2,1}

12

{1,2,1}

14

{1,2,2}

17

{2}

24
{3}

18

{2,1}

22

{2,2}

25
{3,1}

27
{3,2}

26

{3,1,1}

5

{1,1,1,1}

7

{1,1,1,2}

6

{1,1,1,1,1}

Programación II

Tema 9. Vuelta atrás

19

{2,1,1}

21

{2,1,2}

23

{2,2,1}

13

{1,1,2,1}

20

{2,1,1,1}

© Mario Aldea Rivas

09/05/11

4

9.1 Introducción a la Vuelta Atrás
Introducción a la Vuelta Atrás (cont.)

Algunas definiciones:

• Nodo vivo: nodo del que todavía no se han generado todos sus

hijos

• Nodo prometedor: nodo que no es solución pero desde el que

todavía podría ser posible llegar a la solución

Dependiendo de si buscamos una solución cualquiera o la óptima
• el algoritmo se detiene una vez encontrada la primera solución
• o continúa buscando el resto de soluciones

Estos algoritmos no crean ni gestionan el árbol explícitamente

• se crea implícitamente con las llamadas recursivas al algoritmo

Programación II

Tema 9. Vuelta atrás

© Mario Aldea Rivas

09/05/11

5

9.2 Eficiencia de los algoritmos VA
La eficiencia de este tipo de algoritmos depende del número de
nodos que sea necesario explorar para cada caso

- es imposible de calcular a priori de forma exacta

9.2 Eficiencia de los algoritmos VA

Pero es posible calcular una cota superior
• sea n la longitud máxima de la solución
y 0..v-1 el rango de valores para cada
decisión tenemos que:

nodos

vi

vn≅

n
1–
∑=
0=

i

0

1

2

...

v-1

...

...

v0 nodos

v1 nodos

v2 nodos

...

vn-1 nodos

• luego su eficiencia temporal será O(vn)
- resultado muy pesimista en la mayoría de los casos

...

Tienen unos requisitos de memoria O(n)

- máxima “profundidad” de las llamadas recursivas

Programación II

© Mario Aldea Rivas

09/05/11

6

Tema 9. Vuelta atrás

9.3 Problema de la mochila con Vuelta Atrás

9.3 Problema de la mochila con Vuelta Atrás
Vamos a resolver otra versión del problema de la mochila:
• se dispone un número ilimitado de objetos de cada tipo
• los objetos no se pueden fraccionar (“mochila entera” o

“mochila {0,1}”)

• Problema NP-completo

El problema verifica las condiciones necesarias para que pueda
ser abordable utilizando Vuelta Atrás:

• la solución se puede representar con una N-tupla

- conjunto de objetos metidos en la mochila

• en cada etapa de formación de la solución de elige un nuevo

objeto de entre todos los objetos existentes (un conjunto finito)

Programación II

Tema 9. Vuelta atrás

© Mario Aldea Rivas

09/05/11

7

9.3 Problema de la mochila con Vuelta Atrás

Árbol de búsqueda del problema de la mochila
Veamos el árbol de búsqueda para un caso particular
• tipos de objetos: {p0=2,v0=3}, {p1=3,v1=5}, {p2=4,v2=6} y
{p3=5,v3=10}, N=4
• la mochila soporta un peso máximo Pm=8

{}0

{1}3

{2}5

{3}6

{4}10

{1,1}6

{1,2}8 {1,3}9 {1,4}13 {2,2}10 {2,3}11 {2,4}15 {3,3}12

{1,1,1}9

{1,1,2}11 {1,1,3}12

{1,2,2}13

{1,1,1,1}12
• La solución es la pareja {2,4}

Programación II

Tema 9. Vuelta atrás

solución

© Mario Aldea Rivas

09/05/11

8

9.3 Problema de la mochila con Vuelta Atrás

Pseudocódigo (sólo da valor máximo)
// retorna el máximo valor que podemos guardar en
// una mochila de peso máximo pm
método mochila(entero pm) retorna entero
v:=0 // valor almacenado
// probamos si cabe cada clase de objeto
desde n:=0 hasta N-1 hacer
si pn<=pm entonces
// el objeto cabe en la mochila
v:=max(v, vn+mochila(pm-pn))
fsi
fhacer
retorna v
fmétodo
Se puede optimizar este algoritmo

• para no repetir en una llamada recursiva casos ya explorados

con anterioridad

Programación II

© Mario Aldea Rivas

09/05/11

9

Tema 9. Vuelta atrás

9.3 Problema de la mochila con Vuelta Atrás

Pseudocódigo optimizado
// retorna el máximo valor que podemos guardar en
// una mochila de peso máximo pm utilizando sólo
// objetos de los tipos n0..N-1
método mochila(entero n0, entero pm) retorna entero
v:=0 // valor almacenado
// probamos si cabe cada clase de objeto
desde n:=n0 hasta N-1 hacer
si pn<=pm entonces
// el objeto cabe en la mochila
v:=max(v, vn+mochila(n,pm-pn))
fsi
fhacer
retorna v
fmétodo
La primera llamada a este método será:
mochila(0,P) // donde P es el peso máximo

Programación II

Tema 9. Vuelta atrás

© Mario Aldea Rivas

09/05/11

10

9.3 Problema de la mochila con Vuelta Atrás

Árbol de búsqueda
La llamadas recursivas incluidas en el pseudocódigo anterior
generan el árbol de búsqueda formado por las soluciones
parciales
Ejemplo de árbol de búsqueda para un caso sencillo:
• tipos de objetos: {p0=1,v0=2} y {p1=2,v1=3}, N=2
• la mochila soporta un peso máximo Pm=2
v=4

mochila(0,1)

n=1

v=2

+v1

mochila(0,0)
n=2

n=1

v=0

Programación II

Tema 9. Vuelta atrás

v=3

mochila(0,2)
v=4
+v1

+v2

n=1

n=2

n=2
v=0

mochila(1,0)
n=2
n=1

© Mario Aldea Rivas

09/05/11

11

9.3 Problema de la mochila con Vuelta Atrás

Eficiencia (resultado pesimista)
Para un problema con N tipos de objetos, en que el peso máximo
es Pm y el peso del objeto más ligero es p
• el número máximo de objetos que caben en la mochila es Pm/p
N0 nodos

0

1

2

...

N-1

...

...

...

N1 nodos

N2 nodos

...

NPm/p-1 nodos

Su eficiencia es proporcional al máximo número de nodos que
puede ser necesario explorar
• Eficiencia: O(NPm/p)

Programación II

© Mario Aldea Rivas

09/05/11

12

Tema 9. Vuelta atrás

9.3 Problema de la mochila con Vuelta Atrás

Pseudocódigo (retorna objetos incluidos)
método mochila(entero n0, entero pm)
retorna listaIncluidos
listaIncluidos:=∅ // lista vacía
// probamos si cabe cada clase de objeto
desde n:=n0 hasta N-1 hacer
si pn<=pm entonces
lista := mochila(n, pm-pn)
si vn+lista.v > listaIncluidos.v entonces
// ‘lista’ más el nuevo objeto tiene mejor
// valor que ‘listaIncluidos’
listaIncluidos := lista
añade objeto n a listaIncluidos
fsi
fsi
fhacer
retorna listaIncluidos
fmétodo

Programación II

Tema 9. Vuelta atrás

© Mario Aldea Rivas

09/05/11

13

9.3 Problema de la mochila con Vuelta Atrás

Implementación (retorna objetos incluidos)
// cada uno de los tipos de objetos disponibles para
// incluir en la mochila
public static class ObjetoMochila {
int v;
int p;
String nombre;
public ObjetoMochila(int v, int p, String nombre){
this.v=v; this.p=p; this.nombre=nombre;
}
}

// solución del algoritmo: lista de objetos
// incluidos en la mochila y suma de su valor
public static class SoluciónMochila {
int v = 0;
LinkedList<ObjetoMochila> lista =
new LinkedList<ObjetoMochila>();
}

Programación II

Tema 9. Vuelta atrás

© Mario Aldea Rivas

09/05/11

14

9.3 Problema de la mochila con Vuelta Atrás

Implementación (retorna objetos incluidos) (cont.)

// método que retorna el contenido óptimo de la mochila
// (conjunto de objetos con el que se consigue el mayor valor)
// Recibe como argumentos el array con los objetos y
// el peso máximo soportado por la mochila
// Llama a mochilaRec
public static SoluciónMochila
mochila(ObjetoMochila[] objs, int pm){
return mochilaRec(0,objs,pm);
}

// retorna el conjunto de objetos con mayor valor que podemos
// guardar en una mochila de peso máximo pm utilizando sólo
// objetos de los tipos n..obj.length-1
private static SoluciónMochila
mochilaRec(int n0, ObjetoMochila[] objs, int pm){
... // código en la transparencia siguiente

Programación II

© Mario Aldea Rivas

09/05/11

15

Tema 9. Vuelta atrás

9.3 Problema de la mochila con Vuelta Atrás

Implementación (retorna objetos incluidos) (cont.)

private static SoluciónMochila
mochilaRec(int n0, ObjetoMochila[] objs, int pm) {
SoluciónMochila sm = new SoluciónMochila();
// probamos si cabe cada clase de objeto
for(int n=n0; n<objs.