Hacker News Reader

Comment by bertil | Hacker News Reader

I’m confused: how is “walk-straight ahead” not an obvious best solution? It’s minimum performance is null, average performance, half of the diameter of any (compact) shape, and worst, the diameter. Is the problem implicitly with infinite distance, multiple dimention or fractal?

View on HN

You may have misread the problem.

Consider a forest that is 1000km long but only 1km wide, it is possible that "walk straight ahead" has a worst case of 1000km. But the strategy of "walk 1.5km, turn 90 degrees, walk 1.5km" has a worst case of 3km and is guaranteed to get you out of the forest (and I'm sure there are better strategies).

The optimal strategy in this case is known and is called the Zallager curve. See http://www.wardsattic.com/joomla/Download/WebPresentation/za... for a picture.

So you’re not too far off: the optimal value is 2.27.

Apparently you've mistyped the name - the curve is named after a Russian-Israeli mathematician Viktor Zalgaller.

What happens for a 1 : 1.1 rectangle? it seems to me that that curve isn't optimal then. If so, what is the ratio for a rectangle where that curve becomes optimal.

If I'm reading http://wardsattic.com/joomla/Download/BellmanForestProblem.p... correctly, the ratio you're looking for is ≈ 2.0471.

thanks for the link!

That paper shows the value of visualization... I followed the Bellman Forest Problem link to the Wikipedia page on the Moser's Worm Problem[1] and it didn't do anything for me.

In Ward's paper, he summarized Moser's Worm Problem differently (p.7):

In 1966, Moser posed a related problem which roughly asks: “What's the best-shaped hammer for smashing one-inch worms?”

Great visualization!

[1] https://en.wikipedia.org/wiki/Moser%27s_worm_problem

In particular, the problem is to find a path that minimises the worst case (ie, which path minimises the time to hit the forest border over all possible starting locations and orientations within the forest).

The shape and size of the forest is known. If you know that the forest is long and thin, you're better off walking in a curved path so that you're guaranteed to hit the "side" of the forest rather than walking straight and potentially continuing until you hit the "end".

If you know the dimensions, you know that if you walked more then the width , then you have to make a left or right turn.

Yes, but you can optimize it even further by following a curve.

walking a in side leaning curve minimizes mean total walked distance over all possible cases

What if the shape is the set of all finite curves arranged as a star and given equal length?

If you accidentally start in the middle, there will always be a worst case scenario route determined for any arbitrary curve and no way to pick between curves to find the best one.

Isn't that set a circle?

Yes, and the solution for a circle of radius r is easy(going straight, you don't need to walk more than 2r; if you turn anywhere, you risk walking more than that).

Bellman put exact knowledge of the shape of the forest in the problem statement to make it nontrivial and therefore more difficult.

Walk straight ahead could be worst case if you are near the edge and oriented to walk all the way across the width of the forest.

Reply on news.ycombinator.com