4

行列で表される島があります。あなたは島のどこかにいます(x,y)。あなたがn時間をジャンプする場合、あなたが生き残る確率はどれくらいですか？サバイバルとは、nジャンプした後、島にいる必要があることを意味します。

私の解決策：flood fill algorithmすべての方向（つまり、N、W、E、S）に移動できるように適用し、nジャンプする前に島を離れているかどうかを確認してから、 failureカウンターをインクリメントします。それ以外の場合は、successカウンターをインクリメントします。

考えられるすべてのパスを繰り返した後、答えは（（成功）/（成功+失敗））です。指数関数的な時間がかかります。

あなたからの私の質問は、動的計画法または他のプログラミング手法を使用して、この問題を多項式時間で実行できるかどうかです。もしそうなら、そのテクニックの背後にあるコンセプトを教えていただけますか？

編集：私のコード

#include<iostream>

using namespace std;

double probability_of_survival(int n, int m, int x, int y, int jumps) {
    int success = 0;
    int failure = 0;
    probability_of_survival_utility_func(n, m, x, y, 0, jumps, &sucess, &failure);
    return (double)((success)/(failure+success));
}

void probability_of_survival_utility_func(int n, int m, int x, int y, int jump_made, int jumps, int *success, int *failure) {
    if(x > m || x < 0 || y > n || y < 0) { (*failure)++; return;}
    if(jump_made == jumps) { (*success)++; return;}
    probability_of_survival_utility_func(n, m, x+1, y, jump_made++, jumps, success, failure);
    probability_of_survival_utility_func(n, m, x, y+1, jump_made++, jumps, success, failure);
    probability_of_survival_utility_func(n, m, x-1, y, jump_made++, jumps, success, failure);
    probability_of_survival_utility_func(n, m, x, y-1, jump_made++, jumps, success, failure);
}
4

2 に答える 2

4

この問題は、マルコフ行列によってきちんと説明されています。次の方法で問題をグラフに変換します。行列の行を座標に、つまり可能なすべての にマッピングし(x,y) -> iます。サイトが接続されている場合にのみ、対称隣接行列Aを構築します。すべてのデス サイトは 1 つのサイトにマッピングされ、そのようなプロパティを持ちます。つまり、吸着状態です。行は行列を正規化します。開始位置に対応する開始ベクトルを使用して、次の積を取ります。(i,j)=1(x1,y1)->i, (x2,y2)->jA[i,i]=1A[i,j!=i]=0p=[0,0,0,...,1,...,0,0]

 (A**k) . p

そして、ライブサイトを合計すると、生存確率が得られます. 分析のために、ここでのメモのn数は、島の生きているサイトの数です。複雑さはきちんとバインドされており、最もコストのかかる操作は行列累乗A**kです。これは単純にO(n**3 * k)で実行できますが、最初に のコストで行列を対角化しO(n**3)、固有値をべき乗できると思います。

視覚的な例:

赤い開始点と隣接行列を持つ島:

ここに画像の説明を入力

ステップの関数として計算された生存確率:

ここに画像の説明を入力

Python 実装:

from numpy import *

# Define an example island
L = zeros((6,6),dtype=int)
L[1,1:2] = 1
L[2,1:4] = 1
L[3,1:5] = 1
L[4,2:4] = 1

# Identify alive sites
alive = zip(*where(L))
N = len(alive)

# Map the entries onto an index for easy access
ID = dict(zip(alive, range(N)))

# Create adj. matrix, the final index is the dead site
def connect(x, horz, vert):
    s = (x[0]+horz, x[1]+vert)
    if s not in ID: A[ID[x], N] += 1
    else          : A[ID[x], ID[s]] += 1
    
A = zeros((N+1,N+1))
for x in alive:
    connect(x,  1, 0)
    connect(x, -1, 0)
    connect(x,  0, 1)
    connect(x,  0,-1)

# Define the dead site as adsorbing, and row normalize
A[N,N] = 1
A /= A.sum(axis=1)[:,newaxis]


# Define the initial state
inital = (3,2)
p0 = zeros(N+1)
p0[ID[inital]] = 1

# Compute survival prob. as a function of steps
steps = 20
A2 = A.copy()
S = zeros(steps)
for t in xrange(steps):
    S[t] = 1-dot(A2.T,p0)[-1]
    A2   = dot(A2, A)

# Plot results
import pylab as plt
plt.subplot(121)
LSHOW = L.copy()
LSHOW[inital] = 2
plt.imshow(LSHOW,interpolation='nearest')
plt.subplot(122)
plt.imshow(A,interpolation='nearest')
plt.figure()
plt.plot(range(steps), S,'ro--')
plt.show()
于 2012-08-28T15:19:16.833 に答える
3 
f(x,y,0) = 0     if (x,y) is not in the island
           1     otherwise

f(x,y,i) = 0     if (x,y) is not in the island
           otherwise: 1/4 * f(x+1,y,i-1) + 
                      1/4 * f(x-1,y,i-1) + 
                      1/4 * f(x,y+1,i-1) + 
                      1/4 * f(x,y-1,i-1)

動的計画法を使用する2n+1 x 2n+1 x n+1と、3 次元配列を作成し、この式に従って から開始して まで埋めることi=0ができますi=n。

最後のソリューションはf(0,0,n)配列にあります。(座標で元の (x,y) を (0,0) として設定し、必要な調整を行うことを忘れないでください)。

複雑さはO(n^3)- 行列のサイズです。

この解決策は疑似多項式であるため、将来の回答でこの問題が NP-Hard であることが示されている場合 (そうであるかどうかはわかりません)、矛盾していません。

PS実際の実装では、正確な答えが必要な場合は、倍精度の数値を使用する場合は特に注意してください。特に、ステップ数が多い場合は、数値誤差が大きくなる可能性があります。

于 2012-08-28T12:39:13.557 に答える