Trafico

Diante do objetivo deste trabalho, fazer um estudo comparativo entre os algoritmos de busca de caminhos, o busca em largura, o busca em profundidade e o algoritmo A*, entre os personagens do jogo PacMan, os objetivos foram alcançados e superados, pois além do estudo comparativo entre os algoritmos mencionados, foram implementados também os algoritmos de busca em profundidade adaptado e o A* adaptado, sendo que estes algoritmos são específicos para o problema proposto, o jogo PacMan.
O algoritmo de busca em largura, em relação aos outros algoritmos implementados, encontra a solução do problema, porém testa uma grande quantidade de vértices, mesmo sabendo onde está o vértice que ele está procurando, mesmo assim ele é melhor que o busca em profundidade pois acha uma solução.
O algoritmo busca em profundidade, conforme os testes realizados, não é eficiente para o problema proposto, pois o “fantasma” dificilmente chega até onde está o “come-come”.
O algoritmo A* encontra sempre uma boa solução, ou seja, um caminho sem ter que testar uma grande quantidade de vértices, levando em consideração que é um algoritmo genérico, e que não foi criado para ser utilizado exclusivamente neste jogo.
O algoritmo A* adaptado, é a implementação do algoritmo A* com número limitado de vértices que podem ser tirados da lista de abertos, o número escolhido foi 25 vértices, levando em consideração o tamanho do labirinto implementado. O A* adaptado, às vezes testa menos vértices que o A*, porém na maioria dos testes realizados ele deixa de testar um vértice importante para a solução do problema, acabando testando mais vértices que o A*.
O algoritmo busca em profundidade adaptado mescla o algoritmo busca em profundidade com o algoritmo A*. Diante do problema proposto ele foi o algoritmo com o melhor desempenho, ou seja, a menor média de vértices testados. O busca em profundidade ordena os vértices adjacentes a serem testados por ordem de menor custo, colocando todos os adjacentes não