Universidad Nacional de Trujillo
Facultad de Ciencias Físicas y Matemáticas
Ingeniería Informática
Curso: Estrategias Algorítmicas
Daniel Augusto Alvarez Campos
Temas.
Introducción
Desarrollo
Conclusiones
Referencias
Introducción
Introducción.
La búsqueda con retroceso (backtracking) es una técnica de algoritmos
utilizada para resolver problemas de toma de decisiones, donde se busca una
solución incrementando progresivamente una construcción parcial hasta que
se encuentra una solución completa.
Introducción.
Si en algún punto se determina que la construcción parcial no puede llevar a
una solución válida, se retrocede (backtrack) al estado anterior y se intenta
con una alternativa diferente. Esta técnica es especialmente útil para
problemas de combinatoria, como el Sudoku, el problema de las N-reinas y la
generación de anagramas.
Desarrollo
BACKTRAKING
- Backtraking (o búsqueda atrás) es una táctica de programación para hacer búsqueda
sistemática a través de todas las configuraciones posibles dentro de una espacio de
búsqueda.
- Para lograr esto, los algoritmos de tipo backtraking construyen posibles soluciones
candidatas de manera sistemática.
BACKTRAKING
- En general, dado una solución candidata s:
1. Verifican si s es solución. Si lo es, hacen algo con ella (depende del problema).
2. Construyen todas las posibles extensiones de s, e invocan recursivamente al algoritmo
con todas ellas.
- A veces los algoritmos de tipo backtraking se usan para encontrar una solución, pero otras
veces interesa que las revisen todas (por ejemplo, para encontrar la ruta más corta)
Suposición sobre el espacio de soluciones
Suposiciones sobre el espacio de soluciones
• Supondremos que una solución se puede modelar como un vector a = (a1,
a2, . . . , an), donde cada elemento ai está tomado de un conjunto ordenado
finito Si.
• Representamos a una solución candidata como un vector a = (a1, . . . , ak).
• Las soluciones candidatas se extenderán agregando un elemento al final.
Algoritmo Genérico de Backtraking
Donde
Solucion?(·) es una función que retorna verdadero si su argumento es una solución.
• procesarSolucion(·), depende del problema y que maneja una solución.
• Sucesores(·) es una función que dado un candidato, genera todos los candidatos que
son extensiones de éste.
• terminar? es una variable global booleana inicialmente es falsa, pero que puede ser
hecha verdadera por procesarSolucion, en caso que solo interesa encontrar una
solución.
Algunas aplicaciones con el Algoritmo de
Backtraking
Problema de las n-reinas
El problema de las n reinas consiste en colocar en un tablero n
reinas tal que no se amenacen.
Problema de las n-reinas: Número de soluciones
Problema de las n reinas – Solución
Problema de las n reinas – Solución
Problema de las n reinas – Solución
Problema de las 4 reinas – Solución
Representación del Árbol 4 reinas
Problema de la mochila
Problema de la mochila con n objetos – Solución
Problema de la mochila n objetos – Solución
Problema de la mochila con 4 objetos
Problema de la mochila con 4 objetos – Solución
Problema de la mochila con 4 objetos Solución
Representación del Árbol mochila
Graph Coloring
Problema del Coloreo de Mapas – Solución
Problema del Coloreo de Mapas - Solución
Representación del Coloreo de Mapas
Cierre
Conclusiones.
En conclusión, la búsqueda con retroceso es una técnica poderosa
para resolver problemas complejos que implican múltiples decisiones
y condiciones.
TRABAJO FINAL – UNIDAD 3
Resolver el VRP(Problema de Ruteo de Vehículos: escoger una variante)
utilizando el algoritmo visto en clase
Consultas.
