移動ターゲットを追いかけるアルゴリズム

Question

クエリとリセットができるブラックボックス$ f $があるとします。 $ f $をリセットすると、$ f $の状態$ f_s $は、set $$ {0、1、...、n -1 } $$からランダムに均一に選択された要素に設定されます。ここで$ n $は固定されており、与えられた$ f $で知られています。 $ f $を照会するには、$$ {0、1、...、n -1 } $$からの要素$ x $（推測）が提供され、返される値は$（f_s -x）です。 mod n $。さらに、$ f $の状態$ f_s $は$ f_s '= f_s pm k $に設定されます。ここで、$ k $は$$ {0、1、2、...、...、ランダムに均一に選択されます。 lfloor n/2 rfloor - （（f_s -x） mod n）} $$

各クエリで均一にランダムな推測を行うことにより、$ f_s = x $を取得する前に$ n $推測を行う必要があると予想されます。

アルゴリズムは、より良いことをするように設計できますか（つまり、推測の数が少ない場合、推測が少なくなります）？それはどれほど良いことができますか（つまり、最適なアルゴリズムは何ですか、そしてそのパフォーマンスは何ですか）？

この問題に対する効率的な解決策は、暗い部屋でウサギ（円形トラックに飛び込むことに限定されている）での射撃に重要なコスト削減の意味を持つ可能性があります。

Answer 1

まず第一に、私はそれを想定します

さらに、$ f $の状態$ f_s $は$ f_s '= f_s pm k $に設定されます。ここで、$ k $は$$ {0、1、2、...、...、ランダムに均一に選択されます。 lfloor n/2 rfloor - （（f_s -x） mod n）} $$

あなたは実際に意味します

さらに、$ f $の状態$ f_s $は$ f_s '= f_s + k mod n $に設定されます。ここで、$ k $は$$ left { - left |からランダムに均一に選択されます。 left lfloor frac {n} {2} right rfloor - （（f_s -x） mod n） right |、 ldots、-1、0、1、2、 ldots、 left | left lfloor frac {n} {2} right rfloor - （（f_s -x） mod n） right | right } $$

それ以外の場合、$ f_s in {0、...、n-1 } $が常に保持され、$ f_s pm k $がどのように動作するかは完全には明らかではありません。

これを使用して、問題は基本的に「可能な限り欠けている」ことになります。ウサギを撃つほど、彼が作る大きなホップがあることを観察してください。極端な場合には、$ f_s -x = pm 1 mod n $があります。これにより、$ - （ lfloor n/2 rfloor pm 1）$と$（ lfloor n/2 rfloor pm 1）$の間の均一なホップが発生します。一方、可能な限りひどく見逃した場合 - $ f_s -x mod n = lfloor n/2 rfloor $のオフセットで、ウサギは実際にはまったく動きません（！） と ブラックボックスは実際にこの事実について私たちを更新します。したがって、振り向いてウサギを撃つことができます。

私たちは、各ショットでますます欠落する手順を見つけることに残されています。簡単な「バイナリ検索」を提案します。 （丸めを便利に省略します。）それは次のようにほぼ進みます。

1. ブラックボックスから回答を取得するまで、任意の位置でリセットして撮影します。 n }。$これには、期待に一定の手順が必要です。
2. 今、私たちは、ラビットの過去の位置$ f_s $であり、どちらの方向にも$ frac {1} {4} n $を超えて移動しなかったことを知っています。これは基本的に、次の反復で検索スペースを半分にします。ウサギは {（f_s - frac {1} {4} n） mod n、...、f_s、f_s ' in { frac {1} { frac { frac {1} { frac { ...、（f_s + frac {1} {4} n） mod n } $
3. 繰り返し：ポジション$ f_s -n/2 mod n $で撮影します。確率$ 1/2 $で、ポジション$ f_s '$はステップ1と2でジャンプしました$ {f_s - frac {1} {8} n、...、f_s、...、f_s + + frac {1} {8} n } $。その場合、検索スペースをもう一度半分にしました。確率$ 1/2 $で、ウサギはその範囲にジャンプしませんでしたが、$ f_s '-x mod n = f_s' -f_s + n/2 mod n in { frac {1} {2} n - frac {1} {4} n、...、 frac {1} {2} n + frac {1} {4} n } $、ステップと同じ仮定があります（2）したがって、何も失いません。

各ステップには$ 2 = mathcal {o}（1）$の予想時間が成功し、検索スペースを半分にし、$ mathcal {o}（ log n）$の予想ステップ数を生成します。