Space-filling curves as a traveling salesman heuristic is a really nice application I was not aware of. I have mostly seen them in the context of domain decomposition for parallel computing, where you cut the curve at n points to obtain n+1 disjoint domains.
Another benefit I see is that you could quickly generate many heuristic solutions by randomly translating, rotating and/or uniformly scaling the curve, and then choose the best.
It does look like it can produce crossing edges, which are suboptimal in Euclidean space, but these are easy to rectify -- whenever 2 edges cross, just swap their endpoints for a quick guaranteed improvement. Because doing this strictly decreases the total tour length, and every such decrease is lower-bounded by the smallest such decrease among all (nCities choose 4) possible sets of 4 cities, repeatedly doing this must eventually terminate in a crossing-free tour.
That's the missing part in the article. The example of the TSP solution for all cities in Germany was a pretty poor one compared to the optimal, which immediately raises the question: how good is it if you do some simple tricks to improve the heuristic? Some simple global perturbations like you suggested, and then local improvements like swaps to remove crossings, or running it at multiple scales and taking the best result for each region, or whatever.
The space-filling curve approach strikes me as a decent way to get a starting point, not something to use unmodified. But I've no idea whether that's true -- does the structure of such a solution lend itself well to simple iterative improvements or not?
> To target a space-based laser for the Strategic Defense Iniative (commonly known as the "Star Wars" program)
I'm guessing this application would be selecting an ordering to engage multiple simultaneous targets in minimal-ish time - MIRV warheads or missiles launched in a barrage.
Are there higher dimensional analogues and generalization of space filling curves? Space filling surfaces (wrt 3D) or volumes (in 4D). Are they useful in any sense?
A few times I've had an irregular 2D dataset to process and thought "aha, maybe I can be lazy and iterate ordered by a space filling curve coordinates and it'll be more cache effective". But it's never given any improvement. Anyone tried something similar?
Why O(n log n)? I guess I thought that mapping a coordinate to its distance from the start of a space filling curve would be a constant time operation, or rather, it would only be proportional to the number of bits in your coordinate system which is usually ignored in combinatorial analysis.
Because once you have that, you just need to sort simple integers, which you can do in linear time with a radix sort. (Again ignoring bit lengths.)
9 comments
[ 3.0 ms ] story [ 31.7 ms ] threadThis describes an implementation using a Rolodex to plan Meals on Wheels routes.
Another benefit I see is that you could quickly generate many heuristic solutions by randomly translating, rotating and/or uniformly scaling the curve, and then choose the best.
It does look like it can produce crossing edges, which are suboptimal in Euclidean space, but these are easy to rectify -- whenever 2 edges cross, just swap their endpoints for a quick guaranteed improvement. Because doing this strictly decreases the total tour length, and every such decrease is lower-bounded by the smallest such decrease among all (nCities choose 4) possible sets of 4 cities, repeatedly doing this must eventually terminate in a crossing-free tour.
The space-filling curve approach strikes me as a decent way to get a starting point, not something to use unmodified. But I've no idea whether that's true -- does the structure of such a solution lend itself well to simple iterative improvements or not?
I'm guessing this application would be selecting an ordering to engage multiple simultaneous targets in minimal-ish time - MIRV warheads or missiles launched in a barrage.
Because once you have that, you just need to sort simple integers, which you can do in linear time with a radix sort. (Again ignoring bit lengths.)
What am I missing?