Travelling Salesman Problem: Introduction (in Haskell)

Here's the original link.

The task here is a setup for some stochastic methods of solving the Travelling Salesman Problem. I'm doing it in Haskell since my skills here need work.

basic.lhs:

Set up a coordinate string. These are the cities in our routes.

> coordinates :: [(Float,Float)]
> coordinates = [(0,1),(1,2),(2,3),(2,4),(0,6)]

This is a simple function that takes two 'cities' and returns the floating-point distance between them using the Pythagorean Theorem

> distance :: (Float, Float) -> (Float, Float) -> Float
> distance (x1,y1) (x2,y2) = sqrt ((x1-x2)^2 + (y1-y2)^2)

This allows us to determine the actual length of a list of cities ('tour'). Note that it's not circular, unlike in the linked article.

The 'let' statement looks up the city in question from the list above and inserts it into an equivalent list.

zipWith is like map, except it takes a two-argument function, and two lists of arguments which are 'zipped' together into a result list.

> tourLength :: [(Float, Float)] -> [Int] -> Float
> tourLength pairs tour = let coords = map (pairs !!) tour 
>                         in sum $ zipWith distance coords (tail coords)

A wrapper, if you'd like to have all tours be circular.

> tourLength' :: [(Float, Float)] -> [Int] -> Float
> tourLength' pairs tour = tourLength pairs (tour ++ (head tour))

The main testing function, which prints the specified tour's length

> main :: IO ()
> main = print $ tourLength' coordinates [2,1,0,3,4]

One thing you'll notice here, is that I'm eliding the matrix calculation in the original source. One of the nice things about Haskell is that a later date, should I choose to do some memoization, there's very little work to be done. Only one of these functions would need to change.

Another nice thing is that if a given pair of cities is not ever used, Haskell (due to it's laziness) won't ever bother to actually calculate the value, even if I do go back and add memoization.

There's more to this, especially the shuffling functions (I'll get to introduce Monads!). That'll have to wait for another day soon.