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，使得(i,j)=1当且仅当站点(x1,y1)->i, (x2,y2)->j连接时。所有死亡地点都将映射到单个地点并具有这样的属性A[i,i]=1，A[i,j!=i]=0即它是一个吸附状态。行归一化矩阵。p=[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+13 维数组，并根据此公式填充它，从 开始i=0并一直到i=n。

最后你的解决方案在f(0,0,n)数组中。（请记住在您的坐标中将原始 (x,y) 设置为 (0,0)，并进行必要的调整）。

复杂性是O(n^3)- 矩阵的大小。

请注意，这个解决方案是pseudo-polynomial，所以如果任何未来的答案表明这个问题是 NP-Hard （不知道是否是） - 它并不矛盾。

PS 对于实际实现 - 如果您需要准确的答案 - 在使用双精度数字时要非常小心 - 特别是对于大量步骤，因为携带的数字错误可能会变得很重要。

于 2012-08-28T12:39:13.557 回答