ベルマンの森で迷子になった問題

ベルマンの森で迷子になる問題は、幾何学における未解決の最小化問題であり、1955 年にアメリカの応用数学者リチャード・E・ベルマンによって提起された。^{[ 2 ]} この問題はしばしば次のように述べられる。「ハイカーが、形状と寸法が正確にわかっている森で迷子になった。森から脱出するために彼がたどるべき最良の道は何か？」^{[ 1 ]}通常、ハイカーは出発点や自分が向いている方向を知らないと想定される。最良の道は、森の端に到達するまでの移動距離が最悪の場合を最小にする道とされる。この問題の他のバリエーションも研究されている。

実際の応用例は明らかではないものの、この問題は、実用的な重要性を持つ探索戦略を含む、幾何学的最適化問題のクラスに分類される。研究のより大きな動機は、モーザーのワーム問題との関連性である。この問題は、数学者のスコット・W・ウィリアムズが「百万ドルの問題」と表現した12の問題のリストに含まれており、彼はこれらの問題の解決に関わる技術が数学にとって少なくとも百万ドルの価値があると信じていた。^{[ 3 ]}

任意の形状に対する最適解を見つける方法は知られていないが、特定の形状や特定の形状クラスについては最適解が知られている。

• 森林に、長い対角線が森林の直径である60°の菱形が含まれている場合、最適な脱出経路の長さは直径であり、この距離を直線で歩くことが最適な脱出方法となる。このケースには、例えば円形の森林が含まれる。^{[ 1 ]}
• 半円形の森林、あるいはより一般的には角度が少なくとも 60° の扇形の森林の最適な脱出経路は、森林の直径であり、3 辺以上の正多角形の最適な脱出経路も同様である。 ^{[ 1 ]}
• 幅が無限に広がる帯状領域における最適な脱出経路${\displaystyle w}$は、4 つの直線セグメントと 2 つの浅い円弧から形成される V 字型の経路で、長さは約${\displaystyle 2.2783w}$この同じ経路は、高さの長方形にも最適です。${\displaystyle w}$その直径は、この経路の長さ以上である。直径が短い長方形の場合、最適な脱出経路の長さは直径である。直径が同じ高さの帯状部分の脱出経路の長さに等しい長方形は、帯状部分の経路と直径と同じ長さの単一の線分という、2つの非常に異なる最適な脱出経路を持つ形状の例となる。^{[ 1 ]}