Algoritmo
Backtracking constrói uma solução passo a passo e desfaz escolhas que violam uma restrição, resolvendo permutações, N rainhas e sudoku.
Backtracking monta a resposta um passo de cada vez, percorrendo em profundidade uma árvore de estados, e assim que as escolhas feitas violam uma restrição volta ao passo anterior para tentar outra opção. O código repete três ações: escolher um candidato, explorar recursivamente e desfazer a escolha na volta.
Diferente da força bruta, que gera cada candidato completo antes de verificá-lo, o backtracking corta cedo os ramos sem futuro e costuma resolver o mesmo problema com ordens de grandeza menos passos. É a abordagem padrão para listar permutações e combinações e para problemas de satisfação de restrições como N rainhas, sudoku e coloração de grafos, além de estar na base dos motores de expressões regulares e dos solucionadores SAT. Por isso aparece tanto em entrevistas técnicas quanto em código de produção.
Comece por enumerações sem poda, como subconjuntos e permutações, para fixar o padrão escolher, explorar, desfazer. Depois pratique a verificação de restrições e a poda com N rainhas e sudoku. Por fim, conte os nós visitados para ver o efeito da poda e compare os mesmos problemas com programação dinâmica.
Com o estado vazio como raiz e cada escolha como aresta, todo candidato vira um caminho, e o backtracking percorre essa árvore em profundidade.
Adiciona-se um candidato à solução parcial, desce-se recursivamente e remove-se o candidato na volta, então todos os ramos compartilham uma única lista.
Quando uma solução parcial não pode mais levar a uma resposta, a subárvore inteira é ignorada, o que reduz bastante na prática um espaço de busca exponencial.
Guardar em conjuntos ou arrays as colunas, diagonais, linhas ou caixas ocupadas permite saber em tempo constante se uma escolha quebra uma regra.
permutations bloqueia com um array used os elementos já escolhidos e gera todas as permutações pelo padrão escolher, explorar, desfazer, guardando cada caminho completo como cópia com path[:]. n_queens mantém em conjuntos as colunas e as duas diagonais (row - c, row + c), pula na hora as casas atacadas e conta as soluções. Rodar python backtracking.py imprime as 6 permutações de [1, 2, 3] e 92, o número de soluções para 8 rainhas.
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 levam você da instalação aos conceitos essenciais de Backtracking.
Tire dúvidas, compartilhe experiências e troque opiniões sobre Backtracking.
Ainda não há discussões. Comece a primeira.
0 comentários
Fazer login · Faça login para deixar um comentário.