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.

Improve this question
6
  • 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, 2014 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, 2014 at 15:01
  • 2
    Even 50 nodes is probably too much to brute force.
    – Telastyn
    Dec 21, 2014 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, 2014 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, 2014 at 4:28

1 Answer 1

Reset to default
1

I won't present an efficient algorithm.

Improve this answer

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