Upload
samuel-lima
View
17
Download
5
Embed Size (px)
DESCRIPTION
Resolução do problema do tabuleiro defeituoso
Citation preview
Dividir e Conquistar
Resolução do problema do tabuleiro defeituoso
Aldo Pires – 1402225;
Jorge Costa – 1402247;
Samuel Lima – 1402607.
Trabalho para a unidade curricular Heurísticas Modernas
Mestrado em Tecnologias e Sistemas Informáticos Web – Universidade Aberta
13/05/2015
Índice Introdução ..................................................................................................................................... 1
A abordagem de dividir e conquistar ............................................................................................ 1
Problema do tabuleiro defeituoso .................................................................................................. 3
Desenvolvimento do algoritmo ..................................................................................................... 7
Conclusão .................................................................................................................................... 11
Introdução Muitas vezes deparamos com problemas aparentemente de difícil resolução, uma boa forma de
as solucionar é dividindo em subproblemas mais simples, resolver os subproblemas e juntar as
soluções obtendo a solução do problema inicial, esta técnica e conhecida por Dividir e conquistar.
Com este trabalho pretendemos, aplicar esta técnica “Dividir e Conquistar” na resolução do
problema do tabuleiro defeituoso.
Começamos por fazer uma abordagem geral sobre o algoritmo, aplicando a um exemplo de fácil
compreensão, seguidamente fizemos o enquadramento do problema do tabuleiro defeituoso,
depois passamos a resolução do problema aplicando o algoritmo “Dividir e Conquistar”,
seguidamente abordamos uma solução de implementação do algoritmo.
A abordagem de dividir e conquistar Para uma instância de problema P de tamanho n, se n for pequeno, o problema pode ser resolvido
diretamente, caso contrario, o problema pode ser dividida em sub-instâcias menores
independentes uns dos outros até que as sub-instâcias sejam trivialmente resolúveis, resolve-se as
sub-intâncias de P recursivamente e combina as suas soluções de modo a obter a solução do
problema inicial P seja obtido.
A resolução de um problema segundo este método é feito em três fases:
Divisão: o problema maior é dividido em problemas menores e os problemas menores
obtidos são novamente divididos sucessivamente de forma recursiva.
Conquista: o resultado do problema é calculado quando o problema é pequeno o suficiente.
Combinação: o resultado dos problemas menores são combinados até que seja obtida a
solução do problema maior.
Este método é implementado em algoritmos que utilizem a metodologia Top Down, onde a
geração dos subproblemas é feita de cima para baixo.
Um exemplo para ilustrar o uso dessa técnica é o algoritmo de ordenação de um vetor por
intercalação (MergeSort).
Neste caso temos que ordenar um vetor de tamanho n.
Dividir: Dividimos o vetor de tamanho n em dois sub-vetores de tamanho [n/2]
Conquista: Resolvemos o problema de ordenação de forma recursiva para estes dois sub-
vetores.
Combinação: Com os dois sub-vetores ordenados, construímos um vetor de tamanho n
ordenado.
MergeSort (A,p,r)
1: if p < r then
2: q = (p + r)/2 // Dividir o vetor no meio n = (p+r), n/2 = (p+r)/2
3: Mergesort(A,p,q) // Ordenar o primeira metade recursivamente
4: Mergesort(A, q + 1,r) // Ordenar a segunda metade recursivamente
5: Merge(A,p,q,r) // Intercalar as duas metades
Problema do tabuleiro defeituoso Consideremos um tabuleiro composto por quadrados, semelhantes ao de xadrez, de tamanho N×N
quadrados, em que uma qualquer dessas cassas é removida e passamos a chamar o tabuleiro de
“defeituoso”.
Figura 1- Tabuleiro de 2kx2k para k=3
Sendo que o tamanho dos lados do tabuleiro seja N: N=2k com k ≥ 1 pretende-se que o tabuleiro
defeituoso seja preenchido com peças em formato de L, designados de triominos, que ocupam
três casas sendo a orientação irrelevante.
Figura 2-Triominos com as suas quatros possíveis representações
Para a resolução do problema em casos em que k=1 ou mesmo k=2 pode ser resolvido
rapidamente sem muito esforço, como podemos ver na figura 3.
Figura 3-Tabuleiro 2x2 e 4x4
Com o aumento da complexidade do problema pode ficar difícil resolver o problema sem seguir
uma metodologia de apoio na sua resolução, sendo que podemos utilizar dividir para conquistar
como método de resolução.
Considerando o problema do tabuleiro da figura 1, tabuleiro de 8x8, podemos dividir o problema
e quatro sub-problemas menores do mesmo tamanho. Onde ficamos agora com o tabuleiro
dividido em quatro tabuleiros menores de tamanho 2k-1 x 2k-1 como mostra a figura 4.
Figura 4- Divisão do tabuleiro 8x8 em quatro de 4x4
Como podemos ver ficamos com um tabuleiro defeituoso e os outros três sem defeito e o próximo
passo será torna-los defeituosos, desenhado um triomino na parte central conforme mostra a
figura-5.
Figura 5-Desenho do triomino central
Repetimos o mesmo processo para todos os tabuleiros de tamanho 4x4, ficando agora com 16
tabuleiros de 2x2, figura 6 e utilizando a mesma estratégia para converte-los em defeituosos figura
7.
Figura 6 Figura 7
De maneira que podemos observar, que ficamos agora perante 16 pequenos problemas de fácil
resolução. Obtendo uma solução global (figura 8) do problema maior proposto inicialmente.
Figura 8
O algoritmo para resolução do problema do tabuleiro defeituoso pode ser representado pelo
fluxograma da figura 9.
Figura 9-Fluxograma resolução do problema tabuleiro defeituoso
Para definição das áreas do problema supomos que o problema seja um tabuleiro de tamanho J
colunas e I linhas onde inicialmente I=J=N=2k. Sendo assim temos valores de I linhas e J colunas
variando entre 1 e N.
Figura 10
A partir desses limites para a efetuar a divisão do problema inicial e quatro sub-problemas
menores, basta dividir as linhas e as colunas em duas partes iguais, conforme está ilustrada na
figura 10. Feita esta divisão obteremos quatro sub-problemas Q1, Q2, Q3 e Q4 delimitados pelos
valores da tabela 1.
P1 P2
Q1 Imin Jmin Imax/2 Jmax/2
Q2 Imin Jmax/2+1 Imax/2 Jmax
Q3 Imax/2+1 Jmin Imax Jmax/2
Q4 Imax/2+1 Jmax/2+1 Imax Jmax
Tabela 1
Já com estes limites estabelecidos, para marcar o triomino central, primeiro verifica qua dos sub-
problemas ficou com o ponto defeituoso de seguida transforma-mos os restantes em tabuleiros
defeituosos, seguindo a seguinte lógica:
PONTO NO Q1 I J
TRIOMINO
Q2 Imax/2 Jmax/2+1
Q3 Imax/2+1 Jmax/2
Q4 Imax/2+1 Jmax/2+1
Tabela 2-Ponto No Q1 Tabela 3-PONTO NO Q2
Desenvolvimento do algoritmo
O programa possui um menu com 4 opções (figura 11), a primeira recebe o parâmetro K que
define o tamanho do tabuleiro, a segunda opção é a opção de debugging que quando está ativo
nos mostra os passos do preenchimento da matriz e a opção de Resultado que dá inicio ao calculo
e exibição da matriz na tela.
Figura 11- Menu
PONTO NO Q2 I J
TRIOMINO
Q1 Imax/2 Jmax/2
Q3 Imax/2+1 Jmax/2
Q4 Imax/2+1 Jmax/2+1
PONTO NO Q3 I J
TRIOMINO
Q1 Imax/2 Jmax/2
Q2 Imax/2 Jmax/2+1
Q4 Imax/2+1 Jmax/2+1
PONTO NO Q4 I J
TRIOMINO
Q1 Imax/2 Jmax/2
Q2 Imax/2 Jmax/2+1
Q3 Imax/2+1 Jmax/2
Tabela 4- Ponto No Q3 Tabela 5-Ponto No Q4
Figura 12
Para isso criamos uma classe ChessBoard, onde foi necessário três atributos: N que é o tamanho
do tabuleiro, debug que nos avisa se é para fazer o debug e a Matriz (tabuleiro) que é um vector
de vector para inteiros que conforme o valor do atributo a K será definido o tamanho do vector.
Figura 13
Temos o método dividirConquistar que recursivamente vai dividindo o tabuleiro em quatro partes
iguais até o problema for trivialmente resolúvel.
void ChessBoard::dividirConquistar(int iMin,int iMax,int jMin,int jMax,int posicao){
/* verifica se a solução é trivialmente resolúvel */
if((iMax-iMin)==1){ /* se for verdade é porque a matrix já é de tamanho 2x2 */
/* preenche todas as células a volta do triomino com o valor do parâmetro posicao */
for(int i=iMin-1;i<iMax;i++)
Resultado
for(int j=jMin-1;j<jMax;j++)
if(matriz[i][j]==0) matriz[i][j]=posicao;
if(debug == 1) imprime(); /* impime se o debugin estiver activo*/
return ;
}
// caso ainda for possível a divisão então é verificado a célula que está preenchida e é feito o
preenchimento do triomino com metodo marcaTriomino
//marca o triominio central
marcaTriomino( iMin, iMax, jMin, jMax,verificaPonto( iMin, iMax, jMin, jMax));
//divide o problema e quatro sub-problemas
dividirConquistar(iMin,(iMin-1+iMax)/2,jMin,(jMin-1+jMax)/2,1);
dividirConquistar(iMin,(iMin-1+iMax)/2,(jMin-1+jMax)/2+1,jMax,2);
dividirConquistar((iMin-1+iMax)/2+1,iMax,jMin,(jMin-1+jMax)/2,3);
dividirConquistar((iMin-1+iMax)/2+1,iMax,(jMin-1+jMax)/2+1,jMax,4);
return;
}
O método marcaTriomino recebe como parâmetro os limites da nossa matriz e também o
retorno da função verificaPonto que nos dá o quadrante em que a célula esta preenchida, faz a
divisão da matriz em 4 quadrantes e preenche o triomino como nos mostra a seguir
switch(posicaoPonto){
case 1:
matriz[(iMin-1+iMax)/2-1][(jMin-1+jMax)/2]=trioCont;//Q2
matriz[(iMin-1+iMax)/2][(jMin-1+jMax)/2-1]=trioCont;//Q3
matriz[(iMin-1+iMax)/2][(jMin-1+jMax)/2]=trioCont;//Q4
break;
case 2:
matriz[(iMin-1+iMax)/2-1][(jMin-1+jMax)/2-1]=trioCont;//Q1
matriz[(iMin-1+iMax)/2][(jMin-1+jMax)/2-1]=trioCont;//Q3
matriz[(iMin-1+iMax)/2][(jMin-1+jMax)/2]=trioCont;//Q4
break;
case 3:
matriz[(iMin-1+iMax)/2-1][(jMin-1+jMax)/2-1]=trioCont;//Q1
matriz[(iMin-1+iMax)/2-1][(jMin-1+jMax)/2]=trioCont;//Q2
matriz[(iMin-1+iMax)/2][(jMin-1+jMax)/2]=trioCont;//Q4
break;
case 4:
matriz[(iMin-1+iMax)/2-1][(jMin-1+jMax)/2-1]=trioCont;//Q1
matriz[(iMin-1+iMax)/2-1][(jMin-1+jMax)/2]=trioCont;//Q2
matriz[(iMin-1+iMax)/2][(jMin-1+jMax)/2-1]=trioCont;//Q3
break;
}
O programa inicializa toda a matriz a 0 e faz o preenchimento da célula aleatoriamente com -1
com método - void solucaoLimpa(int k);
O código vai dividindo a matriz sempre em quatro partes iguais até chegar a de 2x2
automaticamente vai preenchendo os triominos como nos mostra a figura 14.
Figura 14
Conclusão
O presente trabalho pretendeu entender a importância do uso de técnicas heurísticas na
implementação de algoritmos para resolução de problemas computacionais complexos. Porem
um algoritmo só é eficiente se houver uma utilização otimizada dos recursos computacionais na
resolução de um determinado problema.
Concluímos que o algoritmo dividir e conquistar, demonstrou ser uma boa solução na resolução
do problema do tabuleiro defeituoso e com a sua devida implementação e otimização pode-se
obter bons resultados.
Bibliografia
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein - Algoritmos: teoria
e prática, tradução da 2ª edição [americana], Vandenberg D. de Souza, Ed. Campus, 2002. ISBN
85-352-0926-3.