algorithm - 行列で n 歩移動する人の死亡確率

Question

正方行列 nxn で表される島があります。

島にいる人は任意の座標 (x,y) に立っています。彼は島の上、下、左、右に 1 歩、どの方向にも移動できます。島の外に出ると死ぬ。

島が (0,0) から (n-1,n-1) (つまり、nxn 行列) で表され、人が特定の座標 (x,y) に立っているとします。彼は島を (行列に沿って) n 歩移動することができます。彼が島を n 歩歩いた後に死ぬ確率は?

プログラミング手法を使用して確率を見つけるには、どのようなアプローチが必要ですか?

数学的方法を持っていますが、それが正しいかどうかはわかりません。ここにあります：

結果の総数は n^n です。人の死に至る可能性のある結果の数を計算するには:

4 つの方向のそれぞれについて、彼がマトリックスの外に出るまでに何歩進むことができるかを調べます。次に、高校の確率式を適用します。たとえば、彼が実行できるステップの合計数が 5 であるとします。(x, y) = (2,1) [インデックスは 0 ベース]。したがって、彼は北方向に 3 歩進む必要があります。島から落ちる。これらをグループ (NNN) にまとめ、他の 2 つのステップを 4 つの選択肢のいずれかにすると、4*4*3 という式が得られます。他の3方向も同様。最後に、確率 = (計算された死亡結果の合計) / (合計結果)

これはGoogleのインタビューの質問でした.

Answer 1

TL;DR : 再帰。（または、あなたが気取っているなら、「数学的帰納法」。）

(以下では、「彼はn島を歩いた後に死ぬ」は、「次の歩数以下で死ぬ」という意味であると想定されていnます。「彼は正確に数歩後に死ぬ」という意味に解釈するnと、答えは次のようになります。最後に簡単に説明します。)

各セルの値が、そのセルから開始した場合に段階NxN的に死亡する確率を表すマトリックスがあります。n

0段階的に死ぬ確率を考えてみましょう。明らかに、これは0.0島内のすべての場所と島外のすべての場所に適用されます1.0。

1段階的に死ぬ確率は？移動できる方向は 4 方向あり、同じ確率で移動できます。したがって、各セルについて、その 4 つの隣接セルを取得し、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以下で死ぬ確率を で表すことにする。次に、正確に歩数で死ぬ確率は、歩数で生き残る確率に、歩数で生き残った場合のth 歩で死ぬ確率を掛けたものです。（この式についてはよくわかりません。間違っていたら訂正してください。）n(x,y)P(x,y,n)nn-1nn-1(1-P(x,y,n-1))*(P(x,y,n) - P(x,y,n-1))

Answer 2

まず、0 番目のステップで (x, y) の正方形に入る確率を持つ行列から始めます。4x4 マトリックスでシミュレートしてみましょう。男が（1、2）から始まると仮定します：

After 0 steps:
  0.00%   0.00%   0.00%   0.00%
  0.00%   0.00% 100.00%   0.00%
  0.00%   0.00%   0.00%   0.00%
  0.00%   0.00%   0.00%   0.00%
outside:   0.00%
----
After 1 steps:
  0.00%   0.00%  25.00%   0.00%
  0.00%  25.00%   0.00%  25.00%
  0.00%   0.00%  25.00%   0.00%
  0.00%   0.00%   0.00%   0.00%
outside:   0.00%
----
After 2 steps:
  0.00%  12.50%   0.00%  12.50%
  6.25%   0.00%  25.00%   0.00%
  0.00%  12.50%   0.00%  12.50%
  0.00%   0.00%   6.25%   0.00%
outside:  12.50%
----
After 3 steps:
  4.69%   0.00%  12.50%   0.00%
  0.00%  14.06%   0.00%  12.50%
  4.69%   0.00%  14.06%   0.00%
  0.00%   4.69%   0.00%   4.69%
outside:  28.12%
----
After 4 steps:
  0.00%   7.81%   0.00%   6.25%
  5.86%   0.00%  13.28%   0.00%
  0.00%   9.38%   0.00%   7.81%
  2.34%   0.00%   5.86%   0.00%
outside:  41.41%
----

これを計算する python プログラムは次のとおりです。

class Table:
    def __init__(self, n, outside=0):
        self.T = [[0]*n for i in xrange(n)]
        self.outside = outside

    def add(self, i, j, value):
        n = len(self.T)
        if 0<=i<n and 0<=j<n:
            self.T[i][j] += value
        else:
            self.outside += value

    def make_next(self):
        n = len(self.T)
        Q = Table(n, self.outside)

        for i in xrange(n):
            for j in xrange(n):
                value = self.T[i][j] / 4.0
                Q.add(i-1, j, value)
                Q.add(i+1, j, value)
                Q.add(i, j-1, value)
                Q.add(i, j+1, value)
        return Q

    def __repr__(self):
        return '\n'.join(' '.join(
                    '{:6.2f}%'.format(item*100) 
                    for item in line)
                    for line in self.T) + \
               '\noutside: {}'.format('{:6.2f}%'.format(self.outside*100))


