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.
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
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.
Isn't that set a circle?
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.