Re: Traveling Salesman
- To: mathgroup at smc.vnet.net
- Subject: [mg35513] Re: [mg35497] Traveling Salesman
- From: Rob Pratt <rpratt at email.unc.edu>
- Date: Wed, 17 Jul 2002 02:09:04 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
On Tue, 16 Jul 2002, Nathan Given wrote:
> I am looking for some help with the Traveling Salesman problem.
>
> I have one matrix that has the distances in miles between cities, it
> looks like this...
>
>
> [0 1 3 4]
> [1 0 2 6]
> [3 2 0 5]
> [4 6 5 0]
>
> Now, how do I use the traveling salesman algorithm in mathematica to
> help me with this?
>
> (I am new to mathematica)
>
> Thus far, here is what I have accomplished...
>
> << DiscreteMath`Combinatorica`
dist = {{0, 1, 3, 4}, {1, 0, 2, 6}, {3, 2, 0, 5}, {4, 6, 5, 0}}
g = Graph[dist, Range[4]]
TravelingSalesman[g] returns {1, 2, 3, 4, 1}, which is a tour of minimum
length.
Rob Pratt
Department of Operations Research
The University of North Carolina at Chapel Hill
rpratt at email.unc.edu
http://www.unc.edu/~rpratt/