Kohonen Self-Organizing Maps.*;

Code Example 4: Travelling Saleman Problem

This example uses a different kind of self-organizing map called an "elastic net" to solve the traveling salesman problem (TSP). Remember that TSP involves finding a route through a group of cities, visiting each city only once, with the shortest total distance travelled.

Normally, a self-organizing map creates multi-dimensional representations of input patterns and clusters them according to distance. An elastic net creates one ring-like representation of input, manipulating the ring's shape according to distance.

Example Results 1

Five cities with coordinates: (7, 2) (12, 5) (9, 10) (5, 10) (2, 5)

I chose this circular arrangement because it's easy to see what the shortest path is.

The algorithm returns:

(7.1, 10.0) (9.0, 10.0) (10.3, 7.8) (12.0, 5.0) (9.0, 3.2) (7.0, 2.0) (4.5, 3.5) (2.0, 5.0) (3.4, 7.4) (5.0, 10.0),

Matching our map above with a path that traverses counter-clockwise, and successfully demonstrates the shortest path.

The results are printed in a long list, and the last line is the final solution we're interested in.

Example Results 2

Five cities with coordinates: (3, 3) (12, 2) (6, 6) (7, 5) (6, 12)

More challenging since it's not a friendly circle.

The algorithm returns:

(11.2, 2.2) (12.0, 2.0) (8.9, 7.1) (6.0, 12.0) (6.0, 9.3) (6.0, 6.0) (7.0, 5.0) (4.7, 3.9) (3.0, 3.0) (3.5, 3.0)

Matching our map above with a path that traverses clockwise, and successfully demonstrates the shortest path.

Again, it's the last line of the results we're interested in.

public void footer() {
About | Contact | Privacy Policy | Terms of Service | Site Map
Copyright© 2009-2012 John McCullock. All Rights Reserved.
}