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

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.