bjornson’s blog

this blog is very young, come again to watch it grow

Archive for the ‘Heuristic’ tag

Visualisation of heuristics to solve the Travelling Salesman Problem (TSP) in Flash

with 14 comments

This little Flash application implements four heuristics to solve the Travelling Salesman Problem:

This movie requires Flash Player 9

How to use this application:

Type in the number of nodes and press build to set them up randomly (now max. 300 nodes).

Then you can test the different heuristics by clicking on the buttons in the top area. To hide a solution you can click the button again.

To set the nodes up differently, press build again.

NEW functionalities: Now you can edit the nodes and add new ones. Snap to grid and let the application show each step of the process.

Please comment if you are interested in some additional functionalities.

Download the AS3 Class now here. It is licensed under the Creative Commons Attribution 3.0 License. This allows you to use this class in personal and commercial products but you need to leave my name and link in the class, which is actually not seen by anyone after you publish the file. It would be nice to receive an html link, but it is not required.

To use this class do the following:

Unzip the class into the your class root folder (usually you can use the folder your .FLA file resides in). In your FLA import the class, create an object of the TSP class with an adjacency matrix. Call one of the four heuristics to receive a route array. Add the withHistory flag as true to receive the unfinished routes as well.

  1. import bjornson.Algos.TSP;
  2. var myTSP:TSP = new TSP(matrix);
  3. var nextNeighbour:Array = myTSP.returnNextNeighbour();
  4. var nearestInsertion:Array = myTSP.returnNearestInsertion();
  5. var farthestInsertion:Array = myTSP.returnFarthestInsertion();
  6. var cheapestInsertion:Array = myTSP.returnCheapestInsertion();

Now you can use the found path in any way you like. For example simply trace one:

trace(“Route found by cheapest insertion heuristic: “+cheapestInsertion.toString());

An adjacency matrix is simply a two-dimensional array containing the distances from each node to every other node. For example a small matrix containing only three nodes can look like this:

var matrix:Array = new Array( new Array( 0 , 1 , 2 ), new Array( 1,  0 , 3 ), new Array( 2 , 3 , 0 ));

At the moment only symmetric matrices can be used.

Written by bjornson

September 12th, 2008 at 8:41 am