5 ms·

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 (com

by bertil 8y ago

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?

crb002 8y ago
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.
cperciva 8y ago
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".
- paulpauper 8y ago
  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.
  - SargeZT 8y ago
    Yes, but you can optimize it even further by following a curve.
  - make3 8y ago
    walking a in side leaning curve minimizes mean total walked distance over all possible cases
- cuboidGoat 8y ago
  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.
  - rocqua 8y ago
    Isn't that set a circle?
    - HelloNurse 8y ago
      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.
gamegoblin 8y ago
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).
- btilly 8y ago
  The optimal strategy in this case is known and is called the Zallager curve. See http://www.wardsattic.com/joomla/Download/WebPresentation/zalgaller_escapes.htm http://www.wardsattic.com/joomla/Download/WebPresentation/za... for a picture.
  - saagarjha 8y ago
    So you’re not too far off: the optimal value is 2.27.
    - deleted 8y ago
      [deleted]
  - dunkelheit 8y ago
    Apparently you've mistyped the name - the curve is named after a Russian-Israeli mathematician Viktor Zalgaller.
  - rocqua 8y ago
    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.
    - pwiecz 8y ago
      If I'm reading http://wardsattic.com/joomla/Download/BellmanForestProblem.pdf http://wardsattic.com/joomla/Download/BellmanForestProblem.p... correctly, the ratio you're looking for is ≈ 2.0471.

by bertil 8y ago

crb002 8y ago

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.

cperciva 8y ago

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

paulpauper 8y ago
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.
- SargeZT 8y ago
  Yes, but you can optimize it even further by following a curve.
- make3 8y ago
  walking a in side leaning curve minimizes mean total walked distance over all possible cases
cuboidGoat 8y ago
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.
- rocqua 8y ago
  Isn't that set a circle?
  - HelloNurse 8y ago
    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.

gamegoblin 8y ago

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

btilly 8y ago
The optimal strategy in this case is known and is called the Zallager curve. See http://www.wardsattic.com/joomla/Download/WebPresentation/zalgaller_escapes.htm http://www.wardsattic.com/joomla/Download/WebPresentation/za... for a picture.
- saagarjha 8y ago
  So you’re not too far off: the optimal value is 2.27.
  - deleted 8y ago
    [deleted]
- dunkelheit 8y ago
  Apparently you've mistyped the name - the curve is named after a Russian-Israeli mathematician Viktor Zalgaller.
- rocqua 8y ago
  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.
  - pwiecz 8y ago
    If I'm reading http://wardsattic.com/joomla/Download/BellmanForestProblem.pdf http://wardsattic.com/joomla/Download/BellmanForestProblem.p... correctly, the ratio you're looking for is ≈ 2.0471.