Bellman's lost in a forest problem

Re:Bellman's lost in a forest problem by bertil on Sunday September 16, 2018 @08:01PM (#18002070)

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?

[ Parent | on HN ]

Re:Bellman's lost in a forest problem by gamegoblin on Sunday September 16, 2018 @08:11PM (#18002117)

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).

[ Parent | on HN ]

Re:Bellman's lost in a forest problem by btilly on Sunday September 16, 2018 @08:17PM (#18002145)

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.

[ Parent | on HN ]

Re:Bellman's lost in a forest problem by dunkelheit on Monday September 17, 2018 @03:06AM (#18003785)

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

[ Parent | on HN ]

Re:Bellman's lost in a forest problem by rocqua on Monday September 17, 2018 @03:44AM (#18003925)

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.

[ Parent | on HN ]

Re:Bellman's lost in a forest problem by pwiecz on Monday September 17, 2018 @05:07AM (#18004260)

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

[ Parent | on HN ]

Re:Bellman's lost in a forest problem by gvb on Monday September 17, 2018 @08:53AM (#18005440)

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

[ Parent | on HN ]

Re:Bellman's lost in a forest problem by rocqua on Monday September 17, 2018 @07:36AM (#18004896)

thanks for the link!

[ Parent | on HN ]

Re:Bellman's lost in a forest problem by saagarjha on Monday September 17, 2018 @12:57AM (#18003314)

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

[ Parent | on HN ]

Re:Bellman's lost in a forest problem by FabHK on Monday September 17, 2018 @05:50AM (#18004450)

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).

[ Parent | on HN ]

Re:Bellman's lost in a forest problem by cperciva on Sunday September 16, 2018 @08:07PM (#18002091)

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".

[ Parent | on HN ]

Re:Bellman's lost in a forest problem by paulpauper on Sunday September 16, 2018 @08:12PM (#18002119)

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.

[ Parent | on HN ]

Re:Bellman's lost in a forest problem by SargeZT on Sunday September 16, 2018 @08:31PM (#18002207)

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

[ Parent | on HN ]

Re:Bellman's lost in a forest problem by make3 on Sunday September 16, 2018 @09:28PM (#18002466)

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

[ Parent | on HN ]

Re:Bellman's lost in a forest problem by cuboidGoat on Monday September 17, 2018 @12:39AM (#18003237)

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.

[ Parent | on HN ]

Re:Bellman's lost in a forest problem by rocqua on Monday September 17, 2018 @01:03AM (#18003346)

Isn't that set a circle?

[ Parent | on HN ]

Re:Bellman's lost in a forest problem by HelloNurse on Monday September 17, 2018 @10:14AM (#18006090)

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.

[ Parent | on HN ]

Re:Bellman's lost in a forest problem by crb002 on Sunday September 16, 2018 @08:06PM (#18002087)

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.

[ Parent | on HN ]