Forum: Ruby on Rails Travel Salesman Problem

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
F3f27949240208ffe170ff8ba6abe6ea?d=identicon&s=25 Arthur Chan (arthurccube)
on 2009-04-27 14:46
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
6104d7bae8b16958edd24343c8677204?d=identicon&s=25 Robert Anderson (Guest)
on 2009-04-27 14:49
(Received via mailing list)
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@hotmail.com

"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 <
407016c9d4109e726fc30681b21324cc?d=identicon&s=25 Jarl Friis (jarl)
on 2009-04-27 16:05
(Received via mailing list)
Robert Anderson <ranomail@gmail.com> 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
6104d7bae8b16958edd24343c8677204?d=identicon&s=25 Robert Anderson (Guest)
on 2009-04-27 16:06
(Received via mailing list)
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@hotmail.com

"Ausência de evidência não é evidência de ausência." (Carl Sagan)
F3f27949240208ffe170ff8ba6abe6ea?d=identicon&s=25 Arthur Chan (arthurccube)
on 2009-04-28 04: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 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@hotmail.com
>
> "Ausência de evidência não é evidência de ausência." (Carl Sagan)
407016c9d4109e726fc30681b21324cc?d=identicon&s=25 Jarl Friis (jarl)
on 2009-04-28 09:31
(Received via mailing list)
Arthur Chan <rails-mailing-list@andreas-s.net> 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
This topic is locked and can not be replied to.