NOTE: Due to the fact that the trip does not end at the same place it started and also the fact that every point can be visited more than once as long as I still visit all of them, this is not really a TSP variant, but I put it due to lack of a better definition of the problem.
This problem was originally posted on StackOverflow, but I was told that this would be a better place. I got one pointer, which converted the problem from non-metric to a metric one.
Suppose I am going on a hiking trip with n points of interest. These points are all connected by hiking trails. I have a map showing all trails with their distances, giving me a directed graph.
My problem is how to approximate a tour that starts at a point A and visits all n points of interest, while ending the tour anywhere but the point where I started and I want the tour to be as short as possible.
Due to the nature of hiking, I figured this would sadly not be a symmetric problem (or can I convert my asymmetric graph to a symmetric one?), since going from high to low altitude is obviously easier than the other way around.
Since there are no restrictions regarding how many times I visit each point, as long as I visit all of them, it does not matter if the shortest path from a to d goes through b and c. Is this enough to say that triangle inequality holds and thus I have a metric problem?
I believe my problem is easier than TSP, so those algorithms do not fit this problem. I thought about using a minimum spanning tree, but I have a hard time applying it to this problem, which under the circumstances, should be a metric asymmetric directed graph?
What I really want are some pointers as to how I can come up with an approximation algorithm that will find a near optimal tour through all n points