LogRitmo navegador / ativofase / 03LR / fase 03 · ativaAvançar, testar a restrição e desfazer cedo quando o caminho não pode funcionar.
A busca começa com uma possibilidade. Ainda não sabemos se ela levará à resposta, então registramos o ponto de decisão.
princípio /
Explorar sistematicamente, abandonar estados inválidos e retornar ao ponto de decisão anterior.
limite que não pode ser omitido
A poda evita ramos inúteis, mas não transforma automaticamente um espaço exponencial em polinomial. O tamanho da busca continua sendo parte da resposta.
b é o número médio de escolhas por nível e d é a profundidade máxima da árvore de busca.
b é a quantidade média de escolhas por nível e d é a profundidade da busca. Cada nível pode abrir novos ramos para explorar.
A poda descarta ramos inválidos, mas o pior caso continua crescendo muito rápido quando há muitas escolhas e níveis.Escolha duas técnicas diferentes. As curvas usam a mesma escala visual para explicar como o custo tende a aumentar.
Use este par para contrastar uma escolha local eficiente com o custo de preencher e reutilizar estados em problemas de capacidade. Greedy Algorithm e Dynamic Programming usam parâmetros diferentes: O(n·C) depende da capacidade C, e O(bᵈ) depende da ramificação b e da profundidade d. A régua contrasta modelos de crescimento; só compare a inclinação sob hipóteses explícitas sobre como esses parâmetros aumentam.
O destaque acompanha a decisão atual. Leia o pseudocódigo antes de trocar de linguagem; a implementação é uma tradução, não um novo algoritmo.
01function search(state) { // Explore valid choices and undo failed branches02 if (isComplete(state)) return state;03 for (const choice of choices(state)) {04 apply(state, choice);05 if (isValid(state)) {06 const result = search(state);07 if (result) return result;08 }09 undo(state, choice);10 }11 return null;12}Backtracking faz uma busca em profundidade numa árvore implícita de soluções parciais. Em cada nó, escolhe uma decisão ainda livre, testa candidatos, avança apenas quando as restrições continuam consistentes e desfaz exatamente a alteração antes de tentar a próxima alternativa.
Os filhos representam valores candidatos para a próxima decisão: uma coluna para uma rainha, uma cor para um vértice ou um valor para uma célula. A ordem de exploração muda o trabalho observado, não o conjunto de soluções que uma busca completa pode alcançar.
Uma poda por inviabilidade interrompe um ramo quando uma restrição já foi violada. Ela é segura apenas se nenhuma continuação daquele estado puder reparar a violação; por isso, conflito local, domínios e condições da poda precisam ser explícitos.
apply e undo formam uma unidade.Ao retornar, marcas, contadores, domínios e escolhas devem voltar exatamente ao estado anterior. Um desfazer incompleto pode omitir soluções, aceitar candidatas inválidas ou criar uma poda que parece eficiente, mas não é correta.
Na visualização, uma tentativa cria um novo nível de decisão; uma rejeição representa uma poda; e “desfazer” retira a última escolha antes de explorar o irmão. A bancada mostra a ordem de busca, não um certificado automático de que toda poda é segura.
Sem poda, se cada uma de n decisões tiver no máximo b candidatos, a árvore pode crescer exponencialmente. O custo real depende da instância, do fator de ramificação efetivo, da profundidade e do custo para testar ou propagar cada restrição.
MRV escolhe primeiro a variável com menos valores possíveis; ordenar valores pode expor conflitos antes; forward checking atualiza domínios após cada decisão. Essas técnicas frequentemente reduzem ramos visitados, mas não substituem o argumento de que a poda não descarta uma solução viável.
A prova costuma manter dois fatos. Primeiro, a pilha representa sempre uma atribuição parcial consistente. Segundo, cada poda elimina somente extensões incapazes de satisfazer o objetivo. Se a busca termina em profundidade finita, explora os candidatos não podados e desfaz cada escolha corretamente, então encontra todas as soluções viáveis desejadas — ou certifica que nenhuma foi alcançada.
Backtracking é apropriado para N-Queens, Sudoku, coloração de grafos, permutações e problemas de satisfação de restrições. Documente a decisão, a condição de consistência, o estado a desfazer e o que a poda prova. Para otimização, diferencie-o de Branch and Bound; para subproblemas repetidos, avalie Dynamic Programming; para uma escolha local segura demonstrável, considere Greedy.