6

無限の柵の前に牛が立っています。反対側は草です。牛はこの草に行きたがっています。この柵のどこかに、牛が反対側に行くことができる穴があります。牛から穴までの距離dには、それに関連する確率分布f（d）があります。つまり、穴が牛からkステップ離れている確率はf（k）で与えられます。すべての距離を離散的であると考えることに注意してください。つまり、牛がとる歩数で常に測定されます。牛は、負の整数の歩数と正の整数の歩数、つまりそれぞれ左にk歩、右に歩むことができます。また、∑（k =-∞）^∞| k |⋅f（k）<∞であることがわかります。確率1で穴を見つけることができるアルゴリズムを説明したいと思います。

問題1アルゴリズムが確率1で穴を見つけることができるための十分な条件は何ですか？問題2そのようなアルゴリズムを説明してください。

4

4 に答える 4

4

述べたように、あなたの問題には些細な解決策があるように私には思えます。

  • 現在の位置に穴がないか確認してください
  • 1歩進み、穴を確認します
  • 2歩後ろに歩き、穴を確認します
  • 3歩進み、穴を確認します
  • 4歩後方に歩き、穴を確認します。

このウォークでは、確率1ですべての相対整数を訪問します。もちろん、本当に必要なのは、牛がとる必要のある平均歩数を最適化することです。これは、検索ゲームの問題として知られています。解決策は、1次元の指数関数的な「スパイラル」です。上記の1-2-3-4-5算術シーケンスを幾何学的シーケンスに置き換え、毎回2を掛けます。あれは：

  • 現在の位置に穴がないか確認してください
  • 各ステップで穴を確認しながら、1ステップ進みます
  • 各ステップで穴を確認しながら、2ステップ後方に歩きます
  • 各ステップで穴を確認しながら、4ステップ進みます
  • 各ステップで穴を確認しながら、8ステップ後方に歩きます。

Google for "The Cow-Path Problem"は、N-way交差点への一般化です（「左」と「右」の2つしかありません）

于 2010-09-08T13:38:49.513 に答える
1

穴が特定の位置にあるかどうかを確認するだけでいいですか？もしそうなら、やるべきことは可能性の高い順に位置をチェックすることだけのようです。穴を見つけることは保証されますが、それは任意に長い時間がかかる場合があります。（fが有限のサポートを持っている場合、つまり、f（k）> 0のkが有限である場合に限り、特定の数の検索内で穴が見つかることを保証できます）。未知の数の穴がある場合、fが有限のサポートを持っている場合にのみ、それらすべてを見つけたと判断できます。

一方、穴までの距離が指定された量よりも短いかどうかを確認できる場合は、CDFでfを重み付けした二分探索のようなものがおそらく最良のオプションです。

問題の背景を説明できれば助かります。現状では、グラフは実際には方程式に入っていないようです。カップがたくさんあるだけで、その下にボールがあるものを見つけようとしています。

于 2010-09-03T05:15:09.733 に答える
0

砲丸投げを作成し、その間に可変サイズの間隔を置いた壁を置き、壁が撃たれていないことを確認します。そこから続けてください。ただし、穴の関数をグラフ化する方法を知っている必要があります（無限の穴ではなく、近似で十分な場合があります）。

于 2010-09-03T06:14:14.100 に答える
0 
findHole(S)
{
  k = 0;
  previous_k = 0;

  current_f = f(k, S);
  if (current_f == 1) return (S);

  previous_f = 0;
  //While the probability of finding a hole increases,
  //we increase k and verify if the vertex at k steps is a hole
  while (current_f >= previous_f)
  {
    previous_f = current_f;
    previous_k = k;

    //As closer to probability 1 we are, as smaller steps we make
    k = (1 - current_f) * MAX_STEP_SIZE;
    current_f = f(k, S);
    if (current_f == 1) return (S);
  }

  //If we overshot our hole and the probability of finding
  //a hole at k steps distance has started to decrease, we
  //perform a binary search within the boundaries of the interval
  //[previous_k, k], with probabilities in [previous_f, current_f],
  //having a guarantee that our hole is within this interval
  return binSearch(previous_k, k, S);
}
于 2010-09-03T06:55:56.603 に答える