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.
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.
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.
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!
thanks for the link!
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.
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).
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).