Inteligencia Artificial - Busca Labirinto

Prévia do material em texto

Trabalho Labirinto – Inteligência Artificial 
Nome: Adam Yoshida e Gabriela Pereira 
1) Estudar o funcionamento e rodar exemplos: 
a. Geração de labirintos 
b. Estratégias: Busca em largura, profundidade e A* 
 
Figura 1. Labirinto 41x41 gerado 
 
Figura 2. Busca A* em labirinto 41x41 
 
Figura 3. Busca BFS* em labirinto 41x41 
 
Figura 4. Busca DFS* em labirinto 41x41 
 
 
2) Efetuar estudo com tempo de execução e soluções encontradas 
cada estratégia de busca 
Tabela 1. Tabela Tamanho x Método com seus respectivos tempos 
3) Alterar o tamanho do labirinto e efetuar experimentos 
 
Figura 5. Labirinto 25x25 gerado 
 
Figura 6. Labirinto 57x57 gerado 
Tamanho/Método A* BFS DFS 
25x25 3.666 s 5.079 s 4.994 s 
41x41 3.457 s 6.375 s 6.584 s 
57x57 10.198 s 12.061 s 26.171 s 
 
Figura 7. Busca A* em labirinto 25x25 
 
Figura 8. Busca BFS* em labirinto 25x25 
 
 
Figura 9. Busca DFS* em labirinto 25x25 
 
Figura 10. Busca A* em labirinto 57x57 
 
Figura 11. Busca BFS* em labirinto 57x57 
 
Figura 12. Busca DFS* em labirinto 57x57 
4) Alterar as posições de início e fim do labirinto e efetuar os 
experimentos 
 
Figura 13. Busca A* em labirinto 41x41 modificado 
 
Figura 14. Busca BFS em labirinto 41x41 modificado 
 
Figura 15. Busca DFS em labirinto 41x41 modificado 
 
 
 
Tabela 2. Tabela Tamanho x Método com seus respectivos tempos 
em labirinto alterado 
Observações: O início passou a ser na posição (20,20) e o fim na posição 
(41,0). 
5) Para cada estratégia de busca alterar o código para informar o 
custo total (Número de nós visitados) 
Tabela 3. Tabela Tamanho x Métodos com o número de nós 
visitados 
6) Qual é a função de custo utilizada na busca A*? 
 
Figura 16. Função de busca usada em A* 
7) Alterar o código e implementar a distância City Block 
(Manhatan)na busca A* e efetuar os testes. 
Tamanho/Método A* BFS DFS 
41x41 5.836 s 9.782 s 5.276 s 
Tamanho/Método A* BFS DFS 
25x25 221 308 304 
41x41 208 384 394 
41x41 (modificado) 354 592 320 
57x57 622 742 1588 
 
Figura 16. Busca A* em labirinto 25x25 – City Block 
 
 
Figura 17. Busca A* em labirinto 41x41 – City Block 
 
Figura 18. Busca A* em labirinto 41x41 (modificado) – City Block 
 
Figura 19. Busca A* em labirinto 57x57 – City Block 
 
Figura 19. Função de custo A* – City Block 
 
 
 
 
Tabela 4. Tabela Tamanho x Método com o tempo de A* – City 
Block 
 
 
 
 
 
Tabela 5. Tabela Tamanho x Método com a contagem de nós de 
A* – City Block 
 
Tamanho/Método A* 
25x25 3.694 s 
41x41 3.449 s 
41x41 (modificado) 4.179 s 
57x57 10.471 s 
Tamanho/Método A* 
25x25 224 
41x41 210 
41x41 (modificado) 255 
57x57 634 
8) Alterar o código e implementar a função de custo conforme visto 
na última aula: