Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hello

I am trying to solve a problem involving a cross-country ski trail map. I wish to travel every trail on the map, at least once, but no more than twice (so I can out-and-back on a destination, for example).

I don't believe this is a TSP problem, as TSP seems to be point oriented (ensuring all points on a map are visited in the shortest path possible), whereas I am looking to visit all paths, in the shortest route possible.

Is there an existing algorithm that could be implemented? Am I overthinking it?

I'm not a math major/minor. I get math, at a university level, but it's not my field of study. Please excuse my lack of knowledge! :)

Thanks in advance.

share|improve this question
add comment

2 Answers

up vote 4 down vote accepted

Look up Chinese postman problem. This can be done if and only if your graph is connected.
Assuming you want to start and end at the same point, you look at the vertices of odd degree and find a minimum-cost perfect matching (where the cost is distance in the graph). Each edge of the graph that is on the shortest route between two matched vertices will be traversed twice: after doubling these edges, you have a connected graph where each vertex has even degree, and you take an Eulerian cycle in that graph.

share|improve this answer
add comment

Pick a spanning tree of the ski trail map, e.g. by depth-first search or something. You can traverse it by always turning left at a junction. As you're doing this, walk out and back along each edge that's not in the tree. This uses each edge exactly twice.

share|improve this answer
    
But the OP is looking for the shortest route possible, so the hope is to traverse some of the edges only once, and indeed to maximize the total length of the edges that are traversed only once. –  Andreas Blass Mar 17 '13 at 20:02
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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