Backtracking:una técnica sistemática de resolución de problemas
El retroceso es una poderosa técnica algorítmica utilizada para resolver problemas que implican buscar una solución entre una gran cantidad de posibilidades. Funciona construyendo incrementalmente soluciones candidatas y abandonando ("retroceso") a un candidato tan pronto como determine que el candidato no puede conducir a una solución válida. Piense en ello como una forma inteligente y estructurada de realizar una búsqueda de profundidad primero a través de un árbol de decisión.
Ideas clave:
* Edificio incremental: El retroceso construye soluciones paso a paso, agregando una pieza a la vez.
* poda (satisfacción de restricción): En cada paso, verifica si la solución parcial actual satisface las limitaciones del problema. Si no es así, inmediatamente abandona ese camino y se remonta al punto de decisión anterior. Este paso de poda reduce drásticamente el espacio de búsqueda.
* recurre (a menudo): El retroceso a menudo se implementa utilizando funciones recursivas, donde cada llamada recursiva representa una opción o paso en el proceso de construcción de soluciones.
* Árbol de decisión: Puede visualizar el proceso de búsqueda como un árbol de decisión, donde cada nodo representa un estado (solución parcial) y los bordes representan opciones o acciones. El retroceso explora este árbol de manera profunda.
Cómo funciona (algoritmo general):
1. Comience con una solución vacía (o parcialmente inicializada).
2. Haga una elección (explore una rama): Seleccione un posible valor o acción para extender la solución actual.
3. Verifique la validez:
* Si la solución es válida (satisface las restricciones):
* ¿La solución está completa?
* Sí: Devuelve la solución.
* no: Llame recursivamente a la función de retroceso para tomar otra opción y continúe construyendo la solución.
* Si la solución no es válida (viola las restricciones):
* Backtrack: Deshacer la última opción y probar una diferente. Si todas las opciones se han probado en este nivel, retroceda al nivel anterior.
4. Sin solución: Si todas las opciones posibles se han agotado sin encontrar una solución válida, indique que no existe una solución.
Analogía:resolver un laberinto
Imagina que estás resolviendo un laberinto. Empiezas en la entrada y prueba diferentes caminos.
* avanzar: Usted hace una "elección" moviéndose por un camino.
* Buena ruta (válida): Si el camino parece estar conduciendo hacia la salida, continúa.
* Deat End (inválido): Si llega a un callejón sin salida, "retrocede" sobre sus pasos a la última intersección (punto de decisión) y pruebe una ruta diferente.
* resuelto: Si llega a la salida, ha encontrado una solución.
Casos de uso comunes en la programación:
* Problemas de satisfacción de restricción (CSP): Problemas en los que el objetivo es encontrar un conjunto de valores para variables que satisfagan un conjunto de restricciones.
* n-ceaens Problema: Colocando n reinas de ajedrez en un tablero de ajedrez NXN para que no hay dos reinas amenazadas entre sí.
* Solver Sudoku: Llenar una cuadrícula de 9x9 con dígitos para que cada fila, columna y subgrid 3x3 contenga todos los dígitos de 1 a 9.
* Map Coloring: Asignando colores a las regiones en un mapa para que no hay dos regiones adyacentes que tengan el mismo color.
* Problemas de optimización combinatoria: Encontrar la mejor solución de un gran conjunto de combinaciones posibles.
* Problema de vendedor ambulante (TSP): Encontrar la ruta más corta posible que visita cada ciudad en una lista y regresa a la ciudad inicial (el retroceso se puede usar para pequeñas instancias, pero otros algoritmos son más eficientes para instancias más grandes).
* Problema de mochila: Determinar el subconjunto más valioso de elementos que pueden caber en una mochila con una capacidad de peso limitada.
* Problema de suma de subconjunto: Encontrar un subconjunto de un conjunto de números que suma a un valor objetivo dado.
* Análisis de análisis y sintaxis:
* Gramáticas sin contexto: El retroceso se puede usar en analizadores para probar diferentes derivaciones de una oración hasta que se encuentre un árbol de análisis válido.
Ejemplo:problema N-Queens (simplificado)
Ilustremos el problema de N-Queens con N =4 (una placa 4x4).
`` `Python
def is_safe (tablero, fila, col):
"" "Comprueba si colocar a una reina en el tablero [fila] [col] es seguro". ""
# Verifique la misma columna
para i en rango (fila):
if board [i] [col] ==1:
devolver falso
# Verifique la diagonal de la parte superior izquierda
para i, j en zip (rango (fila -1, -1, -1), rango (col -1, -1, -1)):
if board [i] [j] ==1:
devolver falso
# Verifique la diagonal de la parte superior derecha
para i, j en zip (rango (fila -1, -1, -1), rango (col + 1, 4)):
if board [i] [j] ==1:
devolver falso
Devolver verdadero
Def solve_n_queens_util (tablero, fila):
"" "Función de ayuda recursiva para resolver el problema N-Queens". ""
Si fila ==4:# todas las reinas se colocan correctamente
Devolver verdadero
para col en el rango (4):
if is_safe (tablero, fila, col):
tablero [fila] [col] =1 # coloca a la reina
Si solve_n_queens_util (tablero, fila + 1):# coloca recursivamente la próxima reina
Devolver verdadero
tablero [fila] [col] =0 # backtrack:retire la reina si no conduce a una solución
devolver falso # No se encontró solución para esta fila
Def solve_n_queens ()::
"" "Resuelve el problema de N-Queens para n =4". ""
tablero =[[0 para _ en el rango (4)] para _ en el rango (4)] # Inicializar una placa vacía
Si no solve_n_queens_util (tablero, 0):
Imprimir ("La solución no existe")
devolver
# Imprima la solución
Para la fila en el tablero:
Imprimir (fila)
solve_n_queens ()
`` `` ``
Explicación del código:
1. `is_safe (tablero, fila, col)`: Comprueba si es seguro colocar a una reina en `tablero [fila] [col]`. Verifica los conflictos en la misma columna y diagonales.
2. `solve_n_queens_util (tablero, fila)`:
* Caso base: `Si fila ==4:` Si hemos llegado a la última fila (todas las reinas colocadas), tenemos una solución, así que devuelva 'verdadero'.
* iteración: Entren a través de cada columna en la fila actual (`para col en el rango (4)`).
* Verifique la seguridad: `if is_safe (tablero, fila, col):` Si es seguro colocar una reina en esta columna:
* Coloque la reina: `tablero [fila] [col] =1`
* Llamada recursiva: `Si solve_n_queens_util (tablero, fila + 1):` Intenta recursivamente colocar a la siguiente reina en la siguiente fila. Si esta llamada recursiva devuelve `Verdad`, significa que se encontró una solución desde este punto, por lo que también devolvemos 'verdadero'.
* Backtrack: `Board [fila] [col] =0` Si la llamada recursiva devuelve` falso` (no se encontró ninguna solución), * deshacemos * la colocación de la reina (retroceso) y probamos la siguiente columna en la fila actual.
* No hay solución en esta fila: `Return False` Si hemos probado todas las columnas en la fila actual sin encontrar una solución, significa que no hay una ubicación válida de reinas, por lo que devolvemos 'falso'.
3. `solve_n_queens ()`:
* Inicializa el tablero.
* Llama a `solve_n_queens_util` para iniciar el proceso de retroceso.
* Imprime la solución si se encuentra uno.
Ventajas del retroceso:
* Búsqueda sistemática: Garantiza encontrar una solución si existe (búsqueda exhaustiva).
* poda: Evita explorar ramas innecesarias del espacio de búsqueda, lo que lo hace más eficiente que un enfoque de fuerza bruta.
* Simplicidad conceptual: La idea central es relativamente fácil de entender.
Desventajas del retroceso:
* Complejidad del tiempo: Todavía puede tener una complejidad de alto tiempo (exponencial en el peor de los casos) para grandes instancias problemáticas, ya que podría explorar muchos callejones sin salida.
* Complejidad espacial: Puede requerir una memoria significativa, especialmente para la recursión profunda.
Consideraciones clave para aplicar el retroceso:
* restricciones: Defina claramente las restricciones del problema.
* Elección de acción: Considere cuidadosamente cómo tomar decisiones en cada paso.
* Estrategia de poda: Desarrolle una estrategia de poda eficiente para eliminar a los candidatos inválidos lo antes posible. Esto es crucial para el rendimiento.
* Estructura de problemas: El retroceso funciona mejor para problemas donde las soluciones parciales se pueden evaluar fácilmente para la validez.
En resumen, el retroceso es una técnica versátil de resolución de problemas que se puede aplicar a una amplia gama de problemas. Al explorar sistemáticamente posibles soluciones y podar el espacio de búsqueda, ofrece un enfoque poderoso para encontrar soluciones que satisfagan restricciones específicas. Si bien puede tener una complejidad de alto tiempo en el peor de los casos, la satisfacción de restricción cuidadosa y la poda eficiente pueden mejorar significativamente su rendimiento.