Estruturas de Dados - Backtracking (Dibio)

Prévia do material em texto

dibio@unb.br
“Backtracking” (Acompanhamento 
 Reverso): Forma Geral e 
Exemplos
dibio@unb.br
● “Backtracking” é uma forma de recursão
– Usualmente há um número de opções para decidir qual 
tomar, após esta seguem-se outras e se houver a 
necessidade de retroceder em alguma delas há a 
necessidade de manter a história dessas escolhas.
– Conceitualmente seria como iniciasse na raiz de uma 
árvore, vários caminhos levam a diferentes nós folhas. 
A cada nó o processo de escolha se repete.
dibio@unb.br
Seja o exemplo
● Iniciando na Raiz, há opções A e 
B, seja escolha A;
● Em A as opções são C e D, seja 
escolha C;
● C é ruim, retornar até A;
● Em A, C já foi testado, então ir 
para D;
● D é ruim, retornar até A;
● Em A todas opções já testadas, 
então retornar a Raiz;
● Na Raiz então seguir B;
● processo repete-se até...
● E (Final!)
dibio@unb.br
Qual seria o pseudo-código desse 
algoritmo?
● Em um dado nodo n
boolean resolver(nodo n) {
if n eh nodo folha {
if folha eh “bom”, então retornar TRUE
caso contrário retornar FALSE 
} caso contrário {
 para cada filho f do nodo n {
 if resolver (f) TRUE, retornar TRUE
}
retornar FALSE;
}
dibio@unb.br
● A função resolver() é booleana pois se resolver(n) 
for TRUE o nodo n é parte da solução. Se 
resolver(n) for FALSE esse nodo não será parte do 
caminho da solução;
● Como isso funciona?
– Se filho de n for TRUE, n será TRUE;
– Se nenhum filho de n for TRUE, n será FALSE;
– Logo, recursivamente devemos testar os filhos de n:
 para cada filho f do nodo n {
 if resolver (f) TRUE, retornar TRUE
}
retornar FALSE;
dibio@unb.br
● Outra maneira de colocar o algoritmo seria:
 Para pesquisar/buscar uma árvore:
 If a árvore consistir de um único nodo folha, 
 testar se esse nodo for “bom”
 caso contrário, pesquisar as sub-árvores até
 atingir um nodo folha “bom”, ou
 até terminar todos os nodos
dibio@unb.br
Backtracking é tipicamente um 
algoritmo recursivo
● E qualquer algor. recursivo pode ser reescrito com auxílio de uma pilha
boolean resolver (nodo n) {
colocar nodo n na pilha;
while pilha não estiver vazia fazer{
 if o nodo no topo da pilha for folha{
 if folha for “bom”, retornar TRUE
 else remover folha da pilha
}
else {
 if o nodo no topo da pilha tiver filhos não testados
 empilhar próximo nodo filho não testado na pilha
 else remover o nodo da pilha
}
 retornar FALSE
} 
dibio@unb.br
E no caso do “boggle”?
dibio@unb.br
Pseudo-código (um possível)
● Iniciar de um nodo (posição)
– Prosseguir em frente (posições de movimento) até não 
ser possível aquele caminho;
– Onde não for possível prosseguir, retornar ao anterior e 
examinar opções não visitadas;
– Usar uma pilha para acompanhar a história do caminho:
● Inserir na pilha, avançar
● Remover da pilha, “backtrack”
Usar variável de posição para saber local atual e opções: 
(pilha)
● Avançar → inserir na pilha próxima direção
● “Backtrack” → remover a direção
– Usar marcadores (e.g. 0, -1) indicando locais visitados e 
não visitados 
dibio@unb.br
Outros problemas típicos para uso 
de “backtracking”
● Labirinto
● Coloração de 
Mapas(4 cores, sem 
usar cores iguais em 
áreas adjacentes)
● Jogos (Jogo da Velha, 
8 rainhas, resta um, 
damas, caça-palavras, 
xadrez, etc)
dibio@unb.br
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11