Backtracking¶

Backtracking explora uma árvore de decisões e abandona uma solução parcial assim que ela não pode levar a uma solução válida.

search(state):
    if state is a complete solution: report it
    for each candidate decision:
        if decision is consistent with state:
            apply decision
            search(state)
            undo decision

Estrutura da correção¶

Toda folha relatada satisfaz as restrições (correção).
Toda solução válida corresponde a algum ramo que nunca é podado incorretamente (completude).
A árvore de busca finita e o progresso em cada chamada recursiva implicam a terminação.

Problema das n rainhas¶

Posicione uma rainha por linha. Registre as colunas e diagonais ocupadas para rejeitar um posicionamento inválido em tempo constante. A poda reduz substancialmente o trabalho, mas a busca permanece exponencial no pior caso. A complexidade do backtracking é descrita melhor pelo fator de ramificação e pela profundidade máxima, com limites mais justos quando o problema os permite.

Decisões de engenharia¶

Escolha primeiro a variável mais restrita, ordene candidatos promissores antes dos demais e atualize incrementalmente o estado das restrições. Essas heurísticas alteram o trabalho explorado, não o conjunto de soluções válidas.

Exercícios¶

Gere todos os subconjuntos e explique por que o tamanho da saída é Θ(2ⁿ).
Resolva uma pequena instância de coloração de grafos com poda.
Diferencie backtracking de programação dinâmica.