Traveling-Salesman Example (Bruteforce)
Author: Shmulik London
Euclidean traveling-salesman problem
The problem: given a set of n points in the plane, find
the shortest closed tour that visit them all.
Snapshot of TSPApplet running
About the demonstrating applet
Above is a snapshot of an execution of TSPApplet, the applet is given a
map of several cities and their distances; it tries to approximate the
best path traversing all cities in most naive way: it tosses undefinite
number of pathes, while recording the path with the minimal distance so
far. This is implemented by repeatadly distributing computation-packets,
each tosses several hundred pathes and return the one with the minimal
distance.
Running the example
appletviewer tsp.html
Code
You can look at TSPApplet.java,
TSPComputation.java
and Permutator.java,
for the source code. You can also look at the improved
implementation of the TSP problem by Rivki Spira in the 'Real examples'
section.