0

I am given a set of tourist attractions(nodes identified by x, y) and i need to find the shortest path to visit them.

The way i thought of it, is i will ignore if there are streets available and consider the streets always go the way a segment uniting the two points does. However, i need to find the shortest path through them; is this a correct approach to solving this problem?

From what i have read, i should apply the Traveling Salesman Problem or the Chinese Postman Problem, but i cannot figure out which one is more suitable for my case?

Also, if i am to apply TSP, is it better to go at it with a dynamic approach or a genetic algorithm one? Can you please provide an efficient implementation, if possible, as i have found only few resources and i am uneasy as to their efficiency.

  • 6
    The point of someone pointing out the Traveling Salesman Problem is to point out that there is no efficient, general purpose solution to your problem. The best you can get is a somewhat efficient short path which might be the shortest (or an exceptionally slow shortest path via brute force - unless your graph is too big, in which case it is too slow to finish in your lifetime). – Telastyn Dec 21 '14 at 14:58
  • i will have less than 50 nodes, i think, but i would like this to be as efficient as possible...so, TSP is the way to go at this, and you are suggesting brute force instead of a genetic algorithm? – SummerCode Dec 21 '14 at 15:01
  • 2
    Even 50 nodes is probably too much to brute force. – Telastyn Dec 21 '14 at 15:06
  • 1
    Does your task have a requirement to not visit vertices and edges more then once ? If no, you can look at minimal spanning tree for the graph. – Dzhambulat Khasayev Dec 21 '14 at 17:50
  • 1
    @SummerCode it is still equivalent to the TSP. The route A-B-A-C could be considered to be the route A-B-(AC) where the cost to go to C backtracking through A from B exists with a given cost. Thus, the issue of the exact solution to a TSP variation is still answered by the duplicate that Jim G. found. – user40980 Dec 22 '14 at 4:28
1

I won't present an efficient algorithm.

Not the answer you're looking for? Browse other questions tagged or ask your own question.