There are some local conservation areas that have networks of trails with multiple branch points, lollipop loops, and other complexities. I like to try to cover every section of trail while minimizing the amount of doubling back that I need to do, and finding the shortest possible total distance. I think that my practically-derived solutions are pretty good, but I’d like to know if they are really optimal. As a math problem, this is somewhere between the 7 bridges problem and the traveling salesman problem. I want to cover every foot of trail in the shortest possible distance. I assume that this covers the ‘least possible amount of covering the same trail twice’, but if not I want that to be a criterion as well.
My question is whether there is some simple way to determine what the optimal path for covering a given trail network under these conditions. Is this a feature of Google Maps or some trails website, for example? Is there a place that I can upload line art of the network and get an answer? An Excel routine that calls for connectivity data and distances? I’m less interested in a theoretical answer and more interested in a ‘input your data here’ answer.
By that, do you mean the least number of times doubling back / using the same trail twice? Because it seems to me that if the criterion is the least amount of mileage using the same track you’ve used before that that would match the optimal length solution.
I would like to minimize the distance of using the same trail twice. Consider the Greek letter theta: ϴ. To cover that completely I would walk the crossbar twice rather than the upper or lower arcs twice because the crossbar is the shortest segment. I’m not concerned about the number of doubled segments, but rather the length of doubled segments.
Consider it as a psychology problem too: I hate doing laps, because it feels like wasted effort to cover the same ground more than once. That’s exercise, which I don’t want to do. I am a lazy adventurer who wants to see everything there is to see while walking the least and spending as little time as possible looking at things I’ve already seen.
Perhaps to aid in your search what you are doing is called ‘red lining’ the trails, which means hiking every trail in an area. It comes from keeping track of one’s progress on a paper map with a red highlighter/marker.
With a couple minutes thinking, I’m pretty sure that ‘minimize total distance’ and ‘minimize distance walked twice’ are equivalent.
I can’t think of any plug and play solutions, or way to do it in Excel, but it’s a one-hour programming task in any language to just check all the possible routes and find the shortest one (it would take too long to run with millions of paths, but for your group shouldn’t take long).
If you know anyone who can do basic programming (seriously, this is a CS101 or high-school class level), see if a six-pack is a good enough bribe for them to write this for you. You’ll have to type up the trail data in whatever form they want, since that’s the boring part.
Thanks; I hadn’t heard that term before. To add a wrinkle: what if I want to find the longest path in a trail system that has no doubled paths? I would accept paths that intersect at a point.
While avoid excess hiking is always an issue, most redliners I’ve hiked with aren’t that concerned about minimizing any particular route. Only the few who’ve set time limits on their redlining project care that much about it.
There is a similar spirited project in my hiking area where there are 48 peaks over 4000’. The Diretissima is a direct, unsupported hike hitting all the peaks. People who have done it spend a great deal of time planning routes, camping spots, etc to get the optimum 7-10 day trip. As far as I know, no two trips have been identical. But optimal route isn’t always the shortest; there are other considerations.
A additional consideration is you might want to avoid a great elevation change, such as your theta example, if the crossbar went over a mountain and the loop went around it 1: It may be preferable to go around then over it 2x 2: it could be shorter taking the loop around then up and over due to the vertical distance, some hiking maps only have flat earth distances.
What you are doing is slightly more complicated than that applet because your edges have weights, but it’s still probably worthwhile to familiarize yourself with this simpler concept.
Do you need to start and stop at the same spot? If you don’t then you can cover ϴ without any retracing by starting at one end of the crossbar and finishing at the other end. You can always cover all the routes with no retracing as long as there are only 2 nodes with an odd number of branches by starting at one and ending at the other (assuming the routes form a map that is not disjoint into separate sub maps).
If you must start and end at the same spot, you can do that with no retracing if and only all nodes have an even number of paths. The proof is rather obvious in that with an even number of paths at a node there is always an unused one to leave by for each time you get there.
So I think your problem consists of looking at the nodes with an odd number of paths and using twice the shortest path connecting it. I think the only complications is if there are two (or more) directly connected nodes each with an odd number of paths.
Write down all pairings of these odd-degree vertices. For example, if there are four odd-degree vertices A, B, C, and D, then there are three pairings: (AB)(CD), (AC)(BD), and (AD)(BC).
For each of these pairings, find the shortest distance to travel between each pair. Add up all of the distances; that’s the “score” of each pairing.
Find the pairing with the lowest score. Draw a new edge between each of the pairs, paralleling the shortest path between them.
The graph with the new edges now has an Eulerian cycle, à la the Bridges of Königsburg, and it will be pretty easy to find it.
I also found this nifty applet, which would be exactly what you need except that it uses directed edges rather than undirected edges. I don’t see an easy way to kludge it so that it solves the undirected problem. (And before you ask: if you connect all adjacent vertices with two directed paths, one in each direction, then it assumes that you want to walk each path in both directions, and creates a tour that does so.)
