Skip to content

Latest commit

 

History

History
34 lines (34 loc) · 1.53 KB

README.md

File metadata and controls

34 lines (34 loc) · 1.53 KB
Raw

dimacs-project-AI

Para esta atividade você deverá utilizar as seguintes instâncias da base DIMACS (http://www.diag.uniroma1.it/~challenge9/download.shtml): 1- Oeste Americano 2- Centro Americano 3- Leste Americano 4- Todo o Estados Unidos

O que seu trabalho deverá fazer:

O usuário poderá escolher um dos 3 primeiros mapas acima (Todo Estados Unidos

só se conseguir).

Dado a escolha do mapa, o usuário irá colocar uma coordenada geográfica de

origem e destino (latitude e longitude, considere que o usuário irá colocar um dos pontos da base DIMACS como entrada, podendo ser inteiros)

Seu trabalho deverá calcular uma rota entre os dois pontos usando os seguintes

algoritmos:

  • Busca em Largura
  • Busca em profundidade (podendo ser o limitado)
  • Busca de custo uniforme
  • A*
  • IDA* (optativo)

Para o algoritmo A* considere pelos menos duas heurísticas:

  • Linha reta entre as duas coordenadas (heurística “terra plana”);
  • Distância Haversine;
  • Outra heurística que você ache interessante.

Seu programa deverá executar cada um dos algoritmos mencionados e ao fim

deverá imprimir as seguintes métricas:

  • Quantidade de nós expandidos;
  • Fator de ramificação médio;
  • Tempo para encontrar a solução;
  • Quantidade de memória alocada para a execução.

Você poderá colocar um limite de tempo máximo de execução. Por exemplo, 5

minutos.

Crie um relatório com 50 pontos de origem e destinos aleatórios pontos 50 aleatórios

e faça uma tabela de comparação com as métricas.