1

1

Departamento de Lenguajes y Sistemas Informáticos

UNIVERSIDAD DE ALICANTE

TEMA 6VUELTA ATRÁS

2

VUELTA ATRÁS (Backtracking) EJEMPLO INTRODUCTORIO (1)

El Problema de la Mochila (general). Sean n objetos con valoresvi y pesos pi y una mochila con capacidad máxima de transporte de un peso P. Seleccionar un conjunto de objetos de forma que:

no sobrepase el peso P (restricción)el valor transportado sea máximo (función objetivo)

¿Cómo obtener la solución óptima?Programación dinámica: Objetos no fragmentables y pesos discretos. Algoritmos Voraces: Objetos fragmentables

¿Cómo lo resolvemos si no podemos fragmentar los objetos y los pesos son valores reales?

2

3

VUELTA ATRÁSEJEMPLO INTRODUCTORIO (2)

El Problema de la Mochila (general). Sean n objetos con valoresvi y pesos pi y una mochila con capacidad máxima de transporte de un peso P. Seleccionar un conjunto de objetos de forma que:

no sobrepase el peso P (restricción)el valor transportado sea máximo (función objetivo)

¿Cómo obtener la solución óptima?Programación dinámica: Objetos no fragmentables y pesos discretos. Algoritmos Voraces: Objetos fragmentables

¿Cómo lo resolvemos si no podemos fragmentar los objetos y los pesos son valores reales?

Generar todas las combinaciones posibles (espacio de soluciones)Seleccionar las que cumplen las restricciones (soluciones factibles)Elegir aquella que maximiza la función objetivo (solución óptima)

4

VUELTA ATRÁS EJEMPLO INTRODUCTORIO (3)

Tipificación del problema:

Solución =

Restricciones:Implícitas

Explícitas

Función objetivo: (valor transportado)

1

n

i ii

x p P=

≤∑

1 2, , , n iX x x x x=< … > ∈

1

Maxn

i ii

x v=∑

{ }0,1ix ∈0 no se selecciona el objeto 1 se selecciona el objeto completo

i

i

x ix i=⎧

⎨ =⎩

3

5

Solución OPTIMA

VUELTA ATRÁS EJEMPLO INTRODUCTORIO (4)

Combinaciones posiblesSupongamos el siguiente ejemplo:

Espacio de soluciones:

16

(7,8,2)3

(49, 40,20)

P

pn

v

=⎧⎪⎨ =⎧

=⎪ ⎨ =⎩⎩

SOLUCIÓN PESO VALOR

(0,0,0) 0 0

(0,0,1) 2 20

(0,1,0) 8 40

(0,1,1) 10 60

(1,0,0) 7 49

(1,0,1) 8 69

(1,1,0) 15 89

(1,1,1) 17 109

Soluciones factibles

Solución NO factible

6

funcion GENERA (n,k:ent;) x:vector[{0,1}])

para j ∈{0,1} hacerxk = jopcion

(k=n):Imprimir(x);(k<n):GENERA (n,k+1,x);

fopcionfpara

fin

VUELTA ATRÁS EJEMPLO INTRODUCTORIO (5)

Generación de todas las combinaciones

Ejemplo n=3: { }1 2 3, , / 0,1ix x x x< > ∈

00? 01?

0??

000 001 010 011

10? 11?

1??

100 101 110 111

???

4

7

VUELTA ATRÁS EJEMPLO INTRODUCTORIO (6)

Generación de las soluciones factibles

Complejidad:Caso peor:

Caso mejor

funcion MOCHILA (v,p:vector[real];P:real;n,k:entero;x:vector[{0,1}])

para j ∈{0,1} hacerxk = j

si (Σ(k)xipi≤P)opcion(k=n) : Imprimir(x);(k<n) : MOCHILA(v,p,P,n,k+1,x);

fopcionfinsi

fparafin

1

n

i ii

x p P=

≤∑

, ii p P∀ >

( ) 2· ( 1) (2 )nf n f n n= − + ∈Ο

2( ) ( )f n n∈Ω

8

funcion MOCHILA (v,p:vector[real]; P,v_mejor:real; n,k:entero;x,x_mejor:vector[{0,1}])

para j ∈{0,1} hacerxk = j

