Travel Salesman Problem

rubyonrails-talk
1

Start here:

http://en.wikipedia.org/wiki/A*_search_algorithm

Regards,

2

Robert Anderson <ranomail@gmail.com> writes:

1. (*) text/plain ( ) text/html

Start here:

A* search algorithm - Wikipedia

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

[2] NP-completeness - Wikipedia

[3] Branch and bound - Wikipedia

3

I said start here, no finish here :slight_smile:

4

Thanks guys,

I kinda understood the basic idea of the TSP. i wanna do something like heuristic functions. Or, something like:

I don't know if the "grid" method mentioned is applicable for general TSP.

Thanks again.

Robert Anderson wrote:

5

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:

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 :slight_smile:

Jarl

Footnotes: [1] P versus NP problem - Wikipedia

[2] Millennium Prize Problems - Wikipedia