tÉcnica de diseÑo backtracking
DESCRIPTION
TÉCNICA DE DISEÑO BACKTRACKING. PROBLEMA DEL CABALLO DE ATILA. Ing. Claudia Pereira Facultad de Ciencias Exactas Universidad Nacional del Centro de la Provincia de Buenos Aires. CARACTERÍSTICAS DEL PROBLEMA. - PowerPoint PPT PresentationTRANSCRIPT
![Page 1: TÉCNICA DE DISEÑO BACKTRACKING](https://reader036.vdocumento.com/reader036/viewer/2022083007/5681415b550346895dad3579/html5/thumbnails/1.jpg)
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
![Page 2: TÉCNICA DE DISEÑO BACKTRACKING](https://reader036.vdocumento.com/reader036/viewer/2022083007/5681415b550346895dad3579/html5/thumbnails/2.jpg)
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
![Page 3: TÉCNICA DE DISEÑO BACKTRACKING](https://reader036.vdocumento.com/reader036/viewer/2022083007/5681415b550346895dad3579/html5/thumbnails/3.jpg)
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
![Page 4: TÉCNICA DE DISEÑO BACKTRACKING](https://reader036.vdocumento.com/reader036/viewer/2022083007/5681415b550346895dad3579/html5/thumbnails/4.jpg)
• 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
![Page 5: TÉCNICA DE DISEÑO BACKTRACKING](https://reader036.vdocumento.com/reader036/viewer/2022083007/5681415b550346895dad3579/html5/thumbnails/5.jpg)
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
![Page 6: TÉCNICA DE DISEÑO BACKTRACKING](https://reader036.vdocumento.com/reader036/viewer/2022083007/5681415b550346895dad3579/html5/thumbnails/6.jpg)
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
![Page 7: TÉCNICA DE DISEÑO BACKTRACKING](https://reader036.vdocumento.com/reader036/viewer/2022083007/5681415b550346895dad3579/html5/thumbnails/7.jpg)
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
![Page 8: TÉCNICA DE DISEÑO BACKTRACKING](https://reader036.vdocumento.com/reader036/viewer/2022083007/5681415b550346895dad3579/html5/thumbnails/8.jpg)
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
![Page 9: TÉCNICA DE DISEÑO BACKTRACKING](https://reader036.vdocumento.com/reader036/viewer/2022083007/5681415b550346895dad3579/html5/thumbnails/9.jpg)
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
![Page 10: TÉCNICA DE DISEÑO BACKTRACKING](https://reader036.vdocumento.com/reader036/viewer/2022083007/5681415b550346895dad3579/html5/thumbnails/10.jpg)
Estado inicial
Movimientos del caballo
No puede seguir avanzando
Estado solución
........................
Ejemplo: el caballo de Atila
Estados factibles
Espacio de soluciones
![Page 11: TÉCNICA DE DISEÑO BACKTRACKING](https://reader036.vdocumento.com/reader036/viewer/2022083007/5681415b550346895dad3579/html5/thumbnails/11.jpg)
Espacio de soluciones:
Ejemplo: el caballo de Atila
Solución
recorrido
![Page 12: TÉCNICA DE DISEÑO BACKTRACKING](https://reader036.vdocumento.com/reader036/viewer/2022083007/5681415b550346895dad3579/html5/thumbnails/12.jpg)
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
![Page 13: TÉCNICA DE DISEÑO BACKTRACKING](https://reader036.vdocumento.com/reader036/viewer/2022083007/5681415b550346895dad3579/html5/thumbnails/13.jpg)
Depende de la cantidad de estados generados
Ejemplo: el caballo de Atila
TAtila(casillasPisadas) O( 3 #casillasPisadas)
O (#hijos #niveles )
Complejidad temporal
![Page 14: TÉCNICA DE DISEÑO BACKTRACKING](https://reader036.vdocumento.com/reader036/viewer/2022083007/5681415b550346895dad3579/html5/thumbnails/14.jpg)
• Computer Algorithms C++; Horowitz, Sahni, Rajasekaran.
• Algorithms in C; Sedgewick
• Apuntes de cátedra.
BIBLIOGRAFÍA