On Thu, Feb 14, 2002 at 10:20:01AM -0500, Greg London wrote: > Does anyone know of a perl module that solves the "traveling salesman" > problem? > > Given a number of addresses, find the shortest path that covers all > the destinations. > > Part two of the problem would have multiple salesmen and a slew of > addresses, and the program would need to figure out the best route for > each salesman that covers all destinations.
I don't know of Perl implementations. Here's a C implementation: http://www.alumni.caltech.edu/~dank/ftp/tsp.c and there are many others out there, but everything you'll find uses heuristics. It's a NP complete problem. I've seen dynamic programming and genetic algorithm approaches to it as well, besides heuristic ones. Ted
