Backtracking: Técnica de Solução de Algoritmos

Prévia do material em texto

Backtracking
Melina Mongiovi
melina@computacao.ufcg.edu.br
mailto:melina@computacao.ufcg.edu.br
Backtracking
É uma técnica de solução de construção de 
algoritmos que examina o espaço de soluções 
de forma exaustiva, mas abandonando famílias de 
caminhos tão logo alguma inviabilidade seja 
determinada (exaustão inteligente). 
 Quando um caminho é inviável, VOLTAR para 
 caminhos promissores!!!
Exemplo: Geração de Permutação
Problema: gerar todas as permutações de 
um conjunto de inteiros 
Ex: A = {1,2,3}
Permutações = {(1,2,3), (1,3,2), (2,1,3), (2,3,1), 
(3,1,2), (3,2,1)}
Usando força bruta…
Gerar todas as combinações possíveis de 
um conjunto A com elementos 
Representando a solução: 
 um array X[0..n-1] 
Critério da solução final: 
X contém n elementos
Permutações = {(1,2,3), (1,3,2), (2,1,3), (2,3,1), 
(3,1,2), (3,2,1)}
*,*,*A = {1,2,3}
1,*,*
1,1,*
1,1,1 1,1,2 1,1,3
1,2,*
1,2,1 1,2,2 1,2,3
1,3,*
1,3,1 1,3,2 1,3,3
2,*,*
2,1,*
2,1,1 2,1,2 2,1,3
2,2,*
Gera todas as combinações possíveis
permFB(X[0..n-1], A[0..n-1], i)
if i == n
print(X)
else 
for j=0 to n-1
X[i] = A[j]
permFB(X,A,i+1)
//primeira chamada i = 0 A = {1,2,3} 
Gera todas as combinações possíveis 
e checa se cada uma é valida
permFB(X[0..n-1], A[0..n-1], i)
if i == n-1
if isValid(X)
print(X)
else 
for j=0 to n-1
X[i] = A[j]
permFB(X,A,i+1)
// não tem elemento repetido
//primeira chamada i = 0
Ainda assim é custoso gerar 
todas as combinações possíveis…
Como gerar apenas as combinações válidas?
Podemos podar…
perm(X[0..n-1], A[0..n-1], i)
if i == n
print(X)
else 
for j=0 to n-1
 if isValid(X, A[j])
 X[i] = A[j]
 perm(X,A,i+1)
Backtracking
๏ Soluções construídas um componente por vez 
๏ Cada solução parcial é avaliada como promissora ou 
não 
๏ Se solução parcial é promissora, selecionamos como 
próximo candidato 
๏ Senão, algoritmo retrocede (backtracking), e substitui 
componente atual pela próxima opção
Algoritmo genérico backtracking
Árvore do espaço de soluções
A raiz corresponde ao estado inicial 
Um nó interno corresponde a uma solução parcial 
Um nó folha corresponde a uma solução parcial 
não promissora ou solução final 
A busca é feita em profundidade (DFS)
Estrutura geral
Defina a representação da solução 
Normalmente um array 
Estabeleça os conjuntos a1, …, an e a ordem 
em que seus elementos são processados 
Estabeleça as condições que tornam a solução 
parcial válida 
Estabeleça um critério para a solução final
Custo backtracking
No pior caso, gera todos os candidatos 
- Mesmo que força bruta! 
A melhora depende da capacidade de poda de 
soluções não promissoras 
Muito difícil analisar assintoticamente 
- Desempenho experimental em geral é bom