Exercícios de Fixação 05 - Backtracking - Gabarito

Prévia do material em texto

ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
Lista de Exercícios de Fixação 05
Backtracking
1. [Prática em Laboratório] Neste exercício, vamos aplicar backtracking ao problema do passeio do
cavalo no tabuleiro de xadrez. Dado um tabuleiro com n x n posições, o cavalo se movimenta
segundo as regras do xadrez, ou seja, em ‘L’. A partir de uma posição inicial (x 0, y0), o problema
consiste em encontrar, se existir, um passeio do cavalo com n2 – 1
movimentos, visitando todos os pontos do tabuleiro uma única vez. 
Podemos pensar no tabuleiro como uma matriz n x n e, para cada
posição, podemos indicar uma das situações:
• t[x, y] = 0, se <x, y> não foi visitada;
• t[x, y] = i, se <x, y> é visitada no i-ésimo movimento, onde 1 ≤ i ≤ n2.
Sendo assim, com base no algoritmo backtracking genérico, a seguir, podemos
pensar em uma implementação para solucionar o problema do passeio do cavalo.
Segue a implementação, em Java, de uma possível solução para o problema.
public class PasseioDoCavalo { 
 //dx e dy usados para calcular as coordenadas dos movimentos possíveis
 final int[] dx = {2, 1, -1, -2, -2, -1, 1, 2}; 
 final int[] dy = {1, 2, 2, 1, -1, -2, -2, -1};
 
 final int n; //número de posições do tabuleiro
 final int nCasas; //número total de casas
 int[][] tabuleiro;
1
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
 
 public PasseioDoCavalo(int n) {
 this.n = n;
 this.nCasas = n * n;
 this.tabuleiro = new int[n][n];
 }
 
 boolean ehAceitavel(int x, int y) { 
 //é aceitável se estiver dentro do tabuleiro e a se casa não foi visitada
 boolean result = (x >= 0 && x <= n - 1);
 result = result && (y >= 0 && y <= n - 1);
 result = result && (tabuleiro[x][y] == 0);
 return result;
 }
 
 //tenta o i-ésimo movimento em (x, y) 
 boolean tentaMovimento(int i, int x, int y) { 
 //Verifica a quantidade de movimentos
 boolean done = (i > nCasas);
 int k = 0;
 int u, v; //<u, v> é posição de destino e <x, y> é a posição atual
 while (!done && k < 8) {
 //u e v são as coordenadas dos 8 movimentos possíveis em volta do cavalo
 u = x + dx[k];
 v = y + dy[k];
 if (ehAceitavel(u, v)) {
 tabuleiro[u][v] = i;
 done = tentaMovimento(i + 1, u, v); //tenta outro movimento
 if (!done) 
 tabuleiro[u][v] = 0; //sem sucesso. Descarta movimento
 }
 k = k + 1; //passa ao próximo movimento possível
 }
 return done;
 } 
 void mostraPasseio (int x, int y) { 
 //mostra todos os movimentos a partir de (x, y)
 tabuleiro[x][y] = 1;
2
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
 boolean done = tentaMovimento(2, x, y);
 if (done) {
 for (int i = 0; i < n; i++) {
 for (int j = 0; j < n; j++) {
 System.out.print(tabuleiro[i][j] + " ");
 }
 System.out.println();
 }
 } else {
 System.out.println("Não há passeio possível");
 }
 }
 
 public static void main(String[] args) {
 int n = Integer.parseInt(args[0]);
 int x = Integer.parseInt(args[1]);
 int y = Integer.parseInt(args[2]);
 new PasseioDoCavalo(n).mostraPasseio(x, y); 
 } 
}
a. Execute o código-fonte e observe a saída. O que ela representa?
b. Qual é a complexidade computacional da solução?
c. Qual é a restrição aplicada e onde ela é utilizada, no código, para indicar backtracking?
2. Como o backtracking consegue efetuar uma busca eficiente, apesar de não ser exaustiva?
Porque a técnica backtracking é um refinamento do algoritmo de busca por força bruta (ou
enumeração exaustiva), no qual boa parte do espaço de soluções pode ser eliminada sem ser
explicitamente examinada.
3. Considere a seguinte fórmula booleana e demonstre o resultado da aplicação da técnica backtracking
para o problema da satisfatibilidade (SAT).
3
x∨y∨z x∨y y∨z  z∨ x x∨y∨z 
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
Apresente o passo-a-passo.
Lembremos que fazemos backtracking quando uma cláusula é violada.
4. Um arranjo booleano M[1..n,1..n] representa um labirinto quadrado. Estando em um
determinado ponto do labirinto é possível se movimentar para pontos adjacentes na mesma
linha ou mesma coluna. Se M[i, j] é True, é possível passar pelo ponto (i, j); se M[i, j] é
False, não é possível passar pelo ponto (i,j). É possível usar uma solução por backtracking
que encontra um caminho, se existir, do ponto (1,1) para o ponto (n,n). A seguir,
encontramos um exemplo de um labirinto 5x5. Defina restrições para a sua solução de
backtracking e monte a árvore de espaço de estados, indicando a solução do exemplo.
4
x = 0x = 1
 (x V y V z)(x V ~y)(y V ~z)(z V ~x)(~x V 
~y V ~z)
(y V ~z)(z)(~y V ~z)
z = 1 z = 0
 (y)(~y)
y = 1 y = 0
 ()
Cláusula 
violada
Back
track
ing
 ()
Cláusula 
violada
Ba
ckt
rac
kin
g
 (y)()
Cláusula 
violada
Ba
ckt
rac
kin
g
 (y V z)(~y)(y V 
~z)
 ()
y = 0y = 1
Cláusula 
violada
Bac
ktra
ckin
g
 (z)(~z)
z = 0
z = 1
()
()
Cláusula 
violada
Cláusula 
violadaBa
ckt
rac
kin
g
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
Sugestão de solução. Restrições: Seja (i,j) a posição em cada célula do labirinto, incrementar i →
andar para a direita; decrementar i → andar para a esquerda; incrementar j → andar descendo;
decrementar j → andar subindo. Iniciamos no (1,1), sempre tentando descer incrementando j, se o
quadrado for falso, tentaremos andar para direita incrementando i, se não for possível iremos para
esquerda. Portanto, a árvore de estados pode ser representada comos segue.
5
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
5. Ajude um rato a encontrar um pedaço de queijo no labirinto, a seguir.
Um labirinto desses pode ser representado por uma matriz retangular L, cujo elemento lij vale 0 ou
-1 conforme a casa correspondente do labirinto seja uma passagem livre ou uma parede,
respectivamente. É possível aplicar backtracking ao problema? Justifique. Em caso positivo, defina
as restrições a serem consideradas para a solução. 
Sugestão de solução. Restrições: Seja (i,j) a posição em cada célula do labirinto, incrementar i →
andar para a direita; decrementar i → andar para a esquerda; incrementar j → andar descendo;
decrementar j → andar subindo. Iniciamos no (1,1), sempre tentando descer incrementando j, se o
quadrado for falso, tentaremos andar para direita incrementando i, se não for possível iremos para
esquerda.
6
	Lista de Exercícios de Fixação 05