Neste tutorial, você aprenderá o que é um algoritmo de retrocesso. Além disso, você encontrará um exemplo de abordagem de retrocesso.
Um algoritmo de retrocesso é um algoritmo de solução de problemas que usa uma abordagem de força bruta para encontrar a saída desejada.
A abordagem de força bruta tenta todas as soluções possíveis e escolhe as soluções desejadas / melhores.
O termo retrocesso sugere que, se a solução atual não for adequada, retroceda e tente outras soluções. Assim, a recursão é usada nesta abordagem.
Essa abordagem é usada para resolver problemas que possuem várias soluções. Se você deseja uma solução ideal, deve optar pela programação dinâmica.
Árvore do Espaço Estadual
Uma árvore de estado do espaço é uma árvore que representa todos os estados possíveis (solução ou não solução) do problema, desde a raiz como um estado inicial até a folha como um estado terminal.
Árvore do Espaço Estadual
Algoritmo de Backtracking
Backtrack (x) se x não for uma solução retornar false se x for uma nova solução adicionar à lista de soluções backtrack (expandir x)
Exemplo de abordagem de retrocesso
Problema: você deseja encontrar todas as maneiras possíveis de organizar 2 meninos e 1 menina em 3 bancos. Restrição: A menina não deve estar no banco do meio.
Solução: no total são 3! = 6 possibilidades. Tentaremos todas as possibilidades e obteremos as soluções possíveis. Tentamos recursivamente todas as possibilidades.
Todas as possibilidades são:
Todas as possibilidades
A seguinte árvore de espaço de estado mostra as soluções possíveis.
Árvore de estado com todas as soluções
Backtracking Algorithm Applications
- Para encontrar todos os caminhos hamiltonianos presentes em um gráfico.
- Para resolver o problema do N Queen.
- Problema de resolução de labirinto.
- O problema da turnê do Knight.
