Algoritmos de Backtracking

Prévia do material em texto

Análise de Algoritmos
BACKTRACKINGBACKTRACKING
Bacharelado em Ciência da Computação
Flávia Coelho
flaviacoelho@ufersa.edu.br
Atualizado em Abril de 2016
 
Sumário
● Introdução
● Exemplo de Utilização
● Elementos Fundamentais
● Leitura Recomendada
 
Problema do Labirinto
 
Problema do Labirinto
 
Jogo da Troca de Bolas
● n bolas vermelhas e n bolas pretas
● Tabuleiro (uma linha) com 2n + 1 posições
● Bolas com a mesma cor em extremidades diferentes, e um 
espaço vazio separando o conjunto de bolas diferentes
● Movimentos possíveis
● Bola vermelha para a esquerda e preta para a direita
● Mover um espaço, se o espaço está vazio
● Pular sobre exatamente uma bola de cor diferente, se o espaço 
logo após a bola estiver vazio 
 
Jogo da Troca de Bolas
 
O que é Comum ao Labirinto e ao 
Jogo da Troca de Bolas?
● Tomar uma decisão conduz a um novo 
conjunto de decisões
● Alguma(s) sequência(s) de decisões 
pode(m) conduzir à solução do problema
● São problemas de otimização ou 
localização que admitem o conceito de 
”solução candidata parcial” e um teste que 
verifica se a candidata pode fazer parte de 
uma solução válida
 
Como Resolver tais Problemas?
● Fazer uma lista com todos os candidatos 
possíveis
● Examinar todas as respostas ou algumas 
delas
● Retornar a solução
Atenção: Se a lista de candidatos for 
muito grande, uma busca exaustiva 
(força bruta) não será eficiente!!!
 
Backtracking
● Estratégia para 
construir 
sistematicamente a lista 
de possíveis soluções, 
eliminando 
explicitamente a 
verificação de uma boa 
parte de possíveis 
candidatos
● Usa uma árvore 
implícita de soluções
 
Fundamentos
● Aplicamos testes (com base 
em restrições) para avaliar se 
determinada escolha 
(candidato) pode levar a uma 
solução válida
● Se tal escolha não conduz a 
uma solução válida, as opções 
que a incluem são ignoradas
CANDIDATOS RESTRIÇÕES SOLUÇÃO
 
Sumário
● Introdução
● Exemplo de Utilização
● Elementos Fundamentais
● Leitura Recomendada
 
Satisfatibilidade (SAT)
● Problema de relevância prática para testes de chip, 
projeto de computadores e análise de imagens, por 
exemplo
● Dada uma fórmula booleana na forma normal conjuntiva, encontre 
uma atribuição satisfatória ou então declare que nenhuma existe
● FNC (Forma Normal Conjuntiva)
● Conjunção de cláusulas, onde uma cláusula é uma 
disjunção de literais
● Exemplos
– A ^ B
– ~A ^ (B ˅ C)
– A ^ B  ˅ (D ^ E) não está na FNC
 
Satisfatibilidade (SAT)
Exemplo de Instância
● Uma atribuição satisfatória é uma atribuição de 
falso ou verdadeiro a cada variável de modo 
que cada cláusula contenha um literal cujo 
valor seja verdadeiro
x∨y∨z x∨y y∨z  z∨ x x∨y∨z 
 
SAT
Entendendo a Instância
x∨y∨z x∨y y∨z  z∨ x x∨y∨z 
Tornar todas as variáveis verdadeiro satisfaz todas as 
cláusulas, exceto a última!
Tornar todas as variáveis verdadeiro satisfaz todas as 
cláusulas, exceto a última!
verdadeiro falso
● Será que existe alguma atribuição que satisfaça todas 
as cláusulas?
● No exemplo, não há nenhuma! Afinal, as três cláusulas do meio 
restringem as 3 variáveis a ter o mesmo valor
 
Sobre o SAT, portanto...
● Podemos decidir por buscar todas as 
atribuições possíveis, uma por uma
● Para fórmulas com n variáveis, o número de 
atribuições possíveis é exponencial (2n)
● É um problema de localização 
(combinacional)
 
Algoritmo SAT
Comece com algum problema P0
Seja S = {P0}, o conjunto de subproblemas ativos
Repita enquanto S é não vazio
 Escolher um subproblema P ∈ S e removê-lo de S
 Expandir P em subproblemas menores P1, P2, …, Pk
 Para cada Pi
 Se teste(Pi) tem sucesso: pare e anuncie esta solução
 Se teste(Pi) falha: descarte Pi
 Caso contrário: adicione Pi a S
Anuncie que não existe nenhuma solução
 
