O problema do metrô de Paris é muito utilizado nas aulas de Inteligência Artificial para praticar heurísticas. No exemplo abaixo há poucos caminhos possíveis, mas se utilizar o mapa de Paris inteiro o tempo necessário para encontrar o caminho mais rápido cresce muito tornando impraticável a solução sem uma heurística apropriada.
O objetivo principal é desenvolver um algoritmo que a partir das distâncias entre as estações consiga em tempo viável encontrar o caminho mais rápido entre duas estações.
O problema é que além de informar a velocidade dos trens, é necessário contabilizar um determinado tempo para troca de linha. Cada cor determina uma linha diferente do metrô. Deve ser possível selecionar a estação de origem e destino e é obvio que é necessário traçar o caminho a ser percorrido e o tempo total de viagem para instruir o passageiro.
Este trabalho foi desenvolvido para a disciplina de Inteligência Artificial no curso de Ciência da Computação da Unisinos