The Traveling Salesman

Submitted By:
david

Difficulty:
Medium

Tags:
genetic programming

Instructions:
Willy Lomax just got a new job and for his first assignment, he'll be traveling to a bunch of cities. He's graphed it out on a cartesian plan. Assuming he's currently at (0,0), help him save money by finding the shortest route which passes through all cities and returns him to (0, 0).

Code:
cities = [[1, 2], [3, 4], [8, 7], [10, 12], [2, 4]]

___

tsp = TSP.new(cities)
answer_route = [[3, 4], [8, 7], [10, 12], [2, 4], [1, 2]]
assert_equal tsp.dist.round(2), 32.00
assert_equal (tsp.route == answer_route || tsp.route == answer_route.reverse), true

# second check
cities = [[1,1], [8,4], [10, 11], [4, 5], [3,3], [5,6], [3,2]]

tsp = TSP.new(cities)
answer_route = [[1, 1], [3, 3], [4, 5], [5, 6], [10, 11], [8, 4], [3, 2]]
assert_equal tsp.dist.round(2), 31.23
assert_equal (tsp.route == answer_route || tsp.route == answer_route.reverse), true

Your Solution

Ruby 1.9.3

Back to Problems