Abstract: The traveling salesman problem is a simple problem: given a 2D graph of cities, what is the shortest circuit - the shortest route that visits each city exactly once? The triviality of this task is deceptive: it is, in fact, NP-complete: while many algorithms can produce a very good route, no known method exists of finding the shortest route without some measure of brute-force trial-and-error computation.

This application is an attempt to solve the Traveling Salesman Problem with a novel algorithm of the author's design called SetBuilder. In essence, this algorithm begins by finding small combinations of cities with optimally small distances, concatenates them to build longer partial solutions, and continues the upward concatenation process until it reaches an optimized full solution. While this method does not guarantee the discovery of the best solution, it produces good solutions in relatively short time frames and scales well for larger problems (those with many cities.)

Version: 1.0 - last updated Thursday, June 09, 2005

Links: Download (Contents: Executable (Windows), Source Code (C#))

Screenshots: