The Travelling Salesman
Added October 2008
This program can be run in Ruby, and as far as I understand, as long as you have a lot of time on your hands, you can have it search through an infinite amount of cities, and find the fastest route. You simply add in the cities at the declaration point at the top, from lines 4-13.
@distances = [
{:city1 => "A", :city2 => "B", :distance => 7},
{:city1 => "A", :city2 => "C", :distance => 4},
{:city1 => "A", :city2 => "D", :distance => 10},
{:city1 => "A", :city2 => "E", :distance => 2},
{:city1 => "B", :city2 => "C", :distance => 5},
{:city1 => "B", :city2 => "D", :distance => 11},
{:city1 => "B", :city2 => "E", :distance => 6},
{:city1 => "C", :city2 => "D", :distance => 9},
{:city1 => "C", :city2 => "E", :distance => 3},
{:city1 => "D", :city2 => "E", :distance => 8}]
You basically write in the distances in the same way, specifying the first city, then the second city, then the distance between the two. If you have included all distances in the right format and included every possibility, then it will spit out every instance of a cycle in which the shortest path takes place (ex: ABCDE is the same distance as BCDEA, so they will both be returned).
Once you are ready to run the program, type in the following commands:
irb(main):001:0> load "any_city_tsp.rb"
And it will return a full cycle, then the distance, for as many cycles exist with the minimum distance.
