A troca de retorno é uma técnica algorítmica geral usada para resolver problemas recursivamente, tentando construir uma solução de forma incremental, uma peça de cada vez. Se, em algum momento, o algoritmo determinar que a abordagem atual não pode levar a uma solução válida (ele atinge um "beco sem saída"), ele "retorna" - ela desfaz a última etapa ou várias etapas e tenta uma abordagem diferente. Esse processo continua até que uma solução seja encontrada ou todas as possibilidades tenham sido exploradas.
Pense nisso como explorar um labirinto:
* Você começa na entrada e tenta um caminho.
* Se você chegar a um beco sem saída, voltará ao último cruzamento e tenta um caminho diferente.
* Você continua fazendo isso até encontrar a saída (solução) ou explorar todos os caminhos.
características -chave do retrocesso: *
recursivo: Os algoritmos de retrocesso são inerentemente recursivos. Cada chamada recursiva explora um ramo diferente do espaço da solução.
*
tentativa e erro: É uma abordagem de tentativa e erro. Ele tenta várias opções e descarta aqueles que não levam a uma solução.
*
Exploração do espaço do estado: O algoritmo explora todo o espaço de estado (todas as soluções possíveis) sistematicamente, geralmente usando uma estrutura semelhante a uma árvore para representar a pesquisa.
*
poda: Um aspecto crucial é a capacidade de podar os ramos (descartados) da árvore de pesquisa mais cedo, se estiver determinado que eles não podem levar a uma solução válida. Isso melhora significativamente a eficiência.
Aplicações comuns de retrocesso: *
Encontrando todas as permutações possíveis de um conjunto: Gerando todos os arranjos possíveis de elementos.
*
Resolvendo o problema n-aqueh: Colocando N xadrez em um tabuleiro de xadrez N × N para que não haja duas rainhas.
*
Resolvendo quebra -cabeças sudoku: Preenchendo as células vazias de uma grade sudoku de acordo com as regras do jogo.
*
Gerando todos os subconjuntos de um conjunto: Encontrando todas as combinações possíveis de elementos de um conjunto.
*
Algoritmos de travessia de gráfico (por exemplo, pesquisa de profundidade primeiro): Explorando todos os caminhos em um gráfico.
*
Problemas de satisfação da restrição: Problemas onde as soluções devem satisfazer um conjunto de restrições.
Exemplo (N-Queens simplificado): Imagine colocar duas rainhas em um tabuleiro de xadrez 2x2. Um algoritmo de retrocesso seria:
1. Tente colocar a primeira rainha no canto superior esquerdo.
2. Tente colocar a segunda rainha no canto superior direito. Isso é inválido (rainhas se atacam).
3. Backtrack:Remova a segunda rainha.
4. Tente colocar a segunda rainha no canto inferior esquerdo. Isso é inválido.
5. Backtrack:Remova a segunda rainha.
6. Backtrack:Remova a primeira rainha.
7. Tente colocar a primeira rainha no canto superior direito ... e assim por diante até que uma solução (ou a falta dela) seja encontrada.
Em essência, o retorno é uma técnica poderosa, mas potencialmente computacionalmente cara, para resolver problemas em que o espaço da solução é grande e precisa ser explorado sistematicamente. A eficácia depende de quão eficiente o algoritmo pode podar o espaço de pesquisa.