Algoritmo SAT
Comece com algum problema P0
Seja S = {P0}, o conjunto de subproblemas ativos
Repita enquanto S é não vazio
 Escolher um subproblema P ∈ S e removê-lo de S
 Expandir P em subproblemas menores P1, P2, …, Pk
 Para cada Pi
 Se teste(Pi) tem sucesso: pare e anuncie esta solução
 Se teste(Pi) falha: descarte Pi
 Caso contrário: adicione Pi a S
Anuncie que não existe nenhuma solução
Seleciona uma cláusula
 
Algoritmo SAT
Comece com algum problema P0
Seja S = {P0}, o conjunto de subproblemas ativos
Repita enquanto S é não vazio
 Escolher um subproblema P ∈ S e removê-lo de S
 Expandir P em subproblemas menores P1, P2, …, Pk
 Para cada Pi
 Se teste(Pi) tem sucesso: pare e anuncie esta solução
 Se teste(Pi) falha: descarte Pi
 Caso contrário: adicione Pi a S
Anuncie que não existe nenhuma solução
Seleciona uma variável dentro da 
cláusula escolhida
 
Exemplo
● Vamos manter uma árvore de soluções parciais (iniciando por 
w)
● Nenhuma cláusula é imediatamente violada e, assim, 
nenhuma dessas atribuições parciais pode ser eliminada, no 
momento
● Precisamos continuar ramificando
w∨x∨y∨zw∨x x∨y y∨z  z∨ww∨z 
w = 0 w = 1
 
Exemplo
● Atribuição parcial w = 0, x = 1
w = 0 w = 1w = 0 w = 1
x = 0 x = 1
w∨x∨y∨zw∨x x∨y y∨z  z∨ww∨z 
cláusula 
violada
 
Exemplo
● Neste ponto, fazemos backtracking e continuamos 
nossas explorações em um dos 2 nós ativos restantes
● Dessa forma, o backtracking explora o espaço de 
atribuições, crescendo a árvore (implícita) de busca 
apenas nos nós onde existe incerteza sobre o 
resultado e parando se, em qualquer estágio, uma 
atribuição satisfatória for encontrada
● Os nós da árvore de busca, representando 
atribuições parciais, são eles próprios, problemas 
SAT
 
Exemplo
● Na árvore, uma cláusula vazia descarta 
satisfatibilidade
● Vejamos o passo­a­passo
w = 0 w = 1w = 0 w = 1
x = 0 x = 1
x∨y∨z x x∨y y∨ z
w∨x∨y∨zw∨x x∨y y∨z  z∨ww∨z 
Para w = 0, x = 0, 
qualquer cláusula com 
w ou x é satisfeita, 
diretamente! E qualquer 
literal w ou x não é 
satisfeito e pode ser 
removido
 
Exemplo
descarta a
satisfatibilidade
w = 0 w = 1w = 0 w = 1
x = 0 x = 1
x∨y∨z x x∨y y∨ z
w∨x∨y∨zw∨x x∨y y∨z  z∨ww∨z 
 y∨z 
A cláusula vazia () 
indica descarte!
 
Exemplo
w = 0 w = 1w = 0 w = 1
x = 0 x = 1
x∨y∨z x x∨y y∨ z
w∨x∨y∨zw∨x x∨y y∨z  z∨ww∨z 
 y∨z 
fazemos 
backtracking
 
Exemplo
w = 0 w = 1w = 0 w = 1
x = 0 x = 1
x∨y∨z x x∨y y∨ z
w∨x∨y∨zw∨x x∨y y∨z  z∨ww∨z 
 y∨z 
y = 0 y = 1
y∨z y y∨z 
 
Exemplo
w = 0 w = 1w = 0 w = 1
x = 0 x = 1
x∨y∨z x x∨y y∨ z
w∨x∨y∨zw∨x x∨y y∨z  z∨ww∨z 
 y∨z 
y = 0 y = 1
y∨z y y∨z 
  descarta a
satisfatibilidade
 
Exemplo
w = 0 w = 1w = 0 w = 1
x = 0 x = 1
x∨y∨z x x∨y y∨ z
w∨x∨y∨zw∨x x∨y y∨z  z∨ww∨z 
 y∨z 
y = 0 y = 1
y∨z y y∨z 
 
z = 0 z = 1
 z  z 
 
Exemplo
descarta a
satisfatibilidade
w = 0 w = 1w = 0 w = 1
x = 0 x = 1
x∨y∨z x x∨y y∨ z
w∨x∨y∨zw∨x x∨y y∨z  z∨ww∨z 
 y∨z 
y = 0 y = 1
y∨z y y∨z 
 
z = 0 z = 1
 z  z 
 
 
