Hi Guys, I am going to solve the Travel Salesman problem: http://en.wikipedia.org/wiki/Travelling_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

on 2009-04-27 16:46

on 2009-04-27 16:49

Start here: http://en.wikipedia.org/wiki/A*_search_algorithm Regards, -- Robert A. Nogueira de Oliveira _________________________ Tribunal de JustiÃ§a do Estado de Sergipe Graduando em Sistemas de InformaÃ§Ã£o - UNIT MSN: removed_email_address@domain.invalid "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. <

on 2009-04-27 18:05

Robert A. <removed_email_address@domain.invalid> writes: > 1. (*) text/plain ( ) text/html > > Start here: > > http://en.wikipedia.org/wiki/A*_search_algorithm 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] http://en.wikipedia.org/wiki/NP_(complexity) [2] http://en.wikipedia.org/wiki/NP-complete [3] http://en.wikipedia.org/wiki/Branch_and_bound

on 2009-04-27 18:06

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: removed_email_address@domain.invalid "AusÃªncia de evidÃªncia nÃ£o Ã© evidÃªncia de ausÃªncia." (Carl Sagan)

on 2009-04-28 06:00

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: removed_email_address@domain.invalid > > "AusÃªncia de evidÃªncia nÃ£o Ã© evidÃªncia de ausÃªncia." (Carl Sagan)

on 2009-04-28 11:31

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