Exercicios de Fixação 05 - Backtracking

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?
3. Considere a seguinte fórmula booleana e demonstre o resultado da aplicação da técnica backtracking
para o problema da satisfatibilidade (SAT).
Apresente o passo-a-passo.
3
x∨y∨z x∨y y∨z  z∨ x x∨y∨z 
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
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.
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. 
4
	Lista de Exercícios de Fixação 05