I'd like to be optimistic, but this is not a problem that has  
satisfactorily solved. Excerpt:

--------
This lack of improvement in TSP guarantees may be something we cannot  
avoid; with current models of computing it may well be that there  
simply is no solution method for the TSP that comes with an attractive  
performance guarantee, say one of the form n**c for some fixed number  
c, that is, n x n x n ... x n, where n appears c times in the  
product.  A technical discussion of this issue can be found in Stephen  
Cook's paper and the Clay Mathematics Institute offers a $1,000,000  
prize for anyone who can settle it.[1]

--------

So it's unlikely you will type it into Google and get pithy Ruby  
solution to a problem that's been around since I was taking CS and  
that was forever ago. The problem is not that you can't solve it for a  
small number of cities using reduction ad absurdum; it's that the  
solution does not scale to larger numbers of cities.

[1]http://www.tsp.gatech.edu/methods/progress/progress.htm


On Apr 27, 2009, at 6:03 AM, Arthur Chan wrote:

> I think it is a super useful post for me, as I am finding TSP solution
> in Ruby!
>
> Anyway, I've looked at the codes, it's related to the grid mentioned.
> Sorry for my lack of knowledge in Math. My problem is finding the
> shortest path among cities in my website, is it possible to apply the
> grid algorithm?
>
> Thanks much!
> -- 
> Posted via http://www.ruby-forum.com/.
>