O algoritmo de retrocesso explora com eficiência um espaço de pesquisa tentando sistematicamente diferentes combinações e abandonando os caminhos que garantem a não levar a uma solução. Funciona sobre o princípio da * Pesquisa de profundidade * com uma adição crucial: podando .

Aqui está um colapso de como funciona:

1. Representação do espaço do estado: O problema é representado como uma árvore ou gráfico onde cada nó representa uma solução parcial. O nó raiz representa o estado inicial e as ramificações representam escolhas ou decisões tomadas em cada etapa. As folhas representam soluções completas ou becos sem saída.

2. Exploração recursiva (pesquisa de profundidade primeiro): O algoritmo começa no nó raiz e explora uma ramificação de cada vez, indo o mais profundo possível (profundidade primeiro). Isso significa que faz uma série de opções até encontrar uma solução ou atingir um beco sem saída.

3. Verificação/promessa de restrição: Em cada nó, uma verificação é executada para verificar se a solução parcial atual ainda é "promissora" - o que significa que é possível estendê -lo a uma solução completa. É aqui que a eficiência entra. Se a solução parcial atual violar as restrições do problema (por exemplo, em um quebra -cabeça Sudoku, colocando um número que já está na linha, coluna ou bloco 3x3), o algoritmo sabe que não precisa explorar esse ramo mais. Esta é a poda etapa.

4. retrocesso: Se um nó for considerado não promissor, ou se um nó foliar representar uma tentativa fracassada de encontrar uma solução, o algoritmo "backtracks" para o nó anterior (seu pai) e tenta um ramo diferente (uma opção diferente). Isso envolve desfazer as escolhas feitas ao longo desse ramo e explorar possibilidades alternativas.

5. Solução encontrada: Quando um nó foliar representa uma solução completa e válida, o algoritmo encontrou uma solução e pode parar (se encontrar uma solução for suficiente) ou continue a procurar outras soluções, voltando e explorando outras filiais.


Exemplo:N-Queens Problem

Vamos considerar colocar n xadrez em um tabuleiro de xadrez n × n, de modo que não há duas rainhas se ameaçam.

* Espaço de estado: Cada nó na árvore representa uma colocação parcial de rainhas na placa.
* Escolha: Em cada nível da árvore, é feita uma escolha sobre onde colocar a próxima rainha na coluna.
* restrição: A restrição é que não há duas rainhas na mesma linha, coluna ou diagonal.
* poda: Se colocar uma rainha viola a restrição, esse ramo é podado. O algoritmo não explora mais essa filial.
* backtracking: Se um posicionamento levar a uma violação, o algoritmo retorna à coluna anterior, remove a rainha e tenta uma posição diferente nessa coluna.

em resumo: A eficiência do backtracking deriva de sua capacidade de evitar explorar partes desnecessárias do espaço de pesquisa, com galhos de poda de forma inteligente que garantem que não levem a uma solução. Isso reduz significativamente o tempo de computação em comparação com os métodos de pesquisa exaustiva que tentariam todas as combinações. A eficácia depende de quão bem a verificação "promissora" foi projetada para identificar e eliminar caminhos não viáveis ​​no início da pesquisa.