Baixe o app para aproveitar ainda mais
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
Compartilhar