Este projeto foi desenvolvido com o objetivo de aplicar conceitos de Inteligência Artificial para resolver um problema do mundo real: dado um conjunto de dados de rotas de voos, encontrar as rotas com o menor tempo entre dois aeroportos. O trabalho foi estruturado em etapas, conforme especificado, e a equipe optou por utilizar a estratégia de busca heurística Best-First para alcançar a solução.
Dentre as diversas estratégias de busca, o Best-First se destaca por utilizar uma função heurística para priorizar os nós que parecem mais promissores, ou seja, que têm maior chance de levar à solução desejada. Esta abordagem permite que o algoritmo explore o espaço de busca de maneira mais eficiente, focando nos caminhos que são mais relevantes para o problema.
Comparado a outras estratégias, como a busca cega e o Hill Climbing, o Best-First oferece uma combinação de eficiência e precisão. Enquanto a busca cega pode ser muito demorada (explorando todos os caminhos possíveis) e o Hill Climbing pode ficar preso em soluções subótimas, o Best-First busca o equilíbrio, garantindo uma solução de qualidade em um tempo razoável.
Nesta fase, a equipe escolheu o desafio de otimizar rotas de voos entre aeroportos. O problema foi modelado considerando variáveis como aeroportos de origem e destino, tempo de voo, entre outros. A escolha deste problema foi justificada pela relevância e complexidade que ele apresenta no contexto real, sendo um desafio enfrentado por companhias aéreas e passageiros diariamente.
Após a modelagem, a equipe optou por utilizar o Depth First Search como exemplo de busca não informada sobre o problema em questão. No entanto, percebeu-se que, para este problema específico, uma abordagem heurística, como o Best-First, seria mais adequada.
Embora a equipe tenha optado pelo Best-First, outras estratégias foram consideradas e analisadas. Esta etapa serve como uma reflexão e análise crítica das escolhas feitas, garantindo que a solução escolhida seja realmente a mais adequada para o problema.
-
A implementação do algoritmo de A* se mostrou mais eficiente do que outras abordagens eurísticas. Destacamos duas razões para tal:
-
Otimidade : A* garante encontrar uma solução ótima (o caminho mais curto ou de menor custo) se a heurística utilizada for admissível (nunca superestima o custo real) e consistente.
-
Eficiência : A* combina o melhor dos dois mundos - leva em consideração o custo real do caminho até o momento (como a busca de custo uniforme) e a heurística estimada até o objetivo (como a BFS). Isso faz com que evite explorar caminhos que, embora pareçam promissores no início, podem não ser ótimos ao final.
O projeto demonstrou a importância de escolher a estratégia de busca correta para resolver problemas complexos. Através da busca heurística Best-First, foi possível encontrar rotas otimizadas entre aeroportos, contribuindo para uma melhor gestão de voos e satisfação dos passageiros. A equipe está confiante na escolha feita e acredita que esta abordagem pode ser aplicada em outros problemas do mundo real com características semelhantes.