PROBLEMA DEL CABALLO DE ATILA

Ing. Claudia Pereira

Facultad de Ciencias Exactas

Universidad Nacional del Centro de la Provincia de Buenos Aires

TÉCNICA DE DISEÑO

BACKTRACKING

Backtracking: Introducción

• La solución puede expresarse como una n-tupla (x1,x2,...xn)

donde los xi pertenecen a un cierto dominio.

• Función FACTIBLE: determina si una tupla cumple o no con las restricciones del problema.

• Función SOLUCIÓN: determina si una tupla factible es solución al problema.

• Función OBJETIVO a optimizar o satisfacer.

CARACTERÍSTICAS DEL PROBLEMA

Restricciones del problema:

• Explícitas: describen el dominio de los xi.

• Implícitas: describen las relaciones que deben

cumplirse entre los xi.

CARACTERÍSTICAS DEL PROBLEMA

Backtracking: Introducción

• Forma cada tupla de manera progresiva.

• Verifica si cada xi añadido a la tupla (x1,x2,..,xi) conduce a

una solución factible.

• Si FACTIBLE (x1,x2,..,xi) = Falso

• Corta la búsqueda• Prueba con otro valor válido de xi

• Si no existen valores válidos retrocede

• Si FACTIBLE (x1,x2,..,xi) = Verdadero

• Repite el procedimiento para incorporar x i+1 a la tuplaBacktracking: Introducción

TÉCNICA BACKTRACKING

Backtracking: Introducción

(x1) (x2) (x3) ........... (xn)

(x1 ,x1) (x1 ,x2) ...(x1 ,xn) (x3 ,x1) .... (xn ,x1) (xn ,x1)

(x1 ,x1 ,...x1) (x1 ,x1 ,...x2)....

..................

hijos

niveles

(xn ,x1 ,...x1)...(xn ,xn ,...xn)

..................

#niveles

#hijos i

i=0

Cantidad total de nodos: O (#hijos #niveles )

ESPACIO DE SOLUCIONES

Costo computacional exponencial

Solución

Funciones de PODA

• Ventaja

Si existe solución al problema entonces esta técnica la encuentra.

Poda por factibilidad

Poda por costo

Backtracking: Introducción

• Desventaja

Backtracking: Introducción

BACK (estado e, solucion *sol) \\ e: nodo del árbol de soluciones

{ \\sol: solución que retorna

if ( HOJA (e))

CalcularSolución (e, sol);

else

{

int nrohijo = 1;

estado siguiente;

while ( HIJOS (nrohijo, e, siguiente ) )

{ if ( !PODADO ( siguiente, sol) )

BACK ( siguiente, sol);

++nrohijo; }

}

}

ESQUEMA GENERAL

Enunciado:

Todos sabemos que por donde pisa el caballo de Atila jamás

vuelve a crecer el pasto. El caballo fue directamente hacia el jardín

de n x n casillas. Empezó su paseo por una casilla cualquiera y

volvió a ella, es decir, hizo un recorrido cerrado. No visitó dos

veces una misma casilla, se movió de una casilla a otra vecina en

forma horizontal o vertical, pero nunca en diagonal. Por donde

pisó el caballo, el pasto jamás volvió a crecer. Luego de terminado

el recorrido en algunas casillas todavía había pasto (señal de que

en ellas no había estado el caballo). Escriba un algoritmo que

deduzca el recorrido completo que hizo el caballo.

PROBLEMA: EL CABALLO DE ATILA

Ejemplo: el caballo de Atila

• Solución (pos1, pos2, pos3,......posn) posi es una casilla del jardín de m x m casillas

• Restricciones:

• Explícitas: posi {pos1, pos2, pos3,......posmxm}

• Implícitas: en la tupla solución,

• No hay dos posiciones iguales

• pos1 es una casilla del borde del jardín

• posi y posi+1 son casillas son adyacentes

• pos1 y posn son casillas adyacentes

• deben estar todas las casillas pisadas

CARACTERIZACIÓN DEL PROBLEMA

Estado inicial

Movimientos del caballo

No puede seguir avanzando

Estado solución

........................

Ejemplo: el caballo de Atila

Estados factibles

Espacio de soluciones

Espacio de soluciones:

Ejemplo: el caballo de Atila

Solución

recorrido

Ejemplo: el caballo de Atila

else

{

estado sgte; int nrohijo=1;

while ( hijos(nrohijo, e, sgte))

{ if ( sgte.esFactible() )

Atila( sgte, nroPisada+1);

nrohijo++;}}

}

void Atila (estado e, int nroPisada) {

e.marcar(nroPisada);

if ( ! e.HayMovimientos() )

{ if(( nroPisada== e.cantPisadas() ) && (e.vecinaOrigen()))

imprimirSolucion(e); }

Algoritmo para todas las soluciones

Depende de la cantidad de estados generados

Ejemplo: el caballo de Atila

TAtila(casillasPisadas) O( 3 #casillasPisadas)

O (#hijos #niveles )

Complejidad temporal

• Computer Algorithms C++; Horowitz, Sahni, Rajasekaran.

• Algorithms in C; Sedgewick

• Apuntes de cátedra.

BIBLIOGRAFÍA