si (Σ(k)xipi≤P)opcion(k=n) : si valor(x)>v_mejor entonces

x_mejor=x;v_mejor=valor(x);

finsi

(k<n) : MOCHILA(v,p,P,v_mejor,n,k+1,x,x_mejor);fopcion

finsifpara

fin

VUELTA ATRÁS EJEMPLO INTRODUCTORIO (7)

Búsqueda de la solución óptima

5

9

VUELTA ATRÁS DEFINICIÓN Y ÁMBITO DE APLICACIÓN

Algunos problemas sólo podemos resolverlos mediante la obtención y estudio exhaustivo del conjunto de posibles soluciones al problema.

De entre todas ellas, se podrá seleccionar un subconjunto o bien, aquella que consideremos la mejor (la solución óptima)

Para llevar a cabo el estudio exhaustivo Vuelta atrás proporciona una forma sistemática de generar todas las posibles soluciones a un problema.

Generalmente se emplea en la resolución de problemas de selección / optimización en los que el conjunto de soluciones posibles es finito.

En los que se pretende encontrar una o varias soluciones que sean:Factibles: que satisfagan unas restricciones y/oÓptimas: optimicen una cierta función objetivo

10

VUELTA ATRÁS CARACTERÍSTICAS

La solución debe poder expresarse mediante una tupla de decisiones< x1 , x2 , .... , xn > donde xi ∈ Di

Las decisiones pueden pertenecer a dominios diferentes pero estos dominios siempre serán discretos.

Se generan y estudian todas las posibles soluciones

La estrategia siempre proporcionaTodas las soluciones factiblesLa solución óptima al problemaPero... con una complejidad elevada (2n, n!, nn)

6

11

VUELTA ATRÁS CARACTERÍSTICAS

La generación y búsqueda de la solución se realiza mediante un sistema de prueba y error:Sea < x1 , x2 , ...., xi-1 , ..., > una tupla por completar. Decidimos sobre xi

Si Cumple restricciones: se añade xi a la solución y se pasa a xi+1Si no cumple restricciones: se prueba otra posibilidad para xi

Si No cumple restricciones y no hay más posibilidades con xi : se replantea la decisión anterior xi-1

La generación y búsqueda se realiza utilizando una imaginaria estructura de árbol sobre la que se realiza un recorrido en preorden.

12

VUELTA ATRÁS ESQUEMA RECURSIVO

BACKTRACKING (DP:datos_problema; k:entero; var x:tupla)comienzo

Pk = {j : j ∈ Dk} (Posibles valores xk)mientras (Pk ≠ ∅) (comprobar todos los valores para xk)

xk = elemento(Pk) (selección de valor para xk)si factible(x)

opcionsolucion(x): tratar(x) (Todas,la mejor,etc)

¬ solucion(x): BACKTRACKING(D,k+1,x)fopcion

finsiPk = Pk – {xk}

fmientrasfin

7

13

VUELTA ATRÁS BACKTRACKING VS. GREEDY

GREEDYLos dominios son continuosBuscamos la solución óptima y existe un criterio de decisión voraz que nos conduce a ella.Buscamos una aproximación a la solución óptima.

BACKTRACKINGLos dominios no son continuosBuscamos todas las soluciones factibles o todas las soluciones óptimasBuscamos una solución óptima y el problema no tiene solución voraz.

14

VUELTA ATRÁS EJERCICIOS

EJERCICIOS OBLIGATORIOSEl Viajante de Comercio (ciclos hamiltonianos)Problema de las n reinasEl laberinto

OTROS EJERCICIOSTransformación de un númeroPermutacionesEl coloreado de grafos (coloreado de mapas)La empresa navieraEl reparto de paquetesLa asignación de turnos

8

15

EjerciciosPROBLEMA DEL VIAJANTE DE COMERCIO: Solución VORAZ

En un grafo no dirigido y completo encontrar un ciclo hamiltoniano de mínimo coste, es decir, pasar por todos los vértices una sola vez y regresar al de partida de forma que el coste final sea mínimo.

Tipificación del problema:Secuencia de aristas que expresan el recorrido

Función objetivo: Minimizar el coste de la solución

Restricciones:xi ∈ V 1≤ i ≤ nNo existen nodos de grado 3No se forman bucles o ciclos excepto al final

