TEMA 6
1. Introducción
Definición del Backtracking (Vuelta Atrás): Es un método para resolver problemas
combinatorios mediante una búsqueda sistemática de todas las posibles soluciones. Su
característica principal es permitir deshacer decisiones para explorar alternativas.
Motivación:
o Las técnicas voraces son rápidas, pero no siempre garantizan la solución óptima
o factible.
o Si el problema tiene restricciones complejas o múltiples caminos posibles, el
backtracking es una opción robusta.
Características Principales:
o Permite revertir decisiones tomadas previamente.
o Se utiliza para problemas donde se busca construir soluciones completas a
partir de decisiones parciales.
o En caso de encontrar un callejón sin salida, retrocede y prueba otro camino
(poda el árbol de búsqueda).
Ventajas:
o Garantiza encontrar todas las soluciones posibles (si existen).
o Es flexible y puede adaptarse a problemas de decisión, enumeración y
optimización.
2. Funcionamiento del Backtracking
1. Idea General:
o Construir una solución paso a paso.
o En cada etapa, evaluar todas las opciones posibles:
Si una opción es prometedora, continuar.
Si no lo es, retroceder y probar otra opción.
o Parar cuando se haya encontrado una solución deseada o al recorrer todo el
espacio de búsqueda.
2. Árbol de Búsqueda:
o Representa las posibles soluciones del problema como un árbol.
o Nodos: Estados parciales de la solución.
o Arcos: Transiciones entre estados basadas en decisiones.
o Retroceder implica podar ramas del árbol para evitar caminos no prometedores.
3. Exploración en Profundidad:
o Similar al algoritmo DFS (Depth-First Search) en grafos.
o El tamaño del grafo es grande y se genera dinámicamente.
o Se utiliza una pila para almacenar las decisiones actuales.
3. Aplicaciones Clásicas del Backtracking
3.1. Problema de las N-Reinas
Descripción del Problema:
o Colocar N reinas en un tablero de ajedrez N×N de forma que ninguna ataque a
otra.
o Restricciones:
Una sola reina por fila, columna y diagonal.
Enfoque Incremental:
o Colocar una reina por columna.
o Evaluar la factibilidad de cada posición en la fila correspondiente.
Algoritmo Básico:
o Para cada columna, intentar colocar una reina en cada fila válida.
o Si no es posible colocar la reina en la columna actual, retroceder a la columna
anterior.
Pseudocódigo:
3.2. Problema del Laberinto
Descripción del Problema:
o Encontrar un camino desde una entrada hasta una salida en un laberinto n×m,
donde ciertas casillas están bloqueadas.
Metodología:
o En cada casilla, intentar moverse en un orden predeterminado: Norte, Este, Sur,
Oeste.
o Si todos los movimientos son inválidos, retroceder.
o Marcar casillas visitadas para evitar ciclos.
Pseudocódigo:
4. Extensiones del Backtracking
1. Backtracking para Enumeración:
o Objetivo: Encontrar todas las soluciones posibles.
o En lugar de detenerse al encontrar la primera solución, se recorren todas las
ramas del árbol de búsqueda.
o Pseudocódigo:
2. Backtracking para Optimización:
Objetivo: Encontrar la mejor solución factible.
En cada solución parcial, mantener un registro de la mejor solución conocida y
compararla con las nuevas.
5. Complejidad del Backtracking
Tamaño del Árbol de Búsqueda:
o Crece exponencialmente con el número de decisiones posibles por nivel.
o Se puede estimar como: T=1+c1+c1c2+c1c2c3+…
Rendimiento:
o La eficiencia depende de:
Tamaño del espacio de búsqueda.
Calidad de la poda.
Orden de exploración.
Ejemplo Aplicado: Problema de la Suma de Subconjuntos
- Definición:
o Dado un conjunto S={s1,s2,…,sn} de números y un valor M, encontrar el
subconjunto cuya suma sea lo más cercana a M, sin excederlo.
- Estrategia:
o Explorar todas las combinaciones posibles de elementos del conjunto S.
o Comparar la suma actual con el mejor resultado hasta el momento.
- Pseudocódigo:
