Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Using Hilbert Curves to 100% Zelda

blog.merovius.de

Post reply on HN
Print view View original

51–60 of 65 posts

Re: Using Hilbert Curves to 100% Zelda

#51

Post by nwjtkjn »

cbhl wrote: post #15
nwjtkjn wrote: post #9

Why is the Hilbert Curve any better in this situation than say lexicographical order on (x,y)?

It's pretty easy to imagine a counter-example that would have you traverse the length of the map, when the best route would be to detour on an existing traversal. Consider: 1...2...3...4...5 7...............6 8.......9........ 13..12.....11..10 versus 1...2...3...4...5 13..............6 12......9........ 11..10......8...7

Good point, though I'm not convinced Hilbert really avoids this. For example, look at n=3 here:

http://www.texample.net/media/tikz/examples/PNG/hilbert-curv...

This might lead to say

. . . . . . . .

1 . . . . . . 2

4 . . . . . . 3

. . . . . . . .

when

. . . . . . . .

1 . . . . . . 4

2 . . . . . . 3

. . . . . . . .

is more efficient.

Generally speaking, it seems this is basically TSP.

Re: Using Hilbert Curves to 100% Zelda

#53

Post by tedunangst »

nwjtkjn wrote: post #50
tedunangst wrote: post #14

Earlier quoted context omitted.

It's a long walk from (1, 10) to (2, 1).

Yeah sorry I meant like snaking back and forth, which you're right is not the same as pure lexicographic.

Yeah, the length of such a snake is equal to the Hilbert curve.

Re: Using Hilbert Curves to 100% Zelda

#54

Post by drostie »

Xcelerate wrote: post #48
ufo wrote: post #3

> There might also be better approaches than Hilbert Curves. For example, we could view it as an instance of the Traveling Salesman Problem with a couple of hundred points; it should be possible to have a good heuristic solution for that. On the other hand, a TSP solution doesn't necessarily only have short jumps, so it might not be that good? TSP is actually very amenable to heuristics and state of the art branch-an…

> TSP is actually very amenable to heuristics and state of the art branch-and-bound algorithms can often find optimal solutions even for instances with thousands of points. In own research (inverse problems related to signal recovery), I've noticed that a lot of NP-hard problems are actually easily solvable given that the data has some kind of structure to it. I know very little about computational complexity theory,…

That's very unlikely to be true in general, as the proofs that a problem lives in NP usually have a very high signal-to-noise ratio -- i.e. in order to prove that solving this problem is at least as hard as solving an arbitrary boolean circuit, we need to find a subset of the problem which behaves like wires and boolean gates do, and the resulting "circuits" are very heavily structured.

Re: Using Hilbert Curves to 100% Zelda

#55

Post by [deleted] »

Xcelerate wrote: post #48
ufo wrote: post #3

> There might also be better approaches than Hilbert Curves. For example, we could view it as an instance of the Traveling Salesman Problem with a couple of hundred points; it should be possible to have a good heuristic solution for that. On the other hand, a TSP solution doesn't necessarily only have short jumps, so it might not be that good? TSP is actually very amenable to heuristics and state of the art branch-an…

> TSP is actually very amenable to heuristics and state of the art branch-and-bound algorithms can often find optimal solutions even for instances with thousands of points. In own research (inverse problems related to signal recovery), I've noticed that a lot of NP-hard problems are actually easily solvable given that the data has some kind of structure to it. I know very little about computational complexity theory,…

[deleted]

Re: Using Hilbert Curves to 100% Zelda

#56

Post by brians »

decafb wrote: post #33

For reference: The generic name what op does is "spatial indexing". There is an algorithm for efficiently working with such data called Hilbert R-tree ( https://en.wikipedia.org/wiki/Hilbert_R-tree ). But there are alternatives (see https://en.wikipedia.org/wiki/Spatial_database ). Many databases nowadays contain functions to these operations (e.g. https://dev.mysql.com/doc/refman/5.7/en/spatial-analysis-fun... )

They can even be explained to a surprisingly low tech operator, with pre-calculation at a high tech level: http://www2.isye.gatech.edu/~jjb/research/mow/mow.pdf

Re: Using Hilbert Curves to 100% Zelda

#57

Post by Retric »

modalduality wrote: post #20
Retric wrote: post #19

Earlier quoted context omitted.

If you want to minimize the long distance walks add an exponential weight for distance then solve. There are many ways to go about this stuff, but the goal is to map your preferences to the weight function.

Right, but then the problem is no longer linear and approximating is more difficult. I'm not exactly sure what you mean by "exponential weight" in a linear program, do you have an example?

I am not sure what your asking? Your just assigning constants for weights on each trip a>b = K1, a>c = K2.

I am saying you may map K1 as √((x1-x2)^2+(y1-y2)^2) to find least distance, but TSP allows for arbitrary constants. So remove the √ and long trips will be strongly avoided.

PS: As far as I know you can use any arbitrary set of constants then use a linear solver. Or am I forgetting about something?

Re: Using Hilbert Curves to 100% Zelda

#59

Post by hidal »

nwjtkjn wrote: post #51
cbhl wrote: post #15

Earlier quoted context omitted.

It's pretty easy to imagine a counter-example that would have you traverse the length of the map, when the best route would be to detour on an existing traversal. Consider: 1...2...3...4...5 7...............6 8.......9........ 13..12.....11..10 versus 1...2...3...4...5 13..............6 12......9........ 11..10......8...7

Good point, though I'm not convinced Hilbert really avoids this. For example, look at n=3 here: http://www.texample.net/media/tikz/examples/PNG/hilbert-curv... This might lead to say . . . . . . . . 1 . . . . . . 2 4 . . . . . . 3 . . . . . . . . when . . . . . . . . 1 . . . . . . 4 2 . . . . . . 3 . . . . . . . . is more efficient. Generally speaking, it seems this is basically TSP.

I think is TSP only if you start by the first point in the ordered list. If you start any other point, you will be going in only one direction (top-bottom/left-right or bottom-top/left-right) (See how the space is filled)

Re: Using Hilbert Curves to 100% Zelda

#60

Post by CamperBob2 »

amalcon wrote: post #42
CamperBob2 wrote: post #8

Earlier quoted context omitted.

TSP is actually very amenable to heuristics and state of the art branch-and-bound algorithms can often find optimal solutions even for instances with thousands of points. With that many points, how do you prove that your solution is optimal?

TSP (in the traditional sense of finding an optimal solution) is NP-complete, so (by definition of NP-complete) it's much easier to check a proposed correct answer than to find that answer.

Hmm. So there's a polynomial-time method for verifying that you've found the shortest path in TSP, but not for finding it in the first place?
Post reply on HN