1 2 2 3 1 1( , ), ( , ), , ( , ), ( , )n n nx x x x x x x x−< … >

1

1 11

Min peso( , ) peso( , )n

i i ni

x x x x−

+=

⎡ ⎤+⎢ ⎥⎣ ⎦∑

16

EjerciciosPROBLEMA DEL VIAJANTE DE COMERCIO: Solución voraz

funcion VIAJANTE_GREEDY (A:aristas;n:N): cjto_aristasvar y, solución: cjto_aristas;

decisión: arista;comienzo

solución=∅;y=ORDENA_PESOS_CRECIENTE(A);mientras |y|>0 ∧ |solución|≠n hacer

decisión=primero(y);si (¬∃_vértices_grado3(solución,decisión)) ∧

(¬∃_bucles(solución,decisión) ∨ |solución|=n-1) entoncessolución=AÑADIR(solución,decisión);

fsiy=ELIMINAR_PRIMERO(y);

fmientrassi (|solución|=n) entonces

devuelve(solución);si_no

devuelve(∅); /* No hay solución */fsi

fin

9

17

EjerciciosPROBLEMA DEL VIAJANTE DE COMERCIO: Solución voraz

Criterio de selección: Tomar las aristas de menor peso.Inconveniente: No proporciona la solución óptima, pero sí una aproximada con coste razonable.Complejidad Ο(n3)

En función de:n = número de nodosn2 = número de aristas

ORDENA_PESOS_CRECIENTES → Ο(n2logn2)bucle mientras → Ο(n3)

Ο(n2) (en el caso peor, comprobar todas las aristas)∃_vértices_grado3 → Ο(n) (analizar el grado de cada vertice)∃_bucles → Ο(n) (Recorrer la solución y ver si hay bucles)

18

EjerciciosPROBLEMA DEL VIAJANTE DE COMERCIO: Solución VUELTA ATRAS

Tipificación del problema:Secuencia de vértices visitados

Fijamos el 1 como primer vértice

Función objetivo: Minimizar el peso total asociado a x

Restricciones:No podemos pasar dos veces por el mismo vértice, es decir, hay que comprobar que no hay elementos repetidos:

Debe existir arista entre un vértice y el siguiente:

Debe existir un camino de vuelta al principio:

1 2, , , nx x x< … >

1 1i ji j x x i n j n≠ ⇒ ≠ ≤ ≤ ≤ ≤

21, , , [2,n]n ix x x< … > ∈

1( , ) 1 -1i ipeso x x i n+ ≠ ∞ ≤ ≤

1( , )npeso x x ≠ ∞

10

19

EjerciciosPROBLEMA DEL VIAJANTE DE COMERCIO: Solución vuelta atrás

/* Inicialización y llamada inicial */v_mejor=∞;X[1]=1; // Partimos del vértice 1VIAJANTE_BT(G,num_vertices(G),2, v_mejor,x, x_mejor);

/* Función */funcion VIAJANTE_BT (G:grafo;n,k,v_mejor:entero;x,x_mejor:vector[ent]))comienzo

xk=1;mientras xk<n hacerxk=xk+1;opcion

(k=n) ∧ (peso(xn-1,xn)≠∞) ∧ (peso(xn,x1)≠∞) ∧ ¬Repetido(x,n)):si peso_total(x)< v_mejor entonces

v_mejor=peso_total(x);x_mejor=x;

fsi(k<n) ∧ (peso(xk-1,xk)≠∞) ∧ (¬Repetido(x,k)):

VIAJANTE_BT (G,n,k+1,v_mejor,x,x_mejor);fopcion

fmientrasfin

20

EjerciciosPROBLEMA DEL VIAJANTE DE COMERCIO: Solución vuelta atrás

/* Versión Iterativa */funcion VIAJANTE_BT (var G:grafo)var x:vector[1,n]; k:entero;comienzo

x1=1; k=2; xk=1; v_mejor=∞;mientras k>1 hacersi xk<n entonces

xk=xk+1;opcion(k=n) ∧ (peso(xn-1,xn)≠∞) ∧ (peso(xn,x1)≠∞) ∧ ¬Repetido(x,n)):

si peso_total(x)< v_mejor entoncesv_mejor=peso_total(x);x_mejor=x;

