線形探索問題

計算複雑性理論において、線形探索問題はリチャード・E・ベルマン^[1]によって導入され、アナトール・ベック[2]によって独立に考察された最適探索問題である。^{[3 ] [4]}

「動かない隠れ者は、既知の確率分布に従って実線上に位置しています。最大速度が 1 である探索者は、原点からスタートし、最小の期待時間で隠れ者を発見したいと考えています。探索者は、時間を無駄にすることなく移動方向を変更できると想定されています。また、探索者は、隠れ者がいる地点に実際に到達するまで隠れ者を見ることができず、この瞬間までの経過時間がゲームの継続時間であると想定されています。」

問題は、できるだけ短時間で隠れている人を見つけることです。一般に、隠れている人は探索者の両側にいて、距離は任意であるため、探索者は前後に振動する必要があります。つまり、探索者は一方向に距離 x _{1進み、原点に戻って反対方向に距離 x 2}進むなどする必要があります (n 番目のステップの長さは x _nで示されます)。(ただし、最適なソリューションには最初のステップは必要なく、無限の数の小さな「振動」から開始できます。)この問題は通常、線形探索問題と呼ばれ、探索計画は軌道と呼ばれます。

一般確率分布の線形探索問題は未解決である。^[5]しかし、任意の離散分布の解を生成する動的計画法アルゴリズムが存在する。 ^[6]また、任意の確率分布の近似解を任意の精度で生成するアルゴリズムも存在する。^[7]

線形探索問題は、アナトール・ベックとドナルド・J・ニューマン（1970）によって2人ゼロサムゲームとして解かれた。彼らのミニマックス軌道は、各ステップで距離を2倍にすることであり、最適な戦略は、距離を一定の定数だけ増やす軌道の混合である。^[8]この解決策は、ターゲットの分布に関する仮定に左右されない探索戦略を与える。したがって、最悪のシナリオの上限も提示する。この解決策は、シュムエル・ガルによるオンラインアルゴリズムのフレームワークで得られ、彼はこの結果を同時光線のセットに一般化した。^[9]直線上の探索の最良のオンライン競争比は9であるが、ランダム化戦略を使用することで4.6に減らすことができる。デメインらは、ターンコストを伴うオンラインソリューションを与えた。^[10]

これらの結果は、1990 年代にコンピューター科学者によって「牛の道問題」として再発見されました。

• 線形探索
• ゲームを検索