The Paris Metro problem is often used in artificial-intelligence classes to practise heuristics. The example below has only a few possible paths, but using the entire Paris map makes the search take much longer and impractical without a suitable heuristic.
The goal is to develop an algorithm that can use distances between stations to find the fastest route between two stations in a reasonable amount of time.
The problem is that, in addition to train speeds, the algorithm must account for the time required to change lines. Each colour represents a different metro line. A user must be able to select origin and destination stations, and the application must show the route and total travel time to guide the passenger.
This project was developed for the Artificial Intelligence course in the Computer Science program at Unisinos.