6

一头牛站在无限的栅栏前。另一边是草。母牛想要到达这片草地。沿着这个栅栏的某个地方有一个洞，牛可以通过这个洞到达另一边。从牛到洞的距离 d 具有与之相关的概率分布 f(d)，即洞距离牛 k 步的概率由 f(k) 给出。请注意，我们认为所有距离都是离散的，即它们始终以奶牛所走的步数来衡量。奶牛可以走负整数步数以及正整数步数，即分别向左走 k 步和向右走 k 步。此外，我们知道 ∑(k=-∞)^∞|k|⋅f(k)<∞。我们想描述一种可以找到概率为 1 的洞的算法。

问题 1 算法能够以概率 1 找到洞的充分条件是什么？问题 2 描述这样一个算法。

4

4 回答 4

4

如前所述，在我看来，您的问题有一个简单的解决方案：

  • 检查当前位置的孔
  • 向前走 1 步，检查是否有洞
  • 向后走 2 步，检查是否有洞
  • 向前走 3 步，检查是否有洞
  • 向后走4步，检查洞...

此步行将访问所有相对整数，概率为 1。当然，您真正想要的是优化奶牛必须采取的平均步数，这被称为搜索博弈问题。解是一维指数“螺旋”；您只需将上面的 1-2-3-4-5 等差数列替换为几何数列，每次乘以 2。那是：

  • 检查当前位置的孔
  • 向前走 1 步，每一步检查是否有洞
  • 向后走 2 步，每一步检查是否有洞
  • 向前走 4 步，每一步检查是否有洞
  • 向后走 8 步，每一步检查是否有洞……

谷歌搜索“The Cow-Path Problem”，这是你对 N 路十字路口的概括（你只有两个，“左”和“右”）

于 2010-09-08T13:38:49.513 回答
1

你能做的就是检查孔是否在给定的位置吗？如果是这样，似乎唯一要做的就是按照可能性递减的顺序检查位置。你一定会找到一个洞，但它可能需要任意长的时间。（你可以保证你会在一定数量的搜索中找到一个洞当且仅当 f 具有有限支持——也就是说，当且仅当 f(k) > 0 的 k 是有限的）。如果存在未知数量的孔，则只有在 f 具有有限支持的情况下，您才能确定您已将它们全部定位。

另一方面，如果您可以检查到孔的距离是否小于某个指定量，那么类似由 CDF 对 f 加权的二进制搜索可能是最佳选择。

如果您能描述问题的背景，将会很有帮助。就目前而言，图表似乎并没有真正进入等式——你只有一堆杯子，你试图找出哪个杯子下面有一个球。

于 2010-09-03T05:15:09.733 回答
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 回答
0

创建一个子弹射击，在它们之间放置可变大小的间隔墙，看看没有射中哪一堵墙。从那里继续。不过，您必须知道如何绘制孔函数（也许可以近似，而不是无穷无尽的孔）。

于 2010-09-03T06:14:14.100 回答