Hi Guys,
I am going to solve the Travel Salesman problem:
I wanna find out the shortest path to visit all cities in my site.
But… I don’t know even where to start for it… (I am able to find out
any distance between two cities.)
Any clue?
Arthur
Start here:
Regards,
–
Robert A. Nogueira de Oliveira
Tribunal de Justiça do Estado de Sergipe
Graduando em Sistemas de Informação - UNIT
MSN: [email protected]
“Ausência de evidência não é evidência de ausência.” (Carl Sagan)
On Mon, Apr 27, 2009 at 9:46 AM, Arthur C. <
Robert A. [email protected] writes:
- (*) text/plain ( ) text/html
Start here:
This algorithm finds shortest path from initial node to goal node. TSP
(Traveling SalesMan) is aobut visiting all nodes in a graph.
Solving the TSP problem is not one of these problems for which there
eists a well known best algorithm. It belongs to the class NP [1],
well actuall it is known to be NPC [2], but you have read the section
regarding “Solving NP-complete problems” I suggest you read something
about branch-and-bound algorithms[3], and eventually use the A* search
algorithm as part of your BnB implementation.
Jarl
Footnotes:
[1] NP (complexity) - Wikipedia
I said start here, no finish here 
–
Robert A. Nogueira de Oliveira
Tribunal de Justiça do Estado de Sergipe
Graduando em Sistemas de Informação - UNIT
MSN: [email protected]
“Ausência de evidência não é evidência de ausência.” (Carl Sagan)
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.
Thanks again.
Robert A. wrote:
I said start here, no finish here
–
Robert A. Nogueira de Oliveira
Tribunal de Justiça do Estado de Sergipe
Graduando em Sistemas de Informação - UNIT
MSN: [email protected]“Ausência de evidência não é evidência de ausência.” (Carl Sagan)
Arthur C. [email protected] writes:
Thanks guys,
I kinda understood the basic idea of the TSP. i wanna do something like
heuristic functions. Or, something like:Itinerary for a Traveling Salesman (#142) - Ruby - Ruby-Forum
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
error (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] P versus NP problem - Wikipedia