Backtracking é um algoritmo genérico que busca, por força bruta,
soluções possíveis para problemas computacionais (tipicamente
problemas de satisfações à restrições).
- De maneira incremental, busca por candidatos à soluções e abandona
cada candidato parcial C quando C não pode resultar em uma solução
válida.
- Quando sua busca chega a uma extremidade da estrutura de dados,
como um nó terminal de uma árvore, o algoritmo realiza um retrocesso
tipicamente implementado através de uma recursão.
Exemplo de Algoritmo
bool acabou = FALSE;
backtrack(int a[], int k, int n) {
int c[MAXCANDIDATOS]; /* Candidatos para a próxima posição */
int ncandidatos; /* Número de candidatos para a próxima posição */
int i; /* Contador */
if (e_uma_solucao(a, k, n)) {
processar_solucao(a, k, n);
} else {
k = k + 1;
construir_candidatos(a, k, n, c, &ncandidatos);
for (i=0; i<ncandidatos; i++) {
a[k] = c[i];
backtrack(a, k, n);
if (acabou) return;
}
}
}
Características Básicas:
- Para cada chamada recursiva existem diversas opções que podem ser seguidas. Ex.: Muitos vértices
podem ser o próximo.
- Diversos dados do subconjunto de dados de entrada ainda não incluídos na solução são candidatos.
Pode ser que todos sejam e pode existir uma restrição (constraint) reduzindo o número de
candidatos. Ex.: Só vértices vizinhos são candidatos a serem o próximo.
- O algoritmo pode tentar uma chamada recursiva para cada um dos candidatos (solução para
pesquisa exaustiva). Ex.: O Caixeiro Viajante tenta todos os caminhos.
- O algoritmo pode escolher um ou poucos dados segundo um critério qualquer.
- O processo de busca cria uma árvore de chamadas recursivas. Ex.: Todos os caminhos parciais do
caixeiro viajante.
- Folhas dessa árvore são de dois tipos:
- Representam uma possível solução para o problema.
- Representam um ponto onde o algoritmo não pôde mais ir adiante (failure) sem ferir alguma
pré-condição para que a solução gerada até então seja válida. Ex.: Caminho encontrado até
agora é muito longo, embora ainda existam vértices por percorrer.
Pontos Positivos:
- Forma bastante fácil de implementar um problema que de outra forma seria muito mais complexo de
se resolver.
- Linguagens da Área de Programação em Lógica (PROLOG, KL-ONE, OPS5) geralmente trazem algum mecanismo embutido que dá suporte ao backtracking.
Pontos Negativos:
- Programas de backtracking, a não ser que se programe restrições (constraints) executam sempre
uma busca exaustiva e tenderão à explosão combinatória.
- Programas de Backtracking são por natureza, Combinatórios !
- Necessitam de muita memória no Stack, já que a quantidade de variáveis locais transportada por
cada chamada recursiva é diretamente proporcional ao tamanho do problema.
- Isto significa que a quantidade de memória requerida para um programa de backtracking pode
crescer exponencialmente com o tamanho do problema.
Onde é aplicável:
Backtracking é aplicável na solução de vários problemas conhecidos, dentre os quais podem-se destacar:
- Caixeiro Viajante
- Passeio do Cavalo
- N-Rainhas
- Encontrar Espaço de Soluções
- Exame de Graham
- Geração de Permutações
- Problemas de labirinto
OBS: Deve-se ficar atento a explosão combinatória.
Fonte: Backtracking