一个人移动n步死亡矩阵概率 [英] Probability of death of a man moving n steps in a matrix
问题描述
有一个岛屿被重新由方阵n阶psented $ P $。
一个人在岛上正站在任何给定的坐标（X，Y）。他可以在任何方向上一步算一步吧岛上移动，左，上，下。如果他的步骤岛外，他死了。
让岛被重新presented为（0,0）到（n-1，N-1）（即n×n个矩阵）及人站在给定的坐标（X，Y）。他被允许移动至n步上岛（沿矩阵）。什么是他已经死了，他走n步上岛后的概率是多少？
应该用什么方法使用编程技术来发现的概率？
我有一种数学方法，但我不知道它是否是正确与否。在这里，它是：
结果的总数为n的n次方。计算结果的可导致人的死亡数：
有关每个的四个方向，检查有多少步骤可导致他外出基质。然后，应用高中概率公式。对于如假设步骤，他可以采取的总数为5; （X，Y）=（2,1）[索引是基于0]。因此，他需要在北部DIR 3个步骤。跌出岛。使它们保持在一组：（NNN）和作出其他2个步骤的任何的4个选择的，我们具有下式：4 * 4 * 3。同样，对于其他3个方向。最后，probality =（所计算的死亡结果的总和）/（总的结果）
这是一个谷歌的面试问题。
TL; DR ：递归。 （或数学归纳法，如果你是势利的。）
（在下文中，他死了，他走之后， N 岛上步骤被认为是指他在小于或等于死亡为 N 步骤。如果你把它理解为他去世之后正是 N 步骤，答案会略有不同。我会在最后简单地讨论它。）
我们有一个 N×N个矩阵，其中每个小区重$ P $值psents死在 N 步骤，如果我们从细胞开始。
考虑死在 0 步骤的可能性。显然，这是 0.0 为岛内每一个位置，而 1.0 无处不在外面。
什么是死在 1 步骤的概率是多少？你有四个方向可以移动的，概率相同。因此，对于每一个细胞，你把它的四个邻国，发现死在 0 步骤的概率和平均在一起。 （如果邻居是矩阵外，你认为它的概率是 1.0 ）
同样，死在 K 从给定的单元格开始步骤的概率是死在 K-1的概率从相邻小区启动步骤。
Python的code：
从itertools进口产品为督促
高清prob_death（island_size，步骤）：
如果island_size＆LT; 1或步骤：; 0：提高ValueError错误
new_prob = [[0。因为我在范围范围（island_size）对于j（island_size）
如果步骤== 0：
返回new_prob
old_prob = prob_death（island_size，步骤 - 1）
方向= [（0，-1），（1,0），（0,1），（ - 1，0）]
对（I，J，方向）在刺（范围（island_size），范围（island_size），方向）：
neighbor_i = 1 +方向[0]
neighbor_j = J +方向[1]
如果neighbor_i＆GT; = 0和＆neighbor_i其中; island_size和\
neighbor_j＆GT; = 0和＆neighbor_j其中; island_size：
prob_death_this_way = old_prob [neighbor_i] [neighbor_j]
其他：＃邻居是岛外
prob_death_this_way = 1。
new_prob [I] [J] + = 0.25 * prob_death_this_way
返回new_prob
现在，让我们来测试它一点：（ MPR 只是一个功能，打印矩阵很好）
＆GT;＆GT;＆GT; 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步骤死，如果你开始岛内
＆GT;＆GT;＆GT; 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
这是我们所期待的。如果你开始在一个角落里的细胞，你必须死在1步 0.5 概率：2出的4邻居是岛外。如果你开始的边缘，只有1个邻居在外面，所以死亡的概率是 0.25 。在其他地方，所有的邻居都在岛内，因此死在1步的概率 0.0 。
＆GT;＆GT;＆GT; 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 步骤的可能性：让死在小于或等于的概率启动ñ步骤（X，Y）按 N 步骤的概率存活 N-1 步骤，时间的概率的概率死在 N 次步骤给我们存活 N-1 的步骤：（1 -P（X，Y，n-1个））*（P（X，Y，正） - P（X，Y，n-1个））。 （我不是那么肯定这个公式，纠正我，如果我错了。）
There is an island which is represented by square matrix nxn.
A person on the island is standing at any given co-ordinates (x,y). He can move in any direction one step right, left, up, down on the island. If he steps outside the island, he dies.
Let the island be represented as (0,0) to (n-1,n-1) (i.e nxn matrix) & person is standing at given co-ordinates (x,y). He is allowed to move n steps on the island (along the matrix). What is the probability that he is dead after he walks n steps on the island?
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:
The total number of outcomes are n^n. To calculate the number of outcomes which can lead to death of the person:
For each of the four directions, check how many steps can lead to him going out of the matrix. Then, apply the high school probability formula. For e.g. suppose the total number of steps he can take are 5; (x, y) = (2,1) [indexing is 0-based]. So, he needs to take 3 steps in north dir. to fall out of island. Keeping them in a group: (NNN) and making other 2 steps as any of the 4 choices, we have the formula: 4*4*3. Similarly, for other 3 directions. Finally, the probality = (sum of the calculated death outcomes) / (total outcomes)
This was a Google interview question.
TL;DR: Recursion. (Or "mathematical induction", if you're snobbish.)
(In what follows, "he is dead after he walks n steps on the island" is assumed to mean "he dies after less than or equal to n steps". If you take it to mean "he dies after exactly n steps", the answer will be slightly different. I'll discuss it briefly at the end.)
We have an NxN matrix where the value in each cell represents the probability of dying in n steps if we started from that cell.
Consider the probability of dying in 0 steps. Clearly, this is 0.0 for every location inside the island, and 1.0 everywhere outside it.
What's the probability of dying in 1 steps? You have four directions you can move in, with equal probability. So for each cell, you take its four neighbors, find their probability of dying in 0 steps, and average them together. (If a neighbor is outside the matrix, you consider its probability to be 1.0.)
Similarly, the probability of dying in k steps starting from a given cell is the average of the probability of dying in k-1 steps starting from its neighbour cells.
Python code:
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
Now, let's test it out a bit: (mpr is just a function for printing matrices nicely)
>>> 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
As expected: You can't die in 0 steps if you start inside the island.
>>> 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
This is what we'd expect. If you start at a corner cell, you have 0.5 probability of dying in 1 step: 2 out of your 4 neighbors are outside the island. If you start on an edge, only 1 neighbor is outside, so your probability of dying is 0.25. Everywhere else, all neighbors are inside the island, so probability of dying in 1 step is 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
The probability of dying in 5 steps. I can't verify the exact values, but it looks about right: The probability of dying is highest in the corners, a little lower at the edges, and decreases steadily inwards.
That solves the problem of dying in less than or equal to n steps.
Now, to find the probability of dying in exactly n steps: Let the probability of dying in less than or equal to n steps starting from (x,y) be denoted by P(x,y,n). Then the probability of dying in exactly n steps is the probability of surviving for n-1 steps, times the probability of dying in the nth step given that we survived for n-1 steps: (1-P(x,y,n-1))*(P(x,y,n) - P(x,y,n-1)). (I'm not all that sure about this formula; correct me if I'm wrong.)
这篇关于一个人移动n步死亡矩阵概率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
