Algoritmo
El backtracking construye una solución paso a paso y deshace las decisiones que violan una restricción; resuelve permutaciones, N reinas o sudokus.
El backtracking, o vuelta atrás, construye la respuesta paso a paso recorriendo en profundidad un árbol de estados y, en cuanto las decisiones tomadas incumplen una restricción, regresa al paso anterior para probar otra opción. El código repite tres acciones: elegir un candidato, explorar de forma recursiva y deshacer la elección al volver.
A diferencia de la fuerza bruta, que genera cada candidato completo antes de comprobarlo, el backtracking poda pronto las ramas sin futuro y suele resolver el mismo problema con órdenes de magnitud menos pasos. Es la técnica habitual para enumerar permutaciones y combinaciones y para problemas de satisfacción de restricciones como las N reinas, el sudoku o la coloración de grafos, y está en la base de los motores de expresiones regulares y de los solucionadores SAT, así que aparece tanto en entrevistas técnicas como en código de producción.
Conviene empezar por enumeraciones sin poda, como subconjuntos y permutaciones, para dominar el patrón elegir, explorar, deshacer. Después practique la comprobación de restricciones y la poda con las N reinas y el sudoku. Por último, cuente los nodos visitados para medir el efecto de la poda y compare los mismos problemas con la programación dinámica.
Con el estado vacío como raíz y cada decisión como arista, cada candidato es un camino y el backtracking recorre ese árbol en profundidad.
Se añade un candidato a la solución parcial, se baja recursivamente y se retira al volver, de modo que todas las ramas comparten una sola lista.
Si una solución parcial ya no puede llevar a una respuesta, se salta todo el subárbol, lo que reduce en la práctica un espacio de búsqueda exponencial.
Guardar en conjuntos o arreglos las columnas, diagonales, filas o cajas ocupadas permite saber en tiempo constante si una elección rompe una regla.
permutations bloquea con un arreglo used los elementos ya elegidos y genera todas las permutaciones con el patrón elegir, explorar, deshacer, guardando cada camino completo como copia con path[:]. n_queens lleva en conjuntos las columnas y las dos diagonales (row - c, row + c), salta al instante las casillas atacadas y cuenta las soluciones. Al ejecutar python backtracking.py se imprimen las 6 permutaciones de [1, 2, 3] y 92, el número de soluciones de las 8 reinas.
backtracking.py
def permutations(items):
result, path = [], []
used = [False] * len(items)
def backtrack():
if len(path) == len(items):
result.append(path[:]) # store a copy of the full path
return
for i, x in enumerate(items):
if used[i]:
continue
used[i] = True # choose
path.append(x)
backtrack() # explore
path.pop() # unchoose
used[i] = False
backtrack()
return result
def n_queens(n):
cols, diag, anti = set(), set(), set()
def place(row):
if row == n:
return 1
count = 0
for c in range(n):
if c in cols or row - c in diag or row + c in anti:
continue # prune: square is attacked
cols.add(c); diag.add(row - c); anti.add(row + c)
count += place(row + 1)
cols.remove(c); diag.remove(row - c); anti.remove(row + c)
return count
return place(0)
print(permutations([1, 2, 3]))
print(n_queens(8)) # 92
python backtracking.pySeis capítulos que te llevan desde la instalación hasta las ideas clave de Backtracking (vuelta atrás).
Haz preguntas, comparte tu experiencia e intercambia opiniones sobre Backtracking (vuelta atrás).
Todavía no hay debates. Empieza el primero.
0 comentarios
Iniciar sesión · Inicia sesión para dejar un comentario.