algorithm - 二维网格中随机游走所覆盖的区域是多少？

Question

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

背景

您的邻居是一位农民，有两头奶牛，克拉拉贝尔和伯纳黛特。每头奶牛都有自己的边长为 11m 的方形围栏(见第一张图)。农夫正准备出城旅行，并计划将奶牛留在各自的围栏中，开始时这些围栏里全是草。奶牛从围栏中央开始，慢慢地绕着围栏移动吃草。他们在围栏周围移动非常缓慢，每走一步后总是停下来吃饭或休息。如果把围栏分成1m的方格，奶牛每走一步可以向任意方向移动一个方格(就像棋盘上的王)，如图2所示。

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

第一头母牛 Clarabelle 在移动时没有方向偏好。她在任何时候都同样有可能朝任何方向移动。令 p 为她朝某个方向移动的概率，如下面第一张图所示。

第二头牛 Bernadette 更喜欢向有草的方 block 移动。她走向有草的空间的可能性是她走向已经吃过的空间的可能性的两倍，如下面的第二张图所示。

问题

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

我的直觉

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

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

Answer 1

这是一种计算概率的方法(对于 Clarabelle):

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

2. 在 t + 1 时，出现在单元格 (x, y) 上的概率 p(x, y, t + 1) 由以下公式给出: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 计算这些概率(基本上，这是考虑一个 Markov Chain，其中状态 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, ... 是概率性的，因此您会为每个相邻的单元格获得两项。

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