11

我是一名生物学家，正在申请一份工作，为此我需要解决这个问题。这是一个开放的书本测试，互联网和任何其他资源都是公平的游戏。这是问题 - 我坚持如何处理它并希望得到指点。我的直觉贴在下面。

背景

你的邻居是一个农民，有两只牛，克拉拉贝尔和伯纳黛特。每头奶牛都有自己的方形围栏，边长为 11m（见第一张图）。这位农民正要出城旅行，并计划将奶牛留在各自的围栏中，这些围栏完全长满了草。奶牛从围栏的中心开始，慢慢地在围栏周围移动，吃草。他们在围栏周围移动得很慢，每走一步总是停下来吃饭或休息。如果将笔分成 1m 个方格，奶牛每一步可以向任意方向移动一个方格（就像棋盘上的国王一样），如第二张图所示。

图 1/2

每次移动后，奶牛会在新的广场上花 20 分钟时间吃草（如果有的话）。广场上的草一旦被吃掉，就永远消失了。如果牛移动到一个草已经被吃掉的广场，那么牛将在那个广场休息 20 分钟。20 分钟后，无论是休息还是进食，奶牛都会移动到另一个方格。如果一头奶牛在栅栏附近的方格中，她永远不会试图朝栅栏的方向移动。奶牛从不会连续两次在同一个方格内待——它们总是在休息或进食后移动到另一个方格。第一个图显示了几个小时后钢笔的外观示例，棕色斑点表示已擦过的方块。

第一头奶牛克拉拉贝尔在移动时对方向没有偏好。她同样有可能在任何时候都朝任何方向移动。设 p 是她朝某个方向移动的概率，如下图第一张所示。

第二头奶牛伯纳黛特更喜欢向有草的方格移动。她向有草的空间移动的可能性是向她已经吃过的空间移动的可能性的两倍，如下图第二个所示。

图 3/4

问题

  • 如果农夫在 48 小时后返回，您预计 Clarabelle 会吃掉她笔中的草的百分比是多少？
  • 你预计 Bernadette 需要多长时间才能吃掉她笔中 50% 的草？
  • 假设如果任何一头奶牛 24 小时不吃任何草，她就会死。哪头牛有望活得更久？

我的直觉

这似乎是对通过二维网格的随机游走进行建模。例如，我可以计算出在给定时间后处于网格中特定节点的概率。但是我不确定如何考虑牛走过时所覆盖的区域。将不胜感激任何见解。

编辑：这里的最终目标是让我为此编写某种程序。这不是一个纯粹的数学问题，因此这里的帖子。

4

2 回答 2

3

有两种方法可以解决此类问题：分析或通过模拟。

如果您将使用基于Monte-Carlo 的方法来模拟该过程，您可以通过对许多轨迹的结果进行平均来轻松找到答案。

我会假设这是您应该做的，除非您另有指导。

于 2015-08-02T10:34:46.937 回答
3

这是一种计算概率的方法（对于 Clarabelle）：

  1. 从 的网格开始0，除了单元格上的 1 (6, 6)，这是您的时间概率网格t = 0。

  2. 在时间，在单元格上t + 1的概率由下式给出：（总和中有八个项）。p(x, y, t + 1)(x, y)p(x, y, t + 1) = p1 * p(x + 1, y, t) + p2 * p(x + 1, y - 1, t) + ...

请注意，所有的pi都不等于：概率可以是1/3（角）、1/5（边）或1/8（任何其他单元格）。

您可以通过将每个步骤运行t = 0到t = 144(48h) 来动态更新您的网格。

如果你想知道一个单元格已经被吃掉的概率，它只是1 - Pn如果Pn这个单元格从未被访问过的概率，即：

(1 - p(x, y, 0)) * (1 - p(x, y, 1)) * (1 - p(x, y, 2)) * ...

这是一个使用 Python 计算这些概率的代码numpy（基本上，这是考虑一个马尔可夫链，其中状态X是所有单元格的集合 |X| = 121，以及转换矩阵 T = {T ij }，其中 T ij是从 i 移动到 j) 的概率：

GridSize = 11
TranSize = GridSize * GridSize
T_Matrix = np.zeros((TranSize, TranSize), dtype = float)

for u in range(T_Matrix.shape[0]):
    for v in range(T_Matrix.shape[1]):
        ux, uy = u % GridSize, u // GridSize
        vx, vy = v % GridSize, v // GridSize
        if u == v or abs(ux - vx) > 1 or abs(uy - vy) > 1:
            p = 0
        elif (ux == 0 or ux == 10) and (uy == 0 or uy == 10):
            p = 1/3
        elif ux == 0 or ux == 10 or uy == 10 or uy == 0:
            p = 0.2
        else:
            p = 0.125
        T_Matrix[u, v] = p

pxy = np.zeros((TranSize, ), dtype = float)
pxy[11 * 5 + 5] = 1
eat = 1 - pxy

for _ in range(144):
    pxy = pxy.dot(T_Matrix)
    eat *= (1 - pxy)

print((1 - eat).reshape((GridSize, GridSize)))

Bernadette 的算法有点复杂，因为你p1, p2, ...是概率性的，所以每个相邻单元格都有两个项。

一旦你掌握了所有这些概率，你就可以很容易地找到你想要的。

于 2015-08-02T09:27:51.120 回答