Algoritmos Recursivos

1 Introdução à Computação II – 5954006 Introdução à Computação II 5954006 3. Algoritmos Recursivos Prof. Renato Tinós Depto. de Computação e Matemática (FFCLRP/USP) 2 Introdução à Computação II – 5954006 3. Algoritmos Recursivos 3.1. Recursão 3.2. Princípios de Recursão 3.3. Algoritmos Exaustivos Principais Tópicos 3 Introdução à Computação II – 5954006 • A recursividade pode ser usada para a resolução de problemas em que todas as alternativas possíveis devem ser exploradas • Este procedimento é empregado pelos Algoritmos Exaustivos (ou Algoritmos Tentativa e Erro) nos quais  O processo é decomposto em um número finito de subtarefas parciais  As subtarefas são exploradas exaustivamente 3.3. Algoritmos Exaustivos 4 Introdução à Computação II – 5954006 3.3. Algoritmos Exaustivos • Percurso do Cavalo de Xadrez  É possível o cavalo percorrer todo o tabuleiro, tal que todas as células sejam percorridas exatamente uma vez?  O cavalo deve se mover segundo as regras do jogo de xadrez... 5 Introdução à Computação II – 5954006 • Percurso do Cavalo de Xadrez 3.3. Algoritmos Exaustivos 6 Introdução à Computação II – 5954006 • Percurso do Cavalo de Xadrez 3.3. Algoritmos Exaustivos 7 Introdução à Computação II – 5954006 • Percurso do Cavalo de Xadrez 3.3. Algoritmos Exaustivos 8 Introdução à Computação II – 5954006 • Percurso do Cavalo de Xadrez 3.3. Algoritmos Exaustivos 9 Introdução à Computação II – 5954006 • Percurso do Cavalo de Xadrez 3.3. Algoritmos Exaustivos 10 Introdução à Computação II – 5954006 • Percurso do Cavalo de Xadrez 3.3. Algoritmos Exaustivos 11 Introdução à Computação II – 5954006 • Percurso do Cavalo de Xadrez 3.3. Algoritmos Exaustivos 12 Introdução à Computação II – 5954006 • Percurso do Cavalo de Xadrez 3.3. Algoritmos Exaustivos 13 Introdução à Computação II – 5954006 • Percurso do Cavalo de Xadrez 3.3. Algoritmos Exaustivos 14 Introdução à Computação II – 5954006 • Percurso do Cavalo de Xadrez  Considere que o tamanho do tabuleiro pode variar N colunas 3.3. Algoritmos Exaustivos 15 Introdução à Computação II – 5954006 Algoritmo TenteProximoMovimento() iniciar seleção dos movimentos faça selecionar o próximo candidato da lista de movimentos se (aceitável) registrar movimento se (tabuleiro não preenchido completamente) TenteProximoMovimento() se (insucesso) eliminar movimento fim se fim se fim se enquanto (movimento sem sucesso && há mais candidatos) 3.3. Algoritmos Exaustivos 16 Introdução à Computação II – 5954006 • 1ª Versão: Refinamentos  O tabuleiro será representado por uma matriz de inteiros na qual os índices utilizados variam de 1 até o número de linhas/colunas, ou seja, h[1..n][1..n] sendo: h[x][y] = 0 indica que a célula (x,y) não foi ocupada h[x][y] = i indica que a célula (x,y) foi ocupada no movimento i (1 ≤ i ≤ n2) n indica o tamanho do tabuleiro (número de linhas ou colunas) 3.3. Algoritmos Exaustivos 17 Introdução à Computação II – 5954006 • Parâmetros do procedimento  (x,y) : coordenadas onde o cavalo se encontra  i : número do movimento (para fins de registro)  sucesso : variável Booleana que indica que o movimento teve sucesso • (u,v) serão duas variáveis locais que representam as coordenadas dos possíveis pontos de destino dos movimentos, determinados conforme a lei de movimentação do cavalo 3.3. Algoritmos Exaustivos 18 Introdução à Computação II – 5954006 • “tabuleiro não preenchido completamente”  i < n2 • “aceitável”  1 ≤ u ≤ n e 1 ≤ v ≤ n e h[u][v] = 0 • “registrar movimento”  h[u][v] = i • “eliminar movimento”  h[u][v] = 0 3.3. Algoritmos Exaustivos 19 Introdução à Computação II – 5954006 Algoritmo TenteProximoMovimento( i , x , y , &s ) iniciar seleção dos movimentos sucesso 0 faça seja (u,v) o ponto de destino do próximo movimento se ( ( 1 ≤ u ) e ( u ≤ n ) e ( 1 ≤ v ) e ( v ≤ n ) e ( h[u][v] = 0 ) ) h[u][v]  i // registrar movimento se ( i < n*n ) TenteProximoMovimento(i+1 , u , v, sucesso); se ( sucesso= 0 ) h[u][v]  0 // eliminar movimento fim se senão sucesso  1 fim se fim se enquanto ( (sucesso = 0 ) e (há mais candidatos) ) s  sucesso 3.3. Algoritmos Exaustivos 20 Introdução à Computação II – 5954006 • Até o momento, o programa foi desenvolvido de maneira completamente independente das regras que regem os movimentos do cavalo • Dado um par de coordenadas (x,y), existem oito possíveis células candidatas (u,v) de destino 5 4 3 2 8 1 6 7 3.3. Algoritmos Exaustivos 21 Introdução à Computação II – 5954006 • Movimentos Possíveis  (x,y) = posição atual  (u,v) = nova posição 1: (x+2,y+1) 2: (x+1,y+2) 3: (x-1,y+2) 4: (x-2,y+1) 5: (x-2,y-1) 6: (x-1,y-2) 7: (x+1,y-2) 8: (x+2,y-1) 5 4 3 2 8 1 6 7 x y 3.3. Algoritmos Exaustivos 22 Introdução à Computação II – 5954006 • Um método simples para obter (u,v) a partir de (x,y) é através da adição de diferenças de coordenadas, que serão armazenadas nos vetores dx e dy, que serão iniciados com valores apropriados • Um índice k será utilizado para numerar o próximo candidato • O procedimento recursivo é iniciado por uma chamada, tendo como parâmetros as coordenadas iniciais (i,j) fornecidas pelo usuário; a esta posição no tabuleiro deve ser atribuído o valor 1:  h[i][j] = 1;  TenteProximoMovimento(2,i,j,q); 3.3. Algoritmos Exaustivos 23 Introdução à Computação II – 5954006 #include <iostream> #include <iomanip> using namespace std; const int Size = 8; // tamanho maximo int dx[Size+1] = {0,2,1,-1,-2,-2,-1,1,2}, dy[Size+1] = {0,1,2,2,1,-1,-2,-2,-1}, h[Size+1][Size+1], n; //---------------------------------------- void Print() { int i,j; for(i=1; i<=n; i++) { for(j=1; j<=n; j++) cout << setw(5) << h[i][j]; cout << endl; } cout << endl; } //---------------------------------------- void TryNextMove(int i,int x,int y,bool &s) { int u,v,k; bool sucesso; k = 0; sucesso = false; do { k++; u = x + dx[k]; v = y + dy[k]; if (1<=u && u<=n && 1<=v && v<=n && h[u][v]==0) { h[u][v] = i; if (i < n*n) { TryNextMove(i+1,u,v,sucesso); if (!sucesso) h[u][v] = 0; } else sucesso = true; } } while (!sucesso && k < Size); s = sucesso; } 3.3. Algoritmos Exaustivos 24 Introdução à Computação II – 5954006 int main() { int i,j; bool q; cout << "Tamanho do tabuleiro (1-8): "; cin >> n; for(i=1; i<=n; i++) for(j=1; j<=n; j++) h[i][j] = 0; cout << "Posicao inicial do cavalo (x,y): "; cin >> i >> j; h[i][j] = 1; TryNextMove(2,i,j,q); if (q) Print(); else cout << "Caminho nao encontrado" << endl; return 0; } Tamanho do tabuleiro (1-8): 5 Posicao inicial do cavalo (x,y): 3 3 23 10 15 4 25 16 5 24 9 14 11 22 1 18 3 6 17 20 13 8 21 12 7 2 19 Tamanho do tabuleiro (1-8): 5 Posicao inicial do cavalo (x,y): 4 2 23 10 13 4 21 12 5 22 9 14 17 24 11 20 3 6 1 18 15 8 25 16 7 2 19 Tamanho do tabuleiro (1-8): 6 Posicao inicial do cavalo (x,y): 1 1 1 16 7 26 11 14 34 25 12 15 6 27 17 2 33 8 13 10 32 35 24 21 28 5 23 18 3 30 9 20 36 31 22 19 4 29 3.3. Algoritmos Exaustivos 25 Introdução à Computação II – 5954006 6 17 20 13 11 22 1 18 16 5 24 9 23 10 15 4 8 3 14 25 21 12 7 2 19 3.3. Algoritmos Exaustivos • Exemplo de percurso 26 Introdução à Computação II – 5954006 • O algoritmo visto anteriormente é um exemplo de um algoritmo exaustivo • O padrão característico de um algoritmo exaustivo é que  passos próximos da solução total são obtidos e armazenados para uso futuro eliminados da memorização quando se descobre que o passo corrente não terá, seguramente, nenhuma possibilidade de conduzir à solução total procurada, o passo levará a um beco sem saída • Esta característica é conhecida como backtracking 3.3. Algoritmos Exaustivos 27 Introdução à Computação II – 5954006 Algoritmo Backtracking() iniciar seleção de candidatos faça próxima seleção se (aceitável) armazenar se (solução incompleta) Backtracking() se ( sem sucesso) cancelar seleção fim se fim se fim se enquanto ( (sem sucesso) e (há mais candidatos) ) 3.3. Algoritmos Exaustivos 28 Introdução à Computação II – 5954006 • Na prática, os programas assumem diversos padrões, derivados do padrão geral • Uma forma padrão usualmente encontrada utiliza um parâmetro explícito, que indica o grau de profundidade de recursão e que permite a utilização de uma condição simples de término • Se, além disso, em cada passo o número de candidatos a serem avaliados for fixo (por exemplo, m), então o padrão seguinte é aplicável, sendo ativado pelo comando Backtracking2(1) 3.3. Algoritmos Exaustivos 29 Introdução à Computação II – 5954006 Algoritmo Backtracking2( i ) k  0 faça k  k + 1 selecionar o k-ésimo candidato se (aceitável) armazenar se ( i < n ) Backtracking2( i+1 ) se ( sem sucesso) cancelar seleção fim se fim se fim se enquanto ( (sem sucesso) e ( k < m ) ) 3.3. Algoritmos Exaustivos 30 Introdução à Computação II – 5954006 • O problema das oito rainhas  Suponha que você tenha  8 rainhas de um jogo de xadrez um tabuleiro de xadrez 3.3. Algoritmos Exaustivos 31 Introdução à Computação II – 5954006 • O problema das oito rainhas  As rainhas podem ser dispostas no tabuleiro de modo que duas rainhas não se ataquem? 3.3. Algoritmos Exaustivos 32 Introdução à Computação II – 5954006 • O problema das oito rainhas  Duas rainhas não podem ficar na mesma linha... 3.3. Algoritmos Exaustivos 33 Introdução à Computação II – 5954006 • O problema das oito rainhas  Duas rainhas não podem ficar na mesma linha, ou na mesma coluna... 3.3. Algoritmos Exaustivos 34 Introdução à Computação II – 5954006 • O problema das oito rainhas  Duas rainhas não são podem ficar na mesma linha, ou na mesma coluna, ou na mesma diagonal 3.3. Algoritmos Exaustivos 35 Introdução à Computação II – 5954006 • Generalizando  O problema das N rainhas N colunas N Rainhas 3.3. Algoritmos Exaustivos 36 Introdução à Computação II – 5954006 3.3. Algoritmos Exaustivos Algoritmo nRainhas( i ) iniciar seleção de posição para a selecionar a i-ésima rainha faça executar próxima seleção se (rainha está salva) posicionar rainha se ( i < n ) nRainhas( i + 1 ) se ( sem sucesso) remover rainha fim se fim se fim se enquanto ( (sem sucesso) e ( há mais posições ) ) 37 Introdução à Computação II – 5954006 • A rainha ataca peças que se encontrem na mesma linha, coluna ou diagonal do tabuleiro  Cada linha deve conter uma e só uma rainha  Cada coluna deve conter uma e só uma rainha • A variável i é o índice da linha • A variável j é o índice da coluna • A escolha da linha i limita-se a escolher uma dentre as n colunas disponíveis (1 ≤ j ≤ n) 3.3. Algoritmos Exaustivos 38 Introdução à Computação II – 5954006 • Cada vez que o programa coloca uma rainha no tabuleiro, sua posição (coluna) é guardada em x[i] i 3.3. Algoritmos Exaustivos 39 Introdução à Computação II – 5954006 • Cada vez que o programa coloca uma rainha no tabuleiro, sua posição é guardada em x[i] • Uma nova chamada recursiva é efetuada, nRainhas(i+1) i 3.3. Algoritmos Exaustivos 40 Introdução à Computação II – 5954006 • Cada vez que o programa coloca uma rainha no tabuleiro, sua posição é guardada em x[i] • Uma nova chamada recursiva é efetuada, nRainhas(i+1), iniciando outro nível de recursão... i 3.3. Algoritmos Exaustivos 41 Introdução à Computação II – 5954006 • Se há conflito o programa muda a nova rainha para a próxima coluna à direita i 3.3. Algoritmos Exaustivos 42 Introdução à Computação II – 5954006 • Quando não há mais conflitos o programa tenta colocar a próxima rainha no tabuleiro, ativando nRainhas(i+1) i 3.3. Algoritmos Exaustivos 43 Introdução à Computação II – 5954006 • Vamos olhar na terceira linha. A primeira posição que tentamos tem um conflito... i 3.3. Algoritmos Exaustivos 44 Introdução à Computação II – 5954006 • Vamos olhar na terceira linha. A primeira posição que tentamos tem um conflito... • ...então mudamos para a coluna 2. Mas outro conflito surge... i 3.3. Algoritmos Exaustivos 45 Introdução à Computação II – 5954006 • Vamos olhar na terceira linha. A primeira posição que tentamos tem um conflito... • ...então mudamos para a coluna 2. Mas outro conflito surge... • ...e mudamos para a terceira coluna. Ainda há conflito... i 3.3. Algoritmos Exaustivos 46 Introdução à Computação II – 5954006 • Vamos olhar na terceira linha. A primeira posição que tentamos tem um conflito... • ...então mudamos para a coluna 2. Mas outro conflito surge... • ...e mudamos para a terceira coluna. Ainda há conflito... • ...e mudamos para a quarta coluna, ainda há conflito... • ...e não existem mais colunas disponíveis!!! i 3.3. Algoritmos Exaustivos 47 Introdução à Computação II – 5954006 • Quando não há mais espaço em uma linha, o algoritmo retorna para a recursão de nível anterior, ou seja, do nível 3 para o 2 i 3.3. Algoritmos Exaustivos 48 Introdução à Computação II – 5954006 • Quando não há mais espaço em uma linha, o algoritmo retorna para a recursão de nível anterior, ou seja, do nível 3 para o 2 • ...e continua trabalhando na linha 2, mudando a rainha para a direita i 3.3. Algoritmos Exaustivos 49 Introdução à Computação II – 5954006 • Essa posição não apresenta conflitos, então podemos ativar o próximo nível de recursão, nRainhas(i+1) i 3.3. Algoritmos Exaustivos 50 Introdução à Computação II – 5954006 • Na linha 3, começamos novamente pela primeira coluna, reiniciando todo o processo i 3.3. Algoritmos Exaustivos 51 Introdução à Computação II – 5954006 • Implementação  A escolha óbvia para representar as rainhas no tabuleiro é uma matriz quadrada Entretanto, esta escolha acarretaria a necessidade de operações exaustivas para a verificação de disponibilidade de posições  Assim, representaremos tão diretamente quanto possível a informação que for realmente relevante e utilizada com freqüência Não é o caso da posição das rainhas mas sim se a rainha já tenha sido colocada corretamente em uma dada posição (em uma linha, coluna ou diagonal) Note que somente uma rainha deve ser colocada em cada coluna j (1 ≤ j ≤ n ) 3.3. Algoritmos Exaustivos 52 Introdução à Computação II – 5954006 • int x[1..8]  x[i] indica a posição (coluna) da rainha na i-ésima linha • bool a[1..8]  a[j] significa “nenhuma rainha está na j-ésima coluna” • bool b[2..16]  b[k] significa “nenhuma rainha ocupa a k-ésima diagonal do tipo / ”  k = i + j 3.3. Algoritmos Exaustivos 53 Introdução à Computação II – 5954006 • bool c[2..16]  c[r] significa “nenhuma rainha ocupa a r-ésima diagonal do tipo \ ”  r = i – j (-7 <= r <= 7, índice assume valores negativos)  r = i – j + 9 (2 <= r <= 16) 3.3. Algoritmos Exaustivos 54 Introdução à Computação II – 5954006 • “posicionar rainha”  x[i] = j  a[j] = false  b[i+j] = false  c[i-j+9] = false • “remover rainha”  a[j] = true  b[i+j] = true  c[i-j+9] = true • “rainha está salva”  a[j] e b[i+j] e c[i-j+9] 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 3.3. Algoritmos Exaustivos 55 Introdução à Computação II – 5954006 #include <iostream> #include <iomanip> using namespace std; bool a[9],b[17],c[17]; int n,x[9]; void Print() { int i; for(i=1; i<=n; i++) cout << "(" << i << "," << x[i] << ") "; cout << endl; } void Try(int i, bool &s) { int j; j = 0; s = false; do { j++; if (a[j] && b[i+j] && c[i-j+9]) { x[i] = j; a[j]=b[i+j]=c[i-j+9]=false; if (i < n) { Try(i+1,s); if (!s) a[j]=b[i+j]=c[i-j+9]=true; } else s = true; } } while (!s && j < n); } 3.3. Algoritmos Exaustivos 56 Introdução à Computação II – 5954006 int main() { int i; bool q; cout << "Tamanho do tabuleiro (1-8): "; cin >> n; for(i=1; i<=8; i++) a[i] = true; for(i=2; i<=16; i++) { b[i] = true; c[i] = true; } Try(1,q); if (q) Print(); else "Nao foi possivel posicionar as rainhas" << endl; return 0; } 3.3. Algoritmos Exaustivos 57 Introdução à Computação II – 5954006 x1 x2 x3 x4 x5 x6 x7 x8 1 5 8 6 3 7 2 4 1 6 8 3 7 4 2 5 1 7 4 6 8 2 5 3 1 7 5 8 2 4 6 3 2 4 6 8 3 1 7 5 2 5 7 1 3 8 6 4 2 5 7 4 1 8 6 3 2 6 1 7 4 8 3 5 2 6 8 3 1 4 7 5 2 7 3 6 8 5 1 4 2 7 5 8 1 4 6 3 2 8 6 1 3 5 7 4 3.3. Algoritmos Exaustivos • Oito Rainhas: As Doze Soluções 58 Introdução à Computação II – 5954006 Comentários • Agradecimentos  Parte do material desta apresentação foi obtida através de slides da disciplina de Introdução à Computação II ministrada pelo Prof. José Augusto Baranauskas