1
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Andreas Blass
    Commented Mar 17, 2013 at 20:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .