Using Hilbert Curves to 100% Zelda

Re:Using Hilbert Curves to 100% Zelda by Retric on Saturday July 22, 2017 @11:53PM (#14830818)

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.

[ Parent | on HN ]

Re:Using Hilbert Curves to 100% Zelda by modalduality on Sunday July 23, 2017 @12:03AM (#14830849)

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?

[ Parent | on HN ]

Re:Using Hilbert Curves to 100% Zelda by Retric on Sunday July 23, 2017 @02:33PM (#14833674)

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?

[ Parent | on HN ]

Re:Using Hilbert Curves to 100% Zelda by Spivak on Sunday July 23, 2017 @12:27AM (#14830894)

So say you have a graph on distance, d, that you want to weight based on a preference, p, from 0-5 going from least preferred to most preferred.

You might make your weight function as w(d, p) = d * (2 ^ p)

[ Parent | on HN ]

Re:Using Hilbert Curves to 100% Zelda by modalduality on Sunday July 23, 2017 @01:52AM (#14831058)

That's fine, but `p` is a variable, not a constant, in the original post's case, right?

[ Parent | on HN ]

Re:Using Hilbert Curves to 100% Zelda by tgb on Sunday July 23, 2017 @05:32AM (#14831538)

That doesn't seem necessary. Picking a value of p just selects how much you prefer short hope to shorter total distance.

[ Parent | on HN ]