fsi(k<n) ∧ (peso(xk-1,xk)≠∞) ∧ (¬Repetido(x,k)):

k=k+1;xk=1;fopcion

si_no k=k-1;fmientrasdevuelve x_mejor;

fin

11

21

EjerciciosPROBLEMA DE LAS n REINAS

En un tablero de n x n, colocar n reinas sin que se “maten” entre sí.

Tipificación del problema:Secuencia de decisiones en la que cada xi es la columna en la que se encuentra la reina i (fila i)Restricciones:

Dos reinas no pueden estar en la misma columna

Dos reinas no pueden estar en la misma diagonal

Aunando ambas restricciones:

i j

i j

i x j x

x i x j

+ ≠ +

− ≠ −

i jx x i j− ≠ −

1 1i ji j x x i n j n≠ ⇒ ≠ ≤ ≤ ≤ ≤

22

EjerciciosPROBLEMA DE LAS n REINAS

funcion nREINAS (n,k:entero; x:vector[{1,...,n}])comienzoxk=0;mientras xk<n hacer

xk= xk+1;opcion

(k=n) ∧ CORRECTO(x,n): Imprimir(x);(k<n) ∧ CORRECTO(x,k): nREINAS(n,k+1,x);

fopcionfmientras

fin

funcion CORRECTO (var x: vector[{1,...,n}]; k:entero)var i:entero; ok:booleanocomienzo

i=1; ok=cierto;mientras (i>k) ∧ ok hacer

si (xi=xk) ∨ (abs(xi-xk)=abs(i-k)) entonces ok=falso;i=i+1;

fmientrasdevuelve ok

fin

12

23

EjerciciosPROBLEMA DEL LABERINTO (2 MOVIMIENTOS)

Buscar todos los caminos posibles en una laberinto representado por una matriz de n x m, partiendo de la posición (1,1)hasta llegar a la posición (n,m).Sólo se pueden hacer dos movimientos:

derecha (→)abajo (↓).

Tipificación del problema:Secuencia de decisiones en la que cada xi es la dirección en la que nos movemos:

Restricciones:No salirse del laberinto ni tocar los muros

1 2 ?, , ,x x x< … >

{ }( )

( )0 ir hacia la derecha

0,1 1 ir hacia abajoix

→∈

↓

24

EjerciciosPROBLEMA DEL LABERINTO

funcion LABERINTO (n,m,k:entero; x:vector[{0,1}] )comienzoxk=-1; mientras xk<1 hacer

xk = xk+1;opcion(k=n+m-2) ∧ CORRECTO(x,k): Imprimir(x);(k<n+m-2) ∧ CORRECTO(x,k): LABERINTO(n,m,k+1,x);fopcion

fmientrasfin

funcion CORRECTO (var x:vector[{0,1}]; k:entero): booleanovar i, filas, columnas:enterocomienzo

i=1; filas=1; columnas=1;mientras i ≤ k hacer

si xi=0 entonces columnas++si_no filas++;i=i+1;

fmientrassi (filas ≤ n) ∧ (columnas ≤ m) entonces

devuelve M[filas,columnas]si_no devuelve falso

fin

13

25

EjerciciosPROBLEMA DE LA TRANSFORMACIÓN DE UN NÚMERO

Transformar un número n en otro m usando dos funciones f(x) y g(x)con un número máximo de transformaciones P.

f(x) = 3xg(x) = x/2 (división entera)

Tipificación del problema:Secuencia de decisiones

Función que comprueba las transformaciones realizadas:F(x,q,n) = x1(x2( x3 .... xq(n) ....)) = m , q ≤ P

Restricciones:k ≤ P k = nº de transformacionesF(x,k,n) ≠ 0F(x,k,n) ≠ F(x,i,n) i<k (valor repetido)

1 2 ?, , ,x x x< … >

{ }0 se aplica ( )

0,1 1 se aplica g( )i

f xx

x∈

26

EjerciciosPROBLEMA DE LA TRANSFORMACIÓN DE UN NÚMERO

v_mejor=P+1; /* inicialización previa de v_mejor */

funcion TRANSFORMA (P,n,m,k:entero; x,x_mejor:vector; v_mejor:entero)

