一头牛站在无边无际的栅栏前。另一边是草地。牛想要到达这片草地。沿着栅栏的某个地方有一个洞，牛可以通过这个洞到达另一边。从牛到洞的距离 d 具有与之相关的概率分布 f(d)，即洞距牛 k 步的概率由 f(k) 给出。请注意，我们认为所有距离都是离散的，即它们总是以奶牛所采取的步数来测量。奶牛可以采取负整数步数，也可以采取正整数步数，即分别向左 k 步和向右 k 步。另外，我们知道 Σ(k=-∞)^∞|k|⋅f(k)
问题1 算法能够以概率1找到漏洞的充分条件是什么？
问题2 描述这样一个算法。
在我看来，正如所述，你的问题有一个简单的解决方案：
- 检查当前位置是否有孔
- 向前走1步，检查是否有洞
- 向后走 2 步，检查是否有洞
- 向前走3步，检查是否有洞
- 向后走 4 步，检查是否有洞...
这次步行将以概率 1 访问所有相对整数。当然，您真正想要的是优化奶牛必须采取的平均步数，这称为搜索游戏问题 http://en.wikipedia.org/wiki/Search_games。解是一维指数“螺旋”；您只需将上面的 1-2-3-4-5 算术数列替换为几何数列，每次乘以 2 即可。那是：
- 检查当前位置是否有孔
- 向前走一步，每一步检查是否有洞
- 向后走 2 步，每一步检查是否有洞
- 向前走 4 步，每一步检查是否有洞
- 向后走 8 步，每一步检查是否有洞……
谷歌搜索“The Cow-Path Problem”，这是你对 N 路十字路口的概括（你只有两个，“左”和“右”）
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
