Quebra cabeças de 8 peças - Inteligência Artificial

Prévia do material em texto

1 
 
 
UNIVERSIDADE FEDERAL DE MATO GROSSO 
INSTITUTO DE ENGENHARIA – CAMPUS VÁRZEA GRANDE 
 
 
 
RELATÓRIO 1: 
QUEBRA-CABEÇAS DE 8 PEÇAS 
 
 
 
KELVIN VINICIUS DA SILVA MAGALHÃES 
 
 
 
 
 
 
 
 
CUIABÁ, 2017. 
2 
 
 
UNIVERSIDADE FEDERAL DE MATO GROSSO 
INSTITUTO DE ENGENHARIA – CAMPUS VÁRZEA GRANDE 
 
 
 
RELATORIO 1: 
QUEBRA-CABEÇAS DE 8 PEÇAS 
 
Trabalho elaborado para fins 
avaliativos da disciplina 
Inteligência Artificial, do Instituto 
de Engenharia, Prof. Raoni 
Teixeira. 
 
 
 
 
KELVIN VINICIUS DA SILVA MAGALHÃES 
 
 
 
CUIABA, 2017 
3 
 
Sumário 
Resumo............................................................................................................................. 4 
Resultados e Discussões ................................................................................................. 5 
Sessão de Testes 1 ...................................................................................................... 6 
Sessão de Testes 2 ...................................................................................................... 8 
Conclusão ....................................................................................................................... 11 
Bibliografia ...................................................................................................................... 13 
 
 
4 
 
Resumo 
O trabalho consiste em uma implementação que otimize a função de 
minimização em um quebra-cabeças. Ou seja, buscar o menor custo para chegar 
num determinado objetivo. 
 Se tratando de um quebra-cabeças onde se conhece seu estado objetivo 
e seu tamanho (matriz 3 x 3) podemos adotar o conceito de busca heurística 
(aproximações imperfeitas)1 para chegar no estado objetivo com um menor 
custo. Lembrando que pode haver estados onde não é possível chegar ao 
objetivo. 
 Para este fim foi considerado que algumas etapas já estavam 
implementadas , ou seja , este trabalho trata-se de um complemento e coube 
desenvolver apenas as funções A*(astar.m) responsável pela resolução do 
quebra-cabeças que utiliza o conceito de nós e fila de prioridades; E a função 
Manhattan (manhattan.h) responsável pelo cálculo de distância que leva em 
consideração o estado do objetivo e o estado atual do quebra cabeças , ou seja 
, realiza uma comparação dos 2 estados através da soma das distancias vertical 
e horizontal. 
Ao final do trabalho é possível se obter uma função que funcione de forma 
minimizada e mais rápida do que nós homens conseguiríamos resolver, e será 
apresentado uma comparação de heurísticas (manhattan, hamming e heuristic), 
pois, há diversas formas de se calcular a distância até o objetivo. 
5 
 
Resultados e Discussões 
 Após a implementação dos códigos que faltavam, foi possível realizar uma 
comparação de resultados; como trata-se de obter a distância até o objetivo 
sabemos que há diversas maneiras de se abordar o problema do quebra-
cabeças de 8 peças, temos diferentes tipos de buscas e heurística. 
Neste trabalho utilizarei 2 formas de analisar o desempenho dos 
algoritmos de heurística se tratando do problema da distância, são eles o tempo 
de execução de cada heurística e a quantidade de nós(é cada estado que o 
quebra cabeça pode assumir) que estas heurísticas criam até chegar ao objetivo, 
o número de passos que as heurísticas vão criar até chegar ao objetivo será o 
mesmo para as 3 heurísticas testadas, então se é o mesmo número de passos 
, porque há uma grande diferença de desempenho? 
Primeiramente explicarei o princípio de funcionamento de cada heurística 
que calcula a distância. São elas: 
Manhattan: Utiliza o princípio de comparação e diferença, ou seja, comparamos 
o estado atual com o estado objetivo tendo como referência a sua posição dentro 
da matriz, que é de fácil determinação, pois, o tamanho da matriz é fixo e 
podemos utilizar o comando find () para encontrar a posição correta. Após 
localizar o número que queremos nas 2 matrizes (estado, objetivo), realizamos 
o cálculo da distância através da soma das diferenças. Adotamos a seguinte 
formula: 
𝐷𝑖𝑠𝑡â𝑛𝑐𝑖𝑎 = 𝐷𝑖𝑠𝑡â𝑛𝑐𝑖𝑎 + |𝑥 − 𝑎| + |𝑦 − 𝑏| 
Onde, ‘a’ e ’b’ são respectivamente linha e coluna da matriz estado e ‘x’ e 
‘y’ da matriz objetivo. 
Hamming: A heurística de hamming (hamming.h) utiliza o conceito de quantidade 
que estão no local errado para cada estado do jogo. Para números que estão na 
posição correta é atribuído o valor 0 e as que estão na posição incorreta é 
atribuído 1, e no final realizamos a soma, o resultado será a distância até o 
objetivo. 
6 
 
Heuristic: A função heuristic.m foi desenvolvida como uma alternativa para 
cálculo da distância como parte extra do trabalho. Funciona da seguinte forma, 
utilizando o mesmo princípio da Manhattan (comparação e diferença), sendo a 
comparação da mesma forma, uma matriz objetivo e uma matriz estado fazendo 
uso da função find() para encontrar a posição do número na matriz; O que altera 
é a forma de fazer o cálculo da distância que é mais parecido com a função 
Hamming, procede da seguinte forma: fazemos a diferençado entre as posições 
, mas a distância só é somada se o resultado da conta for diferente de zero , 
eliminando assim o cálculo para um número que já está na posição correta , ou 
seja , uma simplificação, mas que implica também em mais linhas de código. 
Abaixo a implementação: 
 
 
Figura 1: função heuristic 
Fonte: Criado pelo autor 
Sessão de Testes 1 
 Primeiramente faremos o teste de desempenho levando em consideração 
