11
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

Resolução do problema do tabuleiro defeituoso

Embed Size (px)

DESCRIPTION

Resolução do problema do tabuleiro defeituoso

Citation preview

Page 1: Resolução do problema do tabuleiro defeituoso

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

Page 2: Resolução do problema do tabuleiro defeituoso

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

Page 3: Resolução do problema do tabuleiro defeituoso

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.

Page 4: Resolução do problema do tabuleiro defeituoso

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

Page 5: Resolução do problema do tabuleiro defeituoso

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

Page 6: Resolução do problema do 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:

Page 7: Resolução do problema do tabuleiro defeituoso

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

Page 8: Resolução do problema do tabuleiro defeituoso

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

Page 9: Resolução do problema do tabuleiro defeituoso

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;

Page 10: Resolução do problema do tabuleiro defeituoso

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

Page 11: Resolução do problema do tabuleiro defeituoso

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.