Tuesday, June 5, 2007

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.

3 comments:

lilspikey said...

I'll be interested to see how this works in Haskell. I like the idea of the laziness in evaluating the distance matrix, but I suspect it's not going to be of too much use - I'd imagine most values would get used during a reasonable search.

Also bear in mind that for a real world problem the distance matrix will often not be cartesian. It would normally be calculated offline from street level data and loaded whole at the start of a run.

Anyway, good stuff. Looking forward to seeing more.

John

Giles Bowkett said...

+1 on the Cartesian thing. What about a Google Maps mashup?

Jon Harrop said...

Check out the OCaml solution from my book:

http://www.ffconsultancy.com/products/ocaml_for_scientists/complete/

It also uses laziness as an optimization.

Cheers,
Jon.