algorithm - 计算带周期的随机迷宫行走的概率

Question

我正在研究 this programming challenge一只 Frog 在迷宫中随机行走，一路上有各种障碍物和炸弹，可以通往潜在的导出。

挑战是计算 Frog 到达导出的概率。

我的问题是我不知道如何处理循环 - Frog 可以在两个或多个空间之间来回走动的情况。

假设您有:

     BOMB    BOMB
EXIT SPACE 1 SPACE 2 BOMB
     BOMB    BOMB

对于空间 1，到达导出的概率是直接走到导出的概率 (1/4)，或者来回走动直到最终到达导出的概率 (1/4^3 + 1/4 ^6 + 1/4^9...)。对于空间 2，其 (1/4^2 + 1/4^5...)

如果你有多个空闲空间，这会变得更加困惑，例如

     BOMB    BOMB    BOMB
EXIT SPACE 1 SPACE 2 SPACE 3 BOMB
     BOMB    BOMB    BOMB

处理这些循环引入的复杂性的可靠算法是什么？

Answer 1

我会分两个阶段解决这个问题。

第一阶段是确定您可以以任何方式从哪些方格退出。这将让您找到任何没有可能退出的闭环并将其识别为“你被卡住了”。

分析完成后，您可以将 0 分配给所有死胡同和炸弹，将 1 分配给所有导出。所有其他方 block 的退出概率将是一组线性方程的唯一解，其中 p(i, j) = average(p(i', j') 在您可以移动的所有地方在一个回合中。这将是一组 n x m 方程，在 n x m 变量中。用你最喜欢的线性代数技术解决这个问题(我推荐行减少)。

现在对于每个方格，您知道能够退出的确切概率。现在您的答案很简单。

请注意，如果您只是尝试第二种方法的线性代数部分，则线性方程组的解将不是唯一的。第一阶段解决这个问题，以确保您提出正确的解决方案。