Sunday, February 24, 2013

Touring in Brazil


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.

Your browser is completely ignoring the <APPLET> tag!

This post was created as part of the Creative Challenge for the IA Planning course over https://www.coursera.org/course/aiplan