-2

I was wondering if somebody could explain me how to apply the approximate algorithm to a 5-vertex matrix. The solution is as follows: 2-3-5-1-4-2

What I'm not sure is how do I choose the next set

Matrix: (Notice is symmetric)

    T1  T2  T3  T4 T5
  ------------------
T1| -   3   2   4   3
T2| 3   -   4   5   5
T3| 2   4   -   4   4
T4| 4   5   4   -   6
T5| 3   5   4   6   -
flag
There are several approximate algorithms for the TSP; which one do you mean? – Michael Lugo Mar 14 2010 at 0:22
The approximate Traveling Salesperson Tour construction (approximate algorithm) OR also called Quick Traveling Salesperson Construction – Mike Mar 14 2010 at 0:30
I'm trying to follow the following PPT (starting slide 15) academics.smcvt.edu/jellis-monaghan/combo2/… – Mike Mar 14 2010 at 0:34
Not sure why this is appropriate for MO. The heuristic appears to be a greedy extension method via the nearest neighbor. – Suresh Venkat Mar 14 2010 at 2:16
Wow, the good ol' Salesman has been PC-upgraded into a person now? – Mariano Suárez-Alvarez Mar 15 2010 at 17:01

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.