estratégia / tentativa e poda
próxima lente Retrocesso (Backtracking).
Avançar, testar a restrição e desfazer cedo quando o caminho não pode funcionar.
visualização passo a passo
stage / RetrocessoEsta escolha ainda pode fazer parte de uma solução válida?
101
002
003
004
005
006
foco atual / escolher um ramoa faixa mostra o estado, não uma medição de tempo real
ação / progresso comparação / estado conflito / limite
telemetria / estratégia
passo01escolher um ramo
profundidade1estado observado
códigolinha 3JavaScript
estadopausadocontrole manual
/ o que está acontecendoescolher um ramo
escolher um ramo
saiba quando voltar.
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.
complexidade / mapa rápido
melhorO(d)
médioO(bᵈ)
piorO(bᵈ)
b é o número médio de escolhas por nível e d é a profundidade máxima da árvore de busca.
/ por baixo do palco
Um retorno, um caminho.
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.
01se solução completa: retornar sucesso
02para escolha possível:
03 aplicar escolha
04 se estado válido: continuar
05 desfazer escolha
06retornar falha
implementação / JavaScript
01function search(state) {02 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}