Well, I would respectfully point out that is not a "solution" to finding an optimal path, and it is not a "travelling salesman" solution. If what you want is a path through all stumps that takes considerably longer than an approximately optimal solution well, OK, then it's a "solution." Example: Open the map and look at the path through stumps 100, 101, 102, 103, 104. It's a gross error to not visit stump 155, which is next to 102, but instead to defer that to an extremely long detour later on. The route calculated is full of such gross inefficiencies, jumping back and forth in zig zags over long distances. Another example is how stumps 179 and 178 are next to 37, but are ignored in favor of a very inefficient detour later on. 166 and friends next to 92 is a another example. Zig zags, above Tasks that are NP-hard are NP-hard because they are difficult to do. Finding an optimal path through many points is NP-hard. In contrast, if you don't care that you'll be rushing around with a lot of unnecessary travel, finding a non-optimal path is trivially easy. The computed route runs very quickly because it is not, repeat not, a travelling salesman solution. I'm surprised they call it that since it clearly is wildly inoptimal. To see what I mean, load the stumps into Release 8 and do a Spanning Tree. You can see how that Spanning tree with some manual editing by eye done in 9 will result in a significantly shorter overall path than the very zig zag path. Above: Spanning tree on stumps, done in 8 There is no general solution to NP-hard problems which is not NP-hard. That's a non-negotiable consequence of mathematics which people understandably don't like, but it is what it is and there is no getting around it. Second best are approximate solutions. But those are not usually "one size fits all" because they tend to be highly situation dependent: what makes sense driving a tractor across raw terrain isn't likely the same that makes sense within a constrained road network for taxis. That's why so many routing "solutions" are basically technical hints augmented by human know-how / common sense. Build a spanning tree, use that as a guide and the guy piloting the tractor makes decisions on the fly. It's often like that for vehicle navigation as well, where a savvy cab driver takes the computed route as a guide, while making actual course decisions on the fly based on local knowledge and perception. Attachments: spanning_tree.png zig_zags.png
|