Backtracking: Oito Rainhas

Prévia do material em texto

MC202-Estruturas de Dados
Luiz E. Buzato
Instituto de Computação – UNICAMP
buzato@ic.unicamp.br
sala 16, IC 01
2S2010
Tópico: Retrocesso (Backtracking)
Oito Rainhas
Enunciado
Posicione oito rainhas em um tabuleiro de xadrez (8 × 8) de forma
que nenhuma seja capaz de capturar qualquer outra utilizando os
movimentos posśıveis de uma rainha do jogo de xadrez.
Oito Rainhas
Enunciado
Posicione oito rainhas em um tabuleiro de xadrez (8 × 8) de forma
que nenhuma seja capaz de capturar qualquer outra utilizando os
movimentos posśıveis de uma rainha do jogo de xadrez.
O problema geral consiste em posicionar n rainhas em um tabuleiro
n× n de forma a garantir que nenhuma pode tomar qualquer outra.
Oito Rainhas
Uma configuração que resolve o problema
0Z0L0Z0Z
Z0Z0Z0L0
0ZQZ0Z0Z
Z0Z0Z0ZQ
0L0Z0Z0Z
Z0Z0L0Z0
QZ0Z0Z0Z
Z0Z0ZQZ0
Oito Rainhas
Uma configuração que resolve o problema
0Z0L0Z0Z
Z0Z0Z0L0
0ZQZ0Z0Z
Z0Z0Z0ZQ
0L0Z0Z0Z
Z0Z0L0Z0
QZ0Z0Z0Z
Z0Z0ZQZ0
Quantas existem?
Rainhas (n = 4)
4 × 4
Possibilidades: 16 posições no total, devemos escolher 4.
(
16
4
)
=
16!
4!(16 − 4)!
= 21621600
Soluções: 2 (distintas: 1).
Solução: Força Bruta
Enumeração exaustiva
É posśıvel, mas ineficiente.
Uma solução mais interessante
O que queremos?
Queremos uma função que retorne o conjunto de configurações,
digamos A, que resolve o problema.
Uma Estratégia
Busque um conjunto B de configurações que satisfaça as seguintes
propriedades:
1. A ⊂ B;
2. dado um elemento de B, não deve ser muito dif́ıcil decidir se
ele também pertence a A;
3. escrever a função que gera todos os elementos de B deve ser
simples.
A Solução Geral
Com a ajuda da função escrita no passo 3. da estratégia, enumere
os elementos de B e submeta-os, uma a um, ao critério de decisão
definido no passo 2. A execução do critério de decisão determina
quais elementos de B devem ser descartados e quais devem ser
retornados como um configuração boa, isto é, a configuração é um
elemento de A. Graças a 1. temos uma solução para o problema.
Observações importantes
1. Para que a estratégia faça sentido, B não pode ser idêntico a
A e como B deve conter A, então B deve ser maior que A.
Por razão de eficiência, entretanto, é aconselhável escolher B
tão pequeno quanto posśıvel.
2. Devemos escolher um critério de decisão que seja fácil de
aplicar. Pelo menos o fato de que um elemento de B não
pertencer a A deve ser fácil de testar.
3. No final, a estratégia é interessante, porque supõe que a
geração dos elementos de B é mais simples que a geração dos
elementos de A. É claro que se essa condição não for
verdadeira, podemos sempre pensar recursivamente!
Procura-se um conjunto C que contém B como um
subconjunto, etc.
Um otimista tenta encontrar B
Racioćınio do otimista
Listarei todas as condições mutuamente independentes que os
elementos do conjunto A devem satisfazer e suprimirei uma delas.
Usarei as que sobrarem para gerar B.
Um otimista tenta encontrar B
A pode ser caracterizado por:
1. há 8 rainhas no tabuleiro;
2. quaisquer 2 delas não podem se enfrentar;
Que Bs o otimista encontra?
B1 todas as configurações de 8 rainhas no tabuleiro tal que
quaisquer duas não podem se enfrentar.
B2 todas as configurações de 8 rainhas no tabuleiro.
Esse conjuntos são muito grandes! O otimista não obteve o
resultado que esperava.
Como encontrar B?
Uma estratégia menos otimista pede que listemos as propriedades
construtivas de uma configuração que é um elemento de B.
Construção de B
(a) Nenhuma coluna pode conter mais de uma rainha. Como
devemos posicionar 8 rainhas, sabemos que cada linha conterá
exatamente 1 rainha.
(b) Analogamente, conclúımos que cada coluna conterá
exatamente uma rainha.
(c) Há 15 diagonais para cima (ր) cada uma contendo
exatamente 1 rainha, isto é, 8 diagonais contém rainhas, uma
por diagonal, e 7 diagonais estão vazias.
Construção de B
(d) Há 15 diagonais para baixo (ց), cada uma contendo
exatamente 1 rainha.
(e) Dada qualquer configuração não vazia de rainhas tal que duas
a duas elas não podem se enfrentar, a remoção de qualquer
uma delas resultará em uma configuração com a mesma
propriedade.
A propriedade (e) é muito importante
0Z0L0Z0Z
Z0Z0Z0L0
0ZQZ0Z0Z
Z0Z0Z0ZQ
0L0Z0Z0Z
Z0Z0L0Z0
QZ0Z0Z0Z
Z0Z0ZQZ0
A propriedade (e) é muito importante
0Z0L0Z0Z
Z0Z0Z0L0
0ZQZ0Z0Z
Z0Z0Z0ZQ
0L0Z0Z0Z
Z0Z0L0Z0
QZ0Z0Z0Z
Z0Z0Z0Z0
A propriedade (e) é muito importante
0Z0L0Z0Z
Z0Z0Z0L0
0ZQZ0Z0Z
Z0Z0Z0ZQ
0L0Z0Z0Z
Z0Z0L0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
A propriedade (e) é muito importante
0Z0L0Z0Z
Z0Z0Z0L0
0ZQZ0Z0Z
Z0Z0Z0ZQ
0L0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
A propriedade (e) é muito importante
0Z0L0Z0Z
Z0Z0Z0L0
0ZQZ0Z0Z
Z0Z0Z0ZQ
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
A propriedade (e) é muito importante
0Z0L0Z0Z
Z0Z0Z0L0
0ZQZ0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
A propriedade (e) é muito importante
0Z0L0Z0Z
Z0Z0Z0L0
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
A propriedade (e) é muito importante
0Z0L0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
A propriedade (e) é muito importante
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
A propriedade (e) é muito importante
Construção de configurações em B
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
A propriedade (e) é muito importante
Construção de configurações em B
0Z0L0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
A propriedade (e) é muito importante
Construção de configurações em B
0Z0L0Z0Z
Z0Z0Z0L0
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
A propriedade (e) é muito importante
Construção de configurações em B
0Z0L0Z0Z
Z0Z0Z0L0
0ZQZ0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
A propriedade (e) é muito importante
Construção de configurações em B
0Z0L0Z0Z
Z0Z0Z0L0
0ZQZ0Z0Z
Z0Z0Z0ZQ
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
A propriedade (e) é muito importante
Construção de configurações em B
0Z0L0Z0Z
Z0Z0Z0L0
0ZQZ0Z0Z
Z0Z0Z0ZQ
0L0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
A propriedade (e) é muito importante
Construção de configurações em B
0Z0L0Z0Z
Z0Z0Z0L0
0ZQZ0Z0Z
Z0Z0Z0ZQ
0L0Z0Z0Z
Z0Z0L0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
A propriedade (e) é muito importante
Construção de configurações em B
0Z0L0Z0Z
Z0Z0Z0L0
0ZQZ0Z0Z
Z0Z0Z0ZQ
0L0Z0Z0Z
Z0Z0L0Z0
QZ0Z0Z0Z
Z0Z0Z0Z0
A propriedade (e) é muito importante
Construção de configurações em B
0Z0L0Z0Z
Z0Z0Z0L0
0ZQZ0Z0Z
Z0Z0Z0ZQ
0L0Z0Z0Z
Z0Z0L0Z0
QZ0Z0Z0Z
Z0Z0ZQZ0
B1 novamente
Haviamos rejeitado B1 porque ele era muito grande. Mas se
utilizarmos a liberdade que a propriedade (e) nos oferece de
construção incremental, adiciona-se uma rainha por vez, e
sistemática, a rainha é adicionada sempre de acordo com as regras
simples de (a) a (f), de uma configuração de B1, então o número
de configurações a ser gerado diminúı e temos uma forma simples
de gerar uma nova configuração a partir da que já temos.
De B1 para B
Em que ordem devemos gerar os elementos de B1?
Uma outra questão relacionada a esta é como descrevemos uma
configuração?
Descrição (Caracterização) de uma configuração
Numeraremos as linhas e colunas do tabuleiro de 0 a 7.
Graças à propriedade (a) podemos ordenar as rainhas de acordo
com o número da linha que ocupam. Isto induz a declaração da
seguinte estrutura:
i n t c o n f i g u r a t i o n [ 8 ] ;
configuration[i] contém o número da coluna ocupada pela
rainha da linha i .
Caractericação de configurações
Uma configuração é uma “palavra” de 8 digitos e uma ordem bem
razoável para a geração dessas “palavras” é em ordem alfabética.
Conclusão: Gera-se os elementos de B em ordem alfabética e,
conseqüentemente, os elementos de A nessa mesmaordem.
Backtracking
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
Backtracking
QZ0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
Backtracking
QZ0Z0Z0Z
Z0L0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
Backtracking
QZ0Z0Z0Z
Z0L0Z0Z0
0Z0ZQZ0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
Backtracking
QZ0Z0Z0Z
Z0L0Z0Z0
0Z0ZQZ0Z
ZQZ0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
Backtracking
QZ0Z0Z0Z
Z0L0Z0Z0
0Z0ZQZ0Z
ZQZ0Z0Z0
0Z0L0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
Backtracking
QZ0Z0Z0Z
Z0L0Z0Z0
0Z0ZQZ0Z
ZQZ0Z0Z0
0Z0Z0Z0L
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
Backtracking
QZ0Z0Z0Z
Z0L0Z0Z0
0Z0ZQZ0Z
ZQZ0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
Backtracking
QZ0Z0Z0Z
Z0L0Z0Z0
0Z0ZQZ0Z
Z0Z0Z0L0
0Z0Z0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
Backtracking
QZ0Z0Z0Z
Z0L0Z0Z0
0Z0ZQZ0Z
Z0Z0Z0L0
0Z0L0Z0Z
Z0Z0Z0Z0
0Z0Z0Z0Z
Z0Z0Z0Z0
Backtracking
E assim por diante...
Conceitos fundamentais
• espaço de soluções: conjunto de todas as tuplas que satisfaz
as restrições expĺıcitas.
• estados: conjunto de todas as subseqüências das tuplas do
espaço de soluções.
• algoritmo força bruta: enumera todas as tuplas do espaço de
soluções e verifica quais delas satisfazem as restrições
implicitas.
• algoritmo de backtracking:
• busca sistemática no espaço de estados do problema,
organizado segundo uma estrutura de árvore, chamada árvore
do espaço de estados.
• uso de funções limitantes para restringir a busca na árvore.
Tipicamente estas funções reduzem os doḿınios das variáveis
de acordo com as decisões anteriores.
Conceitos fundamentais
• Onde usar?
• Problemas cujas soluções são caracterizadas por uma
seqüência de decisões, cada uma delas feita sobre um conjunto
de várias possibilidades.
• Soluções são representadas por tuplas (vetores) de tamanho
fixo ou variável da forma (x1, . . . , xn).
• uma tupla é dita viável se ela atende ao conjunto de restrições
expĺıcitas e impĺıcitas que definem o problema.
• Solucionar o problema equivale a encontrar uma (ou toda)
tupla viável.
• Restrições:
• Expĺıcitas: definem os doḿınios das váriaves na tupla.
• Impĺıcitas: relações entre as variáveis da tupla que especificam
quais delas respondem ao problema.
Conceitos fundamentais
Origem do nome: backtracking
Durante a execução de um algoritmo de backtracking, pode-se
chegar a um estado cuja seqüência de decisões torna vazio o
doḿınio de uma variável da tupla sem que as restrições implicitas
tenham sido satisfeitas.
Neste caso, o algoritmo retrocede (≡ faz um backtracking),
revertendo a última decisão tomada e escolhendo um novo valor do
doḿınio para uma variável correspondente a ela. Se todas as
posśıveis escolhas tiverem sido tentadas, o algoritmo retrocede
novamente.
Encontramos B
• São todos os elementos de B1 com uma rainha em cada linha
tal que quaisquer duas rainhas não podem se enfrentar.
• Para saber se uma configuração pertence a A basta testar se
n = 8.
Codificação: 1
i n i c i a T a b u l e i r o ( ) ;
do
geraProxElemDeB ( ) ;
i f ( n==8) impr imeCon f i gu racao ( ) ;
whi le ( BNaoForVazio ( ) ) ;
Codificação: 1
A codificação 1 não é muito intessante porque não detalha
geraProxElemDeB(). Vamos melhorá-la.
Codificação: 2
i n i c i a T a b u l e i r o ( ) ;
pos = 0 ;
do
co l oque r a i n h a em t a b u l e i r o [ 0 , pos ] ;
g e r e todas as c o n f i g u r a c o e s
com r a i n h a f i x a na po s i c a o 0 ;
remova a r a i n h a da po s i c a o t a b u l e i r o [ 0 , pos ] ;
pos++;
whi le ( pos != 8 ) ;
Codificação: 3
pos1 = 0 ;
do
i f l i v r e ( t a b u l e i r o [ 1 , pos1 ] ) {
p o s i c i o n e r a i n h a em t a b u l e i r o [ 1 , h1 ] ;
g e r e todas as c o n f i g u r a ç õ e s com r a i n h a s f i x a s
a t é aqu i ;
remova a r a i n h a de t a b u l e i r o [ 1 , pos1 ] ;
pos1++;
whi le ( pos1 != 8 ) ;
Oito dos encadeados
Se continuassemos a codificação dessa maneira teriamos 8 laços
encadeados.
Isso não é elegante, mas é instrutivo.
Mostra que dá para criar um código recursivo muito conciso e
eficiente.
Do esboço para o código completo
Variáveis
• n = o número de rainhas no tabuleiro;
• configuracao[i], 0 ≤ i < n, o número da coluna ocupada pela
rainha na i-ésima linha.
Temos as estruturas necessárias e suficientes para codificar o
algoritmo.
Mas podemos tornar o algoritmo mais simples de escrever se
definirmos algumas variávais auxiliares.
Estruturas auxiliares: 1
Uma matriz de booleanos?
A cada inserção 28 posições terão que ser verificadas.
A cada remoção a matriz terá que ser verificada.
Da para fazer melhor.
Estruturas auxiliares: 2
• Não precisamos verificar linhas: estão livres por definição.
• Precisamos verificar colunas, diagonais ր e diagonais ց.
Estruturas auxiliares: 3
• boolean col[8];
• boolean up[15];
• boolean down[15];
Estruturas auxiliares: 3
• boolean col[8];
• boolean up[15];
• boolean down[15];
Examinar o código C (próxima aula!).
Pseudo código
i n t n , k ;
i n t c o n f i g [ 8 ] ;
boo l ean c o l [ 8 ] ;
boo l ean up [ −7:+7] ; /∗ i n d i c e s ! ∗/
boo l ean down [ 1 5 ] ;
main ( ) {
n = 0 ;
f o r ( k = 0 ; k < 8 ; k++) c o l [ k ] = t r u e ;
f o r ( k = 0 ; k < 15 ; k++) {
down [ k ] = t r u e ;
up [ k ] = t r u e ;
}
gen e r a t e ( ) ;
}
Pseudo código
vo id gene r a t e ( ) { i n t h ; h = 0 ;
do
i f /∗ t a b u l e i r o [ n , h ] e s t á l i v r e : ∗/
( c o l [ h ] && up [ n−h ] && down [ n+h ] ) {
/∗ po s i c . r a i n h a em t a b u l e i r o [ n , h ] : ∗/
c o n f i g [ n ] = h ; c o l [ h ] = f a l s e ;
up [ n−h ] = f a l s e ; down [ n+h ] = f a l s e ; n++;
i f /∗ t a b u l e i r o c h e i o : ∗/ ( n == 8) {
/∗ impr ime c on f i g u r a ç ã o : ∗/
f o r ( i n t k = 0 ; k < 8 ; k++) p r i n t ( c o n f i g [ k ] ) ;
p r i n t l n ;
} e l s e
gene r a t e ( ) ;
n−−;
/∗ remove r a i n h a de t a b u l e i r o [ n , h ] : ∗/
down [ n+h ] = t r u e ; up [ n−h ] = t r u e ; c o l [ h ] = t r u e ;
}
h++;
whi le ( h < 8)
}
Projeto de Algoritmos
Técnicas
• retrocesso (backtracking);
• dividir-para-conquistar (divide-and-conquer);
• programação dinâmica;
• algoritmos de busca local;
• algoritmos gulosos.