Arthur C. removed_email_address@domain.invalid writes:

Thanks guys,

I kinda understood the basic idea of the TSP. i wanna do something like

heuristic functions. Or, something like:

http://www.ruby-forum.com/topic/127031#new

I don’t know if the “grid” method mentioned is applicable for general

TSP.

It is not. It is only applicable to the special case TSP (points are

on a euclidean grid) mentioned there. Secondly the method does not

find optimal solution. Both of these limitations are mentioned on the

web-page.

Let me remind you, if you find a polynomial time algorithm for solving

the general TSP problem, you have prooved that P=NP[1] and thereby

solved one of the seven millenium Prize Problems[2] and you will be

rewarded US$1,000,000. So get used to it: “There is no easy way”.

So my suggestion is to analyse what you really need to solve! your

problem may very well be a special case TSP, for which there is a

polynomial algorithm. Secondly in practise you may not need the

optimal solution, just a very good solution. Could you ellaborate on

your real problem.

If that is not the case and you really need to solve TSP. you may

investigate state-of-the-art implementations on

http://www.research.att.com/~dsj/chtsp/ (I belive most of them are

some kind of branch-and-bound algorithm), the page may seem old, but

as you may have guessed, TSP is not called a “millenium” problem for

nothing

Jarl

Footnotes:

[1] http://en.wikipedia.org/wiki/P_=_NP_problem

[2] http://en.wikipedia.org/wiki/Millennium_Prize_Problems