Touring in Brazil: Given the Map of Brazil, as shown in Figure 1, what is the shortest path from one state (starting in its capital) to Espírito Santo (my hometown). Since you want to enjoy your travel, every time you cross a state, you must visit its capital.
 |
| Figure 1: Map of Brazil |
I used the
information contained in: http://www.areaseg.com/distancias.html to collect the
distance between two capitals and created the graph on Figure 2 to represent it. To help creating the graph the jgrapht library (http://jgrapht.org/) was used.
 |
| Figure 2: Distance between two neighbor states capital |
The algorithm used to calculate the shortest path is A* Graph Search, and the heuristic function gives the distance between the current city and the goal city. The heuristic will be the exact distance for any neighbor state but will be at least lower than the optimal path for non-neighbor state (the heuristic doesn’t have to visit the capitals in between those cities).
The applet bellow will calculate the shortest path from any starting city to Espírito Santo, and will also show an step-by-step of the fringe.
This post was created as part of the Creative Challenge for the IA Planning course over https://www.coursera.org/course/aiplan