o tempo de execução e se as funções de cálculo de distância estão realmente 
funcionando, esse teste será feito a partir da função ex1.m fornecida no trabalho 
 
7 
 
Manhattan: Aproximadamente 140 segundos ou 2 minutos e 20 segundos 
Figura 2: executando arquivo ex1 com função manhattan 
Fonte: Criado pelo autor. 
 Heuristic: aproximadamente 1764.5 segundos ou 29 minutos e 24 segundos. 
 
Figura 3: executando arquivo ex1 com função Heuristic 
Fonte: Criado pelo Autor 
8 
 
Hamming: Não conseguiu completar o 5* teste, chegou ao 4* teste com 
aproximadamente 7 minutos e 37 segundos. 
 
Figura 4: executando arquivo ex1 com função Hamming 
Fonte: Criado pelo Autor 
Através de uma simples analise de tempo verificamos que a manhattan 
tem o melhor desempenho nestes testes, a função heuristic desenvolvida tem 
melhor desempenho que a hamming nos testes da função ex1. Observando que 
a função hamming não passou no 5* teste devido a limitação do computador 
utilizado, mesmo após várias horas testando ele atingiu apenas o 4* teste, mas 
se permanecesse rodando por um grande período de tempo, alcançaria o 
objetivo. 
Sessão de Testes 2 
 Agora temos a função test.m onde será definido alguns testes diretamente 
na função e os resultados serão apresentados na tabela abaixo.
 
Figura 5: Tabela comparação de desempenho das heurísticas 
Fonte: Criado pelo Autor 
9 
 
Os testes foram realizados conforme indicado na tabela acima, analisando 
2 parâmetros de desempenho como dito acima podemos perceber que para 
pequenas quantidades de movimentações (10 movimentações) os 
desempenhos da função são muito próximos , pois , a complexidade do problema 
é pequena sendo necessário analisar o desempenho pela quantidade de 
estados criados(nohs) porque no desempenho temporal a diferença é quase 
insignificante, mas quando temos mais que 10 movimentos , como o exemplo 
das 14 movimentações , há uma diferença grande no desempenho tantotemporal como de estados. Abaixo está os gráficos correspondentes aos 4 
testes conforme o desempenho analisado. 
 
Figura 6: Gráfico desempenho temporal 
Fonte: Criado pelo Autor 
 
 
 
 
10 
 
 
Figura 7: Gráfico de desempenho criação de nós. 
Fonte: Criado pelo Autor 
Foi necessário fazer uma adaptação no gráfico no eixo vertical , alterando 
sua escala para logaritmica na base 10 , pois , há um enorme diferença de 
quantidades quando a quantidade de movimentações é maior que 10 , e isto está 
diretamente ligado ao fato da complexidade do problema. 
 
11 
 
Conclusão 
 Ao término do trabalho ficou claro que a melhor heuristica a ser aplicada 
foi a manhattan , pois, apresenta melhores resultados em questão de tempo 
quando o número de movimentações é grande e também na questão de criação 
de nós(estados) e isso se deve a lógica de código da função manhattan. A 
heuristica que foi desenvolvida como desafio teve desempenho intermediário , 
pois , é pior que a manhattan , mas tem desempenho melhor que a hamming. 
O que se conclui de importante desta analise é que devemos realizar 
diversos testes(amostras) e não só de tempo de execução. Deste Modo, como 
alternativa foi adotado a analise de desempenho por nós criados(estados) que é 
mais conclusiva que a temporal e explica o porque á função manhattan é melhor. 
Neste relatório foi mostrado apenas alguns testes , mas que não foram os unicos 
realizados , pois, se fosse testado superficialmente apenas para movimentações 
menores ou igual a 10 o desempenho realmente é muito próximo entre as 
heuristicas; e isso poderia ocasionar uma enorme perda de tempo se escolhido 
um algoritmo diferente do manhattan como parte de um projeto , a função não 
seria a melhor possível. 
 Ficou claro que a resposta da pergunta incial é que como as heuristicas 
tendo a mesma quantidade de movimentação , o que interfere no desempenho 
é a quantidade de nós(estados do quebra-cabeças)1 criados por cada função, 
está quantidade é muito discrepante e isto ocasiona a diferença de desempenho 
temporal que está diretamente ligado á lógica do código, a utilização de 
comparações acelera o processo , então conclui-se que as funções manhattan 
e heuristic tem melhor desempenho que a função hamming. 
Aprender o funcionamento de algumas funções como a manhattan e A* , 
além de ter a possibilidade de criar uma nova heuristica traz uma nova 
perpectiva, utilizar ferramentas de otimização é fundamental para qualquer 
engenheiro, principalmente para á área de engenharia de controle e 
Automação/Computação e este trabalho proporcionou esta experiência, que é 
possível resolver problemas complexos que humanamente são quase 
impossíveis de resolver em curtos prazos de tempo ou com a melhor otimização 
12 
 
através da inteligência artificil utilizando artíficios como jogos de quebra-
cabeças. 
13 
 
Bibliografia 
[1] Teixeira, R. F. (6 de de Novembro de de 2017). Atividade Prática 1: 
Quebra-Cabeças de 8 peças. UFMT, Cuiabá-MT.