N = 4
T = Table(N)
T.add(1, 2, 1)

for k in xrange(N+1):
    print 'After {} steps:'.format(k)
    print T
    print '----'

    T = T.make_next()

Answer 3

アプローチは確率式に依存する必要があります-有利なケースの数/ケースの総数

与えられた座標 (x,y) とステップ - n ユーザーが歩むことができる方法の総数 -
1 番目のステップ - 4 通り 2 番目のステップ - 4 * 3 (彼が後退できないと仮定) 3 番目のステップ - 4* 3^2 .... ... ... n 番目のステップ - 4*3^(n-1) Arthmetic Progression は合計ステップを示します。

Farovable ケース - つまり、境界を越える - 4 つの方向すべてで再帰を伴う再帰関数と、行列の境界が交差するたびに変数カウントが増加します。

両方を割ると答えが得られます。

Answer 4

問題の解決策を明らかにするのに非常に役立ちました。確率として 0.25 を使用すると (前述の )、誤解を招き、不正確になる可能性があります。確率 #dead_cases/#total_possible_moves を見ると、結果は異なります。

死ぬ/生き残ったケースを見つけるための次のコードを検討してください。

def winLoss_stat(N, steps):
    newStats = [[[0, 0, 0] for i in range(N)] for j in range(N)]
    if steps==0:
        newStats = [[[1, 0, 0] for i in range(N)] for j in range(N)]
        return newStats
    oldStats = winLoss_stat(N, steps-1)
    for i in range(N):
        for j in range(N):
            for d in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                indX = i + d[0]
                indY = j + d[1]
                if indX >=0 and indX < N and indY >= 0 and indY<N:
                    newStats[i][j][0] += oldStats[indX][indY][0]
                    newStats[i][j][1] += oldStats[indX][indY][1]
                    newStats[i][j][2] += oldStats[indX][indY][2]
                else:
                    newStats[i][j][1] += 1
                    if steps==1:
                        newStats[i][j][2] = 1
    return newStats

(or equivalently, for one step (using dfs - recursive):

class winLoss:
    def __init__(self, N):
        self.win = 0 
        self.loss = 0
        self.N = N
    def winLoss(self, x, y, n):
        if x < 0 or y < 0 or x >= self.N or y >= self.N:
            self.loss += 1
            return
        if n == 0:
            self.win += 1
            return
        self.winLoss(x - 1, y, n-1)
        self.winLoss(x, y - 1, n-1)
        self.winLoss(x+1, y, n-1)
        self.winLoss(x, y+1, n-1)



    wl = winLoss(n)
    wl.winLoss(i, j, n)
for any i,j start point and n (size of square)
)

The winLoss_stat returns three values for starting point at each square i, j: 
[numbers of survive cases, numbers of die cases before or at k steps, numbers of death exactly at step k]

The results are as the following for n=4 (4X4), steps=4:

              0              1              2             3
0  [58, 24, 12]   [93, 34, 18]   [93, 34, 18]  [58, 24, 12]
1  [93, 34, 18]  [150, 46, 28]  [150, 46, 28]  [93, 34, 18]
2  [93, 34, 18]  [150, 46, 28]  [150, 46, 28]  [93, 34, 18]
3  [58, 24, 12]   [93, 34, 18]   [93, 34, 18]  [58, 24, 12]

This translates to the following probabilities for 
1. death before or at k steps:
          0         1         2         3
0  0.292683  0.267717  0.267717  0.292683
1  0.267717  0.234694  0.234694  0.267717
2  0.267717  0.234694  0.234694  0.267717
3  0.292683  0.267717  0.267717  0.292683

2. death exactly at k steps:
          0         1         2         3
0  0.146341  0.141732  0.141732  0.146341
1  0.141732  0.142857  0.142857  0.141732
2  0.141732  0.142857  0.142857  0.141732
3  0.146341  0.141732  0.141732  0.146341

The results can be verified by looking at the numbers of win-loss from step 1 to 3 for n=3:

winLoss_stat(3, 1)
           0          1          2
0  [2, 2, 1]  [3, 1, 1]  [2, 2, 1]
1  [3, 1, 1]  [4, 0, 0]  [3, 1, 1]
2  [2, 2, 1]  [3, 1, 1]  [2, 2, 1]

winLoss_stat(3, 2)
           0           1          2
0  [6, 4, 2]   [8, 5, 2]  [6, 4, 2]
1  [8, 5, 2]  [12, 4, 4]  [8, 5, 2]
2  [6, 4, 2]   [8, 5, 2]  [6, 4, 2]

winLoss_stat(3, 3)
             0            1            2
0  [16, 12, 4]  [24, 13, 8]  [16, 12, 4]
1  [24, 13, 8]  [32, 20, 8]  [24, 13, 8]
2  [16, 12, 4]  [24, 13, 8]  [16, 12, 4]