Shortest path to visit all nodes [duplicate]

Question

This question already has answers here:

Algorithm for an exact solution to the Travelling Purchaser Problem (3 answers)

Closed 5 years ago.

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.

Answer 1

I won't present an efficient algorithm.

• You may have a look at zero-supressed decision diagrams (ZSDD / ZDD) to enumerate all paths and represent every path in a compact form.
• Zero-Suppressed BDDs for Set Manipulation in Combinatorial Problems by Shin-ichi Minato (NTT LSI Laboratories)

• since you now have a compact representation you can search for the minimal solution more efficient.

• You may have a look Donald Ervin Knuth's book 'The Art of Computer Programming. Volume 4.a' Chapter 7.1.4 which focusses on this topic.