comienzopara j ∈{‘f’,`g’} hacer

xk=j;opcion

F(x,k,n)=m: si k<v_mejor entoncesv_mejor=k;x_mejor=x;

finsi;(P>k ∧ F(x,k,n)≠m ∧ F(x,k,n)≠0 ∧(k<v_mejor) ∧ ¬Repetido(x,k,n)):

TRANSFORMA(n,m,k+1,x,x_mejor,v_mejor);fopcion

fparafin

14

27

EjerciciosPERMUTACIONES

Dado un vector V de n elementos de tipo general ∂, implementar un algoritmo que sea capaz de hallar todas las permutaciones de sus elementos.

28

EjerciciosEL COLOREADO DE GRAFOS

Dado un grafo conexo y un número de colores m>0, llamamos colorear el grafo a asignar un número i (1 <= i <= m) a cada vértice, de forma que dos vértices adyacentes nunca tengan asignados números (o colores) iguales.

Deseamos diseñar dos algoritmos. El primero obtendrá todas las formas diferentes de colorear un grafo dadoEl segundo permitirá colorear un grafo dado empleando el mínimo número de colores diferentes

15

29

EjerciciosLA EMPRESA NAVIERA

Supongamos una empresa naviera que dispone de una flota de Nbuques cada uno de los cuales transporta mercancías de un valor vi que tardan en descargarse un tiempo ti. Solo hay un muelle de descarga y su máximo tiempo de utilización es T.

Diseñar un algoritmo que determine el orden de descarga de los buques de forma que el valor descargado sea máximo sin sobrepasar el tiempo de descarga T. (Si se elige un buque para descargarlo, es necesario que se descargue en su totalidad).

30

EjerciciosEL REPARTO DE PAQUETES

Una empresa de transportes dispone de M vehículos para repartir N paquetes todos al mismo destino. Cada paquete tiene un peso Pi y tiene que estar entregado antes de un tiempo TPi. Por otra parte, cada vehículo puede transportar una carga máxima Cj, tarda un tiempo TVj en llegar al destino y consume una cantidad Lj de litros de combustible independiente de la carga que transporte.

Diseñar un algoritmo que obtenga la forma en que se deben transportar los objetos (en qué vehículo j debe ir cada objeto i) para que el consumo sea mínimo.

16

31

EjerciciosEL LABERINTO

Una matriz bidimensional nxn puede representar un laberinto cuadrado. Cada posición contiene un entero que indica si la casilla es transitable (1) o no lo es (0). Las casillas [1,1] y [n,n]corresponden a la entrada y salida del laberinto y siempre serán transitables.Podemos desplazarnos de una casilla a otra adyacente empleando los movimientos: arriba, abajo, derecha o izquierda (no se permiten movimientos en diagonal).Dada una matriz con un laberinto, el problema consiste en diseñar un algoritmo que encuentre un camino, si existe, para ir de la entrada a la salida.

32

EjerciciosLA ASIGNACIÓN DE TURNOS

Estamos al comienzo del curso y los alumnos deben distribuirseen turnos de prácticas. Para solucionar este problema sepropone que valoren los turnos de práctica disponibles a los quedesean ir en función de sus preferencias. El número de alumnoses N y el de turnos disponibles es T. Se dispone una matriz depreferencias P con N filas y T columnas en la que cada alumnoescribe, en su fila correspondiente, un número entero (entre 0 yT) que indica la preferencia del alumno por cada turno (un valor 0indica que no quiere o no puede ir a dicho turno). Por otra parte,dispondremos de un vector C con T elementos que incluye lacapacidad de cada turno y que, por supuesto no podremossobrepasar.

17

33

EjerciciosLA ASIGNACIÓN DE TURNOS

Por ejemplo, supongamos que hay 5 alumnos. Según el ejemplo en de matriz P, el alumno 1 no puede ir al tuno T1 y al que más preferencia asigna es al T3. Por otro lado, el vector contiene las capacidades máximas de cada turno.

Se pretende encontrar una solución para satisfacer el número máximo de alumnos según su orden de preferencia sin exceder la capacidad de los turnos.

P T1 T2 T3A1 0 1 2A2 1 2 3A3 3 2 1A4 0 0 1A5 2 1 0

CT1 3T2 2T3 4