带循环随机迷宫行走概率的计算
我正在这个编程挑战上工作，青蛙在迷宫中随机行走，在通往潜在出口的路上有各种各样的障碍物和炸弹。
挑战是计算青蛙到达出口的概率。
我的问题是，我不知道如何处理循环--青蛙可以在两个或多个空间之间来回行走的情况。
想象一下你有：
BOMB BOMB
EXIT SPACE 1 SPACE 2 BOMB
BOMB BOMB对于空间1，到达出口的概率是直接走到出口(1/4)，或者来回走到出口(1/4^3 + 1/4^6 +1/4^9.)。对于空间2 its (1/4^2 +1/4^5.)
如果您有多个空闲空间可供选择，这将更加令人困惑。
BOMB BOMB BOMB
EXIT SPACE 1 SPACE 2 SPACE 3 BOMB
BOMB BOMB BOMB有什么可靠的算法方法来处理这些循环带来的复杂性呢？
回答 3
Stack Overflow用户
发布于 2018-03-26 22:50:27
我会分两个阶段解决这个问题。
第一阶段是找出你可以以任何方式退出的方块。这将使您找到并识别为“您被卡住”的任何封闭循环，没有可能的出口。
一旦分析完成，您可以为所有死胡同和炸弹分配0，并为所有出口分配1。所有其他正方形的退出概率将是一组线性方程组的唯一解，其中p(i, j) = average(p(i', j')在所有地方都可以一次移动。这将是n x m变量中的一组n x m方程。用您最喜欢的线性代数技术来解决这个问题(我建议减少行数)。
现在，对于每一个正方形，你都知道能够退出的确切概率。现在你的答案很直截了当。
请注意，如果您只是尝试第二种方法的线性代数部分，线性方程组的解将不是唯一的。第一阶段解决了这一点，以确保您想出了正确的解决方案。
Stack Overflow用户
发布于 2018-04-03 14:17:03
迷宫：
+----+----+----+----+----+
| |BOMB|BOMB|BOMB| |
+----+----+----+----+----+
|EXIT| S1 | S2 | S3 |BOMB|
+----+----+----+----+----+
| |BOMB|BOMB|BOMB| |
+----+----+----+----+----+您可以将其映射到每次移动后发生什么的概率矩阵：
// DEAD, ESC, S1, S2, S3
p = [
[ 1.00, 0.00, 0.00, 0.00, 0.00 ], // DEAD
[ 0.00, 1.00, 0.00, 0.00, 0.00 ], // ESCAPED
[ 0.50, 0.25, 0.00, 0.25, 0.00 ], // S1
[ 0.50, 0.00, 0.25, 0.00, 0.25 ], // S2
[ 0.75, 0.00, 0.00, 0.25, 0.00 ] // S3
];因此，沿着中间一行阅读，如果青蛙从S1广场开始，那么在跳完一次之后，就会有：
- 它死亡的概率为0.5；
- 0.25它逃脱的可能性；以及
- 它可能在S2中。
沿着前两行阅读--如果它死了/逃了，那么它会死/逃(分别)的概率是1。
要计算n跳后的概率，只需将概率矩阵提高到幂n。
// DEAD, ESC, S1, S2, S3
p = [
[ 1.00, 0.00, 0.00, 0.00, 0.00 ], // DEAD
[ 0.00, 1.00, 0.00, 0.00, 0.00 ], // ESCAPED
[ 0.50, 0.25, 0.00, 0.25, 0.00 ], // S1
[ 0.50, 0.00, 0.25, 0.00, 0.25 ], // S2
[ 0.75, 0.00, 0.00, 0.25, 0.00 ] // S3
];
function multiply( a, b )
{
if ( a[0].length !== b.length )
{
throw "Matrices must have same a.x/b.y dimensions!";
}
let r = [];
for ( let y = 0; y < a.length; y++ )
{
r[y] = [];
for ( let x = 0; x < b[0].length; x++ )
{
r[y][x] = 0;
for ( let i = 0; i < a[0].length; i++ )
{
r[y][x] += a[y][i] * b[i][x];
}
}
}
return r;
}
// Start at S1
r = [ [ 0, 0, 1, 0, 0 ] ];
// Output probabilities up to 10 decimal places.
dp = 10;
console.log(
"i"
+ " " + "DEAD".padEnd(" ",dp+2)
+ " " + "ESCAPED".padEnd(" ",dp+2)
+ " " + "S1".padEnd(" ",dp+2)
+ " " + "S2".padEnd(" ",dp+2)
+ " " + "S3".padEnd(" ",dp+2)
);
for ( let i = 1; i <= 50; i++ ){
r = multiply( r, p );
if ( i < 10 || i % 10 === 0 )
{
console.log(
i
+ " " + Number(r[0][0]).toFixed(dp)
+ " " + Number(r[0][1]).toFixed(dp)
+ " " + Number(r[0][2]).toFixed(dp)
+ " " + Number(r[0][3]).toFixed(dp)
+ " " + Number(r[0][4]).toFixed(dp)
);
}
}
这个简单的例子表明，它很快收敛到一种状态，在这种状态下，青蛙不太可能还在移动，而且有可能是0.7321428571死了，0.2678571429是活的。
所面临的挑战将是获取输入地图并输出矩阵，然后研究如何优化将矩阵提升为幂的方法，以便快速找到这个收敛点(通过反复对矩阵( p = multiply(p, p); -或其他方法)进行平方)。
Stack Overflow用户
发布于 2018-03-26 23:17:59
建议解一组线性方程组的答案是正确的，但这里有另一种方法。
想象一下，大量的青蛙都放在开始的广场上，开始在迷宫中随意移动。青蛙们都在同一时间踏步。在每个时间步骤中，我们可以使用一个介于0.0到1.0之间的数字来表示每个方格上青蛙的比例。所以：
- 在时间0，所有的青蛙都在起点，所以正方形的重量为1.0，其余的为0.0。
- 在每个时间步骤：
- 炸弹上的任何青蛙都会被摧毁(设定重量为0.0)
- 任何到达出口的青蛙都待在那里
- 任何其他广场上的青蛙平均分布在它的邻居之间。
- 所有青蛙同时移动，因此这些更新需要同时执行。
在运行了许多步骤之后，几乎所有的青蛙都将处于三种状态中的一种：
- 被炸弹摧毁
- 在出口等候
- 困在迷宫中的无限循环
棘手的部分是根据周期的可能性来决定什么时候停止模拟。我们很容易认为，当权数的变化不超过某个小值时，我们就能停下来。然而，如果有一些重复的循环，这是不可能发生的，例如，在没有出口的2x1迷宫中，青蛙会不停地来回跳，重量永远不会收敛。对于这个特定的任务，考虑到迷宫的大小是有限的，您可以将步骤的数目固定为“足够大”的值。或者，您可以首先找到所有不可能退出的方块，并将这些方块排除在收敛测试之外(如另一个答案所建议的)。
https://stackoverflow.com/questions/49500513
复制相似问题
腾讯云开发者
