Este projeto consiste na implementação de algoritmos de busca, para resolver o problema do menor caminho em um grafo. Nossa aplicação permite a criação de um grafo simples e retorna o menor caminho entre dois vértices dados, utilizando o algoritmo A*. Também implementamos o algoritmo de Dijkstra, mas devido ao tempo, não fomos capazes de integrá-lo ao front-end do projeto.
http://menor-caminho-ia.netlify.app/
https://github.com/YJangir49/AI_Snake_Game
A*-Search (AStar): O algoritmo A* é uma busca informada que combina a busca em largura com uma heurística para estimar o custo total de um caminho até seu objetivo. Ele expande os nós na ordem de seu custo total estimado, buscando o caminho mais eficiente.
Algoritmo de Dijksta: O Algoritmo de Dijkstra é um algoritmo de busca não informada. Ele não usa nenhuma informação sobre a localização do objetivo na busca. Em vez disso, ele explora o grafo, sempre escolhendo o próximo nó mais próximo (com a menor distância) para visitar.
Neste projeto, adotamos como heurística a distância (peso) entre os vértices do grafo em que a busca ocorre. Em nosso caso específico, o Algoritmo A* sempre recebe uma heurística igual ao valor real, o que significa que a estimativa de custo para alcançar o destino é sempre o correto. É comum em exemplos de A* o uso da distância euclidiana entre as coordenadas dos vértices, nosso código optou por encontrar o menor caminho.
Nesta etapa do projeto consiste na implementação do algoritmo A* em conjunto com a estrutura de dados grafos, para resolver o problema do menor caminho. A criação, a edição e a exibição de grafos é um grande diferencial de nossa aplicação.
A criação dos vértices e arestas do grafo é feito de forma dinâmica, pelo usuário. Também criamos duas instâncias de grafos predefinidos. Essa estruturação minuciosa e detalhada do grafo proporciona uma base sólida para a aplicação do algoritmo A*.
Implementação de outros algoritmos de busca, como a Busca em largura, a busca em profundidade e integração do algoritmo Dijkstra ao front end. Além disso, seria interessante tentar integrar alguma API de mapas, como a do Google Maps, para que seja possível calcular distâncias entre cidades ou estados e comparar os resultados obtidos pela aplicação com os dados reais
- Augusto César Honorato dos Santos
- Gabriel Teixeira Silveira