algorithm - 一个人在矩阵中移动 n 步的死亡概率

标签 algorithm recursion matrix dynamic-programming

有一个岛,用方阵nxn表示。

岛上的一个人站在任何给定的坐标 (x,y) 处。他可以在岛上向右、左、上、下向任何方向移动一步。如果他走出岛,他就会死。

让岛表示为 (0,0) 到 (n-1,n-1)(即 nxn 矩阵)& 人站在给定的坐标 (x,y) 处。他被允许在岛上(沿着矩阵)移动 n 步。他在岛上走了 n 步后他已经死了的概率是多少?

What should be the approach to find the probability using programming techniques?

I have a mathematical method, but I don't know whether it's correct or not. Here it is:

结果总数为 n^n。要计算可能导致人死亡的结果数量:

对于四个方向中的每一个,检查多少步可以导致他走出矩阵。然后,应用高中概率公式。例如假设他能走的总步数是 5; (x, y) = (2,1) [索引从 0 开始]。所以,他需要在北方向采取 3 个步骤。掉出岛。将它们放在一个组中:(NNN) 并将其他 2 个步骤作为 4 个选择中的任何一个,我们有公式:4*4*3。同样,对于其他 3 个方向。最后,概率=(计算出的死亡结果之和)/(总结果)

This was a Google interview question.

最佳答案

TL;DR:递归。 (或者“数学归纳法”,如果你势利的话。)

(在下文中,“他在岛上走了 n 步之后就死了”假定是指“他在少于或等于 n 步之后死了”。如果你认为它的意思是“他恰好在 n 步后死了”,答案会略有不同。我将在最后简要讨论。)

我们有一个 NxN 矩阵,其中每个单元格中的值表示如果我们从该单元格开始,则在 n 步后死亡的概率。

考虑在 0 步内死亡的概率。显然,岛内的每个位置都是 0.0,岛外的每个位置都是 1.0

1 步内死亡的概率是多少?你有四个方向可以移动,概率相等。因此,对于每个单元格,您取它的四个邻居,找出它们在 0 步内死亡的概率,然后将它们平均在一起。 (如果邻居在矩阵之外,您认为它的概率为 1.0。)

类似地,从给定单元格开始的 k 步死亡概率是从其相邻单元格开始的 k-1 步死亡概率的平均值。

Python代码:

from itertools import product as prod 

def prob_death(island_size, steps):
    if island_size < 1 or steps < 0: raise ValueError
    new_prob = [[0. for i in range(island_size)] for j in range(island_size)]
    if steps == 0:
        return new_prob
    old_prob = prob_death(island_size, steps - 1)
    directions = [(0, -1), (1, 0), (0, 1), (-1, 0)]
    for (i, j, direction) in prod(range(island_size), range(island_size), directions):
        neighbor_i = i + direction[0]
        neighbor_j = j + direction[1]
        if neighbor_i >= 0 and neighbor_i < island_size and \
                neighbor_j >= 0 and neighbor_j < island_size:
            prob_death_this_way = old_prob[neighbor_i][neighbor_j]
        else: # neighbor is outside the island 
            prob_death_this_way = 1.
        new_prob[i][j] += 0.25* prob_death_this_way
    return new_prob

现在,让我们稍微测试一下:(mpr 只是一个很好地打印矩阵的函数)

>>> mpr(prob_death(5, 0))
0.000000 0.000000 0.000000 0.000000 0.000000
0.000000 0.000000 0.000000 0.000000 0.000000
0.000000 0.000000 0.000000 0.000000 0.000000
0.000000 0.000000 0.000000 0.000000 0.000000
0.000000 0.000000 0.000000 0.000000 0.000000

正如预期的那样:如果您从岛内开始,您将无法在 0 步内死亡。

>>> mpr(prob_death(5,1))
0.500000 0.250000 0.250000 0.250000 0.500000
0.250000 0.000000 0.000000 0.000000 0.250000
0.250000 0.000000 0.000000 0.000000 0.250000
0.250000 0.000000 0.000000 0.000000 0.250000
0.500000 0.250000 0.250000 0.250000 0.500000

这是我们所期望的。如果您从角落单元格开始,您有 0.5 的概率在 1 步内死亡:您的 4 个邻居中有 2 个在岛外。如果你从边缘开始,只有 1 个邻居在外面,所以你的死亡概率是 0.25。在其他任何地方,所有邻居都在岛内,因此在 1 步内死亡的概率是 0.0

>>> mpr(prob_death(5, 5))
0.806641 0.666016 0.622070 0.666016 0.806641
0.666016 0.437500 0.349609 0.437500 0.666016
0.622070 0.349609 0.261719 0.349609 0.622070
0.666016 0.437500 0.349609 0.437500 0.666016
0.806641 0.666016 0.622070 0.666016 0.806641

5 步死亡的概率。我无法验证确切的值,但它看起来是正确的:死亡的概率在角落最高,在边缘稍低,并向内稳步下降。

这解决了在小于或等于 n 步内死亡的问题。

现在,求恰好 n 步死亡的概率:让死亡概率小于或等于 n 步从 (x,y) 开始,用 P(x,y,n) 表示。那么恰好 n 步死亡的概率是 n-1 步存活的概率乘以第 n 步死亡的概率假设我们存活了 n-1 步骤:(1-P(x,y,n-1))*(P(x,y,n) - P(x, y,n-1))。 (我对这个公式不是很确定;如果我错了请纠正我。)

关于algorithm - 一个人在矩阵中移动 n 步的死亡概率,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16522296/

相关文章:

c++ - 创建对象数组的问题 C++

javascript - 如何从叶节点的一组路径片段构建树

java - 为什么我的解决方案对于反转整数是错误的?

recursion - 复发的限制有多大?

Haskell 开关/案例使用

c - 如何用C语言创建矩阵结构?

c# - 使用 DataMatrix 代码作为键盘输入

algorithm - 客户端服务请求的隐式 "Authentication"

c - 俄罗斯农民乘法

python - 如何在抽象语法树上递归执行 "tree walk"?