Exemplo
descarta a
satisfatibilidade
w = 0 w = 1w = 0 w = 1
x = 0 x = 1
x∨y∨z x x∨y y∨ z
w∨x∨y∨zw∨x x∨y y∨z  z∨ww∨z 
 y∨z 
y = 0 y = 1
y∨z y y∨z 
 
z = 0 z = 1
 z  z 
  
 
Exemplow = 0w = 0 w = 1
x = 0 x = 1
x∨y∨z x x∨y y∨ z
w∨x∨y∨zw∨x x∨y y∨z  z∨ww∨z 
 y∨z 
y = 0 y = 1
y∨z y y∨z 
 
z = 0 z = 1
 z  z 
  
z = 0 z = 1
x∨y y∨z  z  z
 
Exemplo
descarta a
satisfatibilidade
w = 0w = 0 w = 1
x = 0 x = 1
x∨y∨z x x∨y y∨ z
w∨x∨y∨zw∨x x∨y y∨z  z∨ww∨z 
 y∨z 
y = 0 y = 1
y∨z y y∨z 
 
z = 0 z = 1
 z  z 
  
z = 0 z = 1
x∨y  y∨z  z  z
x∨y y 
 
Exemplo
descarta a
satisfatibilidade
w = 0w = 0 w = 1
x = 0 x = 1
x∨y∨z x x∨y y∨ z
w∨x∨y∨zw∨x x∨y y∨z  z∨ww∨z 
 y∨z 
y = 0 y = 1
y∨z y y∨z 
 
z = 0 z = 1
 z  z 
  
z = 0 z = 1
x∨y y∨z  z  z
x∨y y x∨y 
 
Sumário
● Introdução
● Exemplo de Utilização
● Elementos Fundamentais
● Leitura Recomendada
 
Elementos Fundamentais
● Escolha de subproblemas a expandir
● Determinação de qual item (variável) usar na 
ramificação
● No exemplo SAT...
● Backtracking elimina porções do espaço de busca
– Escolhe­se o subproblema que contenha a menor 
cláusula
– Ramifica­se sobre uma variável naquela cláusula
 
Exemplo
w = 0w = 0 w = 1
x = 0 x = 1
x∨y∨z x x∨y y∨ z
w∨x∨y∨zw∨x x∨y y∨z  z∨ww∨z 
 y∨z 
y = 0 y = 1
y∨z y y∨z 
 
z = 0 z = 1
 z  z 
  
z = 0 z = 1
x∨y y∨z  z  z
x∨y  y x∨y 
 
Concluindo...
● Um algoritmo de backtracking requer um 
teste que verifique um subproblema e 
rapidamente declare um dos 3 resultados
● Falha: o subproblema não tem solução
● Sucesso: uma solução para o subproblema foi 
encontrada
● Incerteza
● Para o SAT, o teste declara falha se existir 
uma cláusula vazia, sucesso se não há 
nenhuma cláusula, e incerteza caso contrário
 
Concluindo...
● Caso não sejam determinadas restrições de 
modo correto, o backtracking sempre executará 
uma busca exaustiva, com tendência à 
explosão combinatória
● Necessita de bastante memória na pilha, dada 
a quantidade de variáveis locais transportadas 
por cada chamada recursiva ser diretamente 
proporcional ao tamanho do problema
● A quantidade de memória requerida pode crescer 
exponencialmente com o tamanho do problema
 
Algoritmo Backtracking Genérico
backtrack(v){
  //v é o nó sendo pesquisado
  se v é promissor então{
    se v é solução então escreva v
    para cada filho f em v faça
      backtrack(f)
  }
}
 
Algoritmo SAT com Backtracking
Comece com algum problema P0
Seja S = {P0}, o conjunto de subproblemas ativos
Repita enquanto S é não vazio
 Escolher um subproblema P ∈ S e removê-lo de S
 Expandir P em subproblemas menores P1, P2, …, Pk
 Para cada Pi
 se teste(Pi) tem sucesso: pare e anuncie esta solução
 se teste(Pi) falha: descarte Pi
 caso contrário: adicione Pi a S
Anuncie que não existe nenhuma solução
 
Aplicabilidade do Backtracking
● Caixeiro viajante
● Mochila binária
● Passeio do cavalo no tabulaleiro de 
xadrez
● Soma de subconjuntos
 
Referências
Material didático elaborado por Jorge Cesar 
Abrantes de Figueiredo, UFCG 
(Universidade Federal de Campina 
Grande)
 
Leitura Recomendada
S. Dasguta, C. Papadimitriou, U. Vazirani. 
Algoritmos. Mc­Graw Hill, 2009, pp. 232­
235, 272­275
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42