algorithm - 我们可以在不模拟/近似的情况下通过算法找到 2D 随机游走的预期命中时间吗？

假设我们给定了一些包含原点/起始位置的吸收边界，并且我们进行简单的随机游走（上/下/左/右等概率）。为简单起见，假设我们可以访问一个函数，该函数告诉我们 (x,y) 是否越过障碍

我知道模拟这很简单，并且计算击球前的预期时间很容易在数值上近似 - 但是有没有一种简洁的算法方法来获得确切的答案？

我试图让一些东西与 DP/DFS 一起工作，但递归中缺少基本案例似乎让我很困惑。不知道除了模拟之外是否有办法做到这一点/也许还有一些更深入的数学

标签： algorithmdynamic-programmingdepth-first-searchrandom-walk

对障碍内的状态进行编号，形成转移概率矩阵A（A [i,j] 是从状态 j 到状态 i 的概率），求解矩阵方程A x + 1 = x对于x（其中1是全为向量，等价于 ( A − I ) x = 1，其中I是单位矩阵）。元素x [i] 给出了从 i 开始的预期吸收时间。