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 -- Posted via http://www.ruby-forum.com/.
Start here: http://en.wikipedia.org/wiki/A*_search_algorithm Regards, -- Robert Anderson Nogueira de Oliveira _________________________ Tribunal de Justiça do Estado de Sergipe Graduando em Sistemas de Informação - UNIT MSN: ranophoenix-PkbjNfxxIARBDgjK7y7TUQ@public.gmane.org "Ausência de evidência não é evidência de ausência." (Carl Sagan) On Mon, Apr 27, 2009 at 9:46 AM, Arthur Chan < rails-mailing-list-ARtvInVfO7ksV2N9l4h3zg@public.gmane.org> wrote:> > 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 > -- > Posted via http://www.ruby-forum.com/. > > > >--~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Ruby on Rails: Talk" group. To post to this group, send email to rubyonrails-talk-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org To unsubscribe from this group, send email to rubyonrails-talk+unsubscribe@googlegroups.com For more options, visit this group at http://groups.google.com/group/rubyonrails-talk?hl=en -~----------~----~----~----~------~----~------~--~---
Robert Anderson <ranomail-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> writes:> 1. (*) text/plain ( ) text/html > > Start here: > > http://en.wikipedia.org/wiki/A*_search_algorithmThis 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
I said start here, no finish here :) -- Robert Anderson Nogueira de Oliveira _________________________ Tribunal de Justiça do Estado de Sergipe Graduando em Sistemas de Informação - UNIT MSN: ranophoenix-PkbjNfxxIARBDgjK7y7TUQ@public.gmane.org "Ausência de evidência não é evidência de ausência." (Carl Sagan) On Mon, Apr 27, 2009 at 11:04 AM, Jarl Friis <jarl-VtTiYveqpzg@public.gmane.org> wrote:> > Robert Anderson <ranomail-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> 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)<http://en.wikipedia.org/wiki/NP_%28complexity%29> > > [2] http://en.wikipedia.org/wiki/NP-complete > > [3] http://en.wikipedia.org/wiki/Branch_and_bound > > > > > >--~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Ruby on Rails: Talk" group. To post to this group, send email to rubyonrails-talk-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org To unsubscribe from this group, send email to rubyonrails-talk+unsubscribe@googlegroups.com For more options, visit this group at http://groups.google.com/group/rubyonrails-talk?hl=en -~----------~----~----~----~------~----~------~--~---
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 Anderson wrote:> I said start here, no finish here :) > > -- > Robert Anderson Nogueira de Oliveira > _________________________ > Tribunal de Justiça do Estado de Sergipe > Graduando em Sistemas de Informação - UNIT > MSN: ranophoenix-PkbjNfxxIARBDgjK7y7TUQ@public.gmane.org > > "Ausência de evidência não é evidência de ausência." (Carl Sagan)-- Posted via http://www.ruby-forum.com/.
Arthur Chan <rails-mailing-list-ARtvInVfO7ksV2N9l4h3zg@public.gmane.org> 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