OI-wiki 图论专题图上随机游走问题的三种解法与复杂度进阶【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki本篇技术指南以 OI-wiki 仓库中 docs/graph/graph-random-walk.md 为核心脉络系统讲解求棋子从起点随机游走到达终点的期望时间这一类经典问题。文章沿网格图、稀疏图、一般图三种图结构逐层深入依次给出朴素高斯消元、直接消元法、主元法、基于 Cayley–Hamilton 定理与 Berlekamp–Massey 算法的递推法以及借助稳态分布与有向图矩阵树定理的线性代数解法。读完本文你将掌握随机游走问题的统一矩阵建模方式以及针对不同图规模选择合适算法的判断依据与完整推导过程。问题定义与矩阵建模形式化定义给定一张有向简单图 $G(V, E)$$V{v_1, v_2, \cdots, v_{|V|}}$和起点 $s \in V$、终点 $t \in V$每条边 $e\left(x, y\right)$ 有正权值 $w_e$满足对任意 $x \in V \backslash\left{t\right}$ 有$$ \sum_{\left(x, y\right) \in E} w_{\left(x, y\right)}1 $$且对于任意点 $x$ 都存在一条从 $x$ 出发到达 $t$ 的路径。一枚棋子从起点出发每秒从当前所在点 $x$ 以 $w_{(x, y)}$ 的概率选择出边 $\left(x, y\right)$ 并走向 $y$到达终点则停止。所求即为期望花费时间。注意两个关键约束一是每条边权值为正二是除终点外每个点的出边概率和为 $1$这保证 $P$ 是一个截断后的随机矩阵三是图中所有点都能到达终点这保证过程几乎必然终止、期望有限。矩阵形式定义矩阵 $P$$$ P_{x, y} \begin{cases} w_{(x, y)} \text{if } (x, y) \in E \text{ and } x \neq t \ 0 \text{if } (x, y) \notin E \text{ or } xt \end{cases} $$要求的答案即为$$ \sum_{k \geq 0} k \times\left(P^k\right)_{s, t} $$其中 $\left(P^k\right)_{s, t}$ 表示走了 $k$ 步第一次到达终点的概率。当图有限且所有点都能到达终点时由 $P$ 的定义可以证明其特征值都小于 $1$所以答案一定是收敛的。这一收敛性论证正是后文稀疏图解法中最短递推式存在的基石。为方便描述下文如无特殊说明均用 $n$ 代指 $|V|$$m$ 代指 $|E|$稀疏图指边数和点数同阶的图。网格图从 $O(R^6)$ 到 $O(R^3)$例题 1Circles of Waiting一枚棋子起始被放在平面直角坐标系的 $(0,0)$ 点。每秒棋子会随机移动假设它当前在 $(x, y)$下一秒有 $p_1$ 的概率移动到 $(x-1, y)$$p_2$ 的概率移动到 $(x, y-1)$$p_3$ 的概率移动到 $(x1, y)$$p_4$ 的概率移动到 $(x, y1)$。保证 $p_1p_2p_3p_41$。求期望经过多少时间它会移动到一个离原点的欧几里得距离大于 $R$ 的位置。数据范围 $0 \leq R \leq 50$$p_1, p_2, p_3, p_40$答案对 $10^97$ 取模。这是一道典型的网格图上随机游走问题状态数约 $O(R^2)$四个方向转移只涉及上下左右四邻域具有极强的局部性。下文三种做法展示了如何利用这种局部性逐步压缩复杂度。朴素做法全量高斯消元记 $f(i, j)$ 表示棋子在 $(i, j)$ 时移动到一个离原点的欧几里得距离大于 $R$ 的位置的期望时间转移方程为$$ f(i, j) \begin{cases} p_1 f(i-1, j) p_2 f(i, j-1) p_3 f(i1, j) p_4 f(i, j1) 1 i^2 j^2 \leq R^2 \ 0 i^2 j^2 R^2 \end{cases} $$由于转移并不存在拓扑序$f$ 的四个邻域互为依赖无法按 DAG 顺序递推需要使用高斯消元求解时间复杂度 $O\left(R^6\right)$无法通过本题$R$ 最大为 50 时 $R^6$ 不可接受。关于高斯消元的实现细节与数值稳定性讨论可参考仓库中的 docs/math/numerical/gauss.md。直接消元法利用系数稀疏性注意到需要消元的方程中系数大多数都是 $0$消元时只对值非 $0$ 的位置进行计算就可以降低复杂度。考虑消元的过程将方程按照在坐标系中从上到下、同一层中从左到右的顺序进行消元。将已经消元过的方程染成黄色与黄色点相邻的点染成绿色其余点染成黑色如下图所示接下来要对下一个绿色格子对应的方程进行消元。关键在于两个只有在这个方程中只有绿色格子和它下方的第一个黑色格子对应的变量系数可能不为 $0$而只有绿色格子和它下方的第一个黑色格子对应的方程中当前格子对应的变量系数可能不为 $0$。注意到绿色格子只有 $O(R)$ 个所以单个方程消元的时间复杂度为 $O\left(R^2\right)$一共只有 $O\left(R^2\right)$ 个方程因此总时间复杂度降低为 $O\left(R^4\right)$可以通过本题。该图的原图.tex源文件位于 docs/graph/images/graph-random-walk-1.tex。从实现角度看直接消元法的核心收益在于虽然仍需对 $O(R^2)$ 个方程做消元但每个方程的非零元被压缩到 $O(R)$ 量级消元中的内层循环只需扫描这些候选位置从而把朴素全矩阵消元的 $O(R^6)$ 降为 $O(R^4)$。它本质上是按图结构稀疏存储 定向消元顺序的组合。主元法把规模压到 $O(R)$方程和变量都有 $O\left(R^2\right)$ 个如果能将规模缩小至 $O(R)$那么朴素的高斯消元就能通过。将每行从左到右第一个格子对应的变量设为主元共 $2R1$ 个设法将其他格子对应的变量用关于这些主元的线性函数表示。从左到右逐列考虑对于当前列的每个格子 $(i, j)$注意到 $f(i, j)$、$f(i-1, j)$、$f(i, j-1)$、$f(i, j1)$ 都是已知的关于主元的线性函数将转移方程移项有$$ f(i1, j)\frac{f(i, j)-p_1 f(i-1, j)-p_2 f(i, j-1)-p_4 f(i, j1)-1}{p_3} $$这样就能得到 $f(i1, j)$ 关于主元的线性函数表示。如果 $(i1, j)$ 已经离原点欧几里得距离超过 $R$则可以得到一个方程 $f(i1, j)0$。最终会得到 $2R1$ 个方程对这些方程进行高斯消元即可。复杂度分析分两阶段递推关于主元的线性函数阶段共有 $O\left(R^2\right)$ 个变量递推单个变量需要花费 $O(R)$ 的时间合计 $O(R^3)$对 $O(R)$ 个方程做高斯消元$O(R^3)$。总时间复杂度为 $O\left(R^3\right)$可以通过本题。从实现角度看主元法可以类比线性代数中的变量代换思想先用 $2R1$ 个自由变量线性表出全部 $O(R^2)$ 个变量每步只需 $O(R)$ 的合并同类项开销再把这 $2R1$ 个最终约束边界上的 $f0$代入消元。相比直接消元法它以维护线性表达式为代价换取了消元矩阵规模的根本性缩减。两种做法的对比维度主元法直接消元法网格图最坏时间复杂度$O(n\sqrt{n})$网格长宽均为 $O(\sqrt{n})$ 时最高$O\left(n^2\right)$实数精度较差线性表达式的系数累积误差更大较优障碍/零概率边每个障碍或零概率边需增加一个主元数量超过 $O(R)$ 时复杂度上升复杂度不变推广到特殊转移方程可处理 $f(i,j)p_1f(i1,j)p_2f(i,j1)p_3f(\operatorname{pre}(i,j))1$ 一类非邻域转移其中 $\operatorname{pre}(i,j)(x,y)\ (x\le i,\ y\le j)$ 由题目给定复杂度分析不再适用网格图邻接矩阵行列式不能使用可用直接消元法优化时间复杂度总结从时间复杂度看主元法在网格图上的最坏时间复杂度为 $O(n\sqrt{n})$直接消元法最坏为 $O(n^2)$主元法较优从精度看需要进行实数计算而非取模的题目中直接消元法精度优于主元法从适用性看两种做法各有侧重需要根据具体题目分析采用不同的做法。稀疏图Cayley–Hamilton 定理 Berlekamp–Massey 算法例题 2Expected Value给定一张简单无向连通稀疏图 $G(V, E)$一枚棋子起始被放在 $v_1$每秒棋子会从与当前点相连的边中等概率选择一条走到出边指向的点求到达 $v_n$ 的期望时间。$n \leq 2000$答案对 $p$ 取模$p$ 是在区间 $\left[10^9, 1.01 \times 10^9\right]$ 内随机生成的一个质数。当 $n$ 高达 2000 时$O(n^3)$ 的高斯消元已不可行需要全新的思路把期望转化为存活概率序列再用线性递推工具在 $O(nmn^2)$ 内求解。基础知识零化多项式与 Cayley–Hamilton 定理定义 4.1所有满足 $p(A)0$ 的多项式 $p(\lambda)$ 称为矩阵 $A$ 的零化多项式。定义 4.2记 $I_n$ 表示 $n$ 阶单位矩阵定义一个 $n\times n$ 矩阵 $A$ 的特征多项式为 $p(\lambda)\det(\lambda I_n - A)$其中 $\det$ 表示行列式。不难发现一个 $n$ 阶矩阵 $A$ 的特征多项式的次数不超过 $n$。定理 4.2Cayley–Hamilton 定理任意矩阵的特征多项式是它的零化多项式。所以一个 $n$ 阶矩阵的次数最小的零化多项式的次数也不超过 $n$。这给出了线性递推的阶数不超过 $n$的代数保证。仓库中 docs/math/linear-algebra/char-poly.md 对这一主题有完整展开它定义了特征值与特征向量、阐述了最小多项式整除任一零化多项式特别地最小多项式整除特征多项式并指出特征多项式可与常系数齐次线性递推联系起来结合 Cayley–Hamilton 定理与多项式取模可加速求矩阵幂次——与本节的论证一脉相承。求解原问题注意到期望走的时间满足 $E(t)\sum_{i\geq 0}\Pr[ti]$。如果能求出走了 $i$ 步还没有结束的概率对所有 $i\ge 0$ 求和即为答案。记 $f(i, j)$ 表示走了 $i$ 步、当前停留在 $j$、且没有走到过 $n$ 的概率那么$$ f(i,j)\sum_{(k,j)\in E}\frac{f(i-1,k)}{\deg_k}\quad(j\neq n) $$其中 $\deg_k$ 表示 $k$ 的度数。关键观察$f$ 的转移与 $i$ 无关可以认为一次转移是乘上了一个矩阵即 $f_{i1}f_iM$。由于 $M$ 的最小零化多项式次数不超过 $n$所以 $f$ 的最短递推式长度也不超过 $n$故 $\Pr[ti]\sum_{j1}^{n-1}f(i,j)$ 的最短递推式长度也不超过 $n$。算法流程如下在 $O(nm)$ 时间内求出 $\Pr[t0],\Pr[t1],\cdots,\Pr[t3n]$使用Berlekamp–Massey 算法在 $O(n^2)$ 时间内求解出 $\Pr[ti]$ 的最短递推式。关于 Berlekamp–Massey 算法本身的原理仓库中 docs/math/berlekamp-massey.md 给出了完整定义与增量式构造过程给定长为 $n$ 的数列如果其最短递推式阶数为 $m$算法能在 $O(nm)$ 时间内求出每个前缀的最短递推式最坏复杂度 $O(n^2)$实现时只需存储当前递推系数与上次调整时的递推系数空间复杂度 $O(n)$仓库内还附有参考实现。由递推式求总和生成函数取 $x1$考虑求一个 $k$ 阶线性递推序列 $a$ 的生成函数。不妨设 $i\ge i_0$ 时 $a_i\sum_{j1}^k c_j a_{i-j}$记 $a$ 和 $c$ 的生成函数为 $A(x)$ 和 $C(x)$那么$$ A(x)A(x)C(x)A_0(x) $$其中 $A_0(x)$ 是由 $ii_0$ 的项决定的。回到原问题由于我们能求出 $\Pr[ti]$ 的最短递推式则我们可以求出 $C(x)$ 和 $A_0(x)$定义与上一段相同移项得$$ A(x)\frac{A_0(x)}{1-C(x)} $$要求的 $\sum_{i\geq 0}[x^i]A(x)$ 恰好等于 $A(1)$将 $x1$ 代入原问题求解即可。由于模数是随机质数可以认为分母不会为 $0$即 $1-C(1)\not\equiv 0\pmod p$ 的概率极高。复杂度总结整个算法在 $O(nmn^2)$ 的时间复杂度内解决本题如果图 $G$ 的点数与边数同阶即稀疏图时间复杂度可以认为是 $O(n^2)$。一般图稳态分布与有向图矩阵树定理例题 3Frank给定一张简单强连通有向图 $G(V,E)$对于所有 $1\le s\le n$、$1\le t\le n$、$s\neq t$回答下面的问题一枚棋子起始被放在 $v_s$每秒棋子会从当前点的出边中等概率选择一条走到出边指向的点求到达 $v_t$ 的期望时间。$3\le n\le 400$。本题要求回答所有点对之间的期望到达时间共 $O(n^2)$ 个答案且只保证强连通没有网格或稀疏结构可利用需要完整的矩阵分析。分析和转化记 $p_{i,j}$ 表示棋子在 $i$ 时选择出边 $(i,j)$ 走到 $j$ 的概率特别地出边不存在时概率为 $0$。记 $f_{i,j}$ 表示 $i$ 随机游走到 $j$ 的期望时间特别地 $f_{i,i}0$。当 $i\neq j$ 时转移方程为$$ f_{i,j}1\sum_{1\leq k\leq n}p_{i,k}f_{k,j} $$当 $ij$ 时记 $g_i$ 表示从 $i$ 开始随机游走第一次回到 $i$ 的期望时间那么$$ f_{i,i}1-g_i\sum_{1\le k\le n}p_{i,k}f_{k,i} $$将转移方程写成矩阵形式记 $P$ 表示转移矩阵$F$ 表示答案矩阵$I$ 表示 $n$ 阶单位矩阵$J$ 表示 $n$ 阶全 $1$ 矩阵$G$ 是一个 $n$ 阶矩阵满足 $G_{i,i}g_i$其他位置为 $0$则$$ FJ-GPF $$如果能求出 $G$就只需要解方程$$ (I-P)FJ-G $$问题转化为两个子问题如何求 $G$即每个点的首次返回期望以及如何处理 $(I-P)$ 不满秩带来的求解困难。G 的求法稳态分布定义 5.1定义一个 $n$ 阶转移矩阵 $P$ 的稳态分布为一个 $n$ 维向量 $\pi$满足 $\sum_{i1}^{n}\pi_{i}1$$\pi P\pi$且 $\pi$ 每一维的值都在区间 $[0,1]$ 内。稳态分布的实际意义很直观如果某个时刻棋子有 $\pi_i$ 的概率停留在 $v_i$则在之后的任意时刻棋子仍然满足这个概率分布。可以在 $O(n^3)$ 时间内通过高斯消元解方程求出 $\pi$。定理 5.1对于任意 $1\le i\le n$有 $\pi_i g_i1$。证明由 $FJ-GPF$移项得 $GPFJ-F$。两边同时在左边乘上 $\pi$ 有$$ \pi G \pi PF \pi J - \pi F $$由 $\pi$ 的定义有 $\pi P\pi$故 $\pi G\pi J$所以$$ \pi_i g_i\sum_{j1}^n\pi_j1 $$原命题得证。由此通过引入稳态分布可以在 $O(n^3)$ 时间内求解 $G$。$g_i1/\pi_i$ 正是马尔可夫链理论中著名的平均返回时间结论。求解原问题处理不满秩方程在解方程的过程中发现$(I-P)$ 并不满秩不能通过乘逆矩阵的方法求解。为此引入有向图上的矩阵树定理。定义 5.2定义一个有向图 $G(V,E)$ 的以 $r\in V$ 为根的有向生成树是 $G$ 的一个子图 $T(V,A)$满足对于任意 $i\neq r$$i$ 的出度为 $1$$r$ 的出度为 $0$$T$ 中不存在环。引理 5.1有向图上的矩阵树定理对于一个有向图 $G$记 $D$ 表示其出度矩阵$D_{i,i}d_i$$D_{i,j}0\ (i\neq j)$$d_i$ 为 $i$ 的出度$A$ 表示其邻接矩阵则其以 $r$ 为根的有向生成树个数为 $D-A$ 去掉第 $r$ 行第 $r$ 列后的行列式。该引理与仓库中 docs/graph/matrix-tree.md 所述的有向图情形一致那里定义出度 Laplace 矩阵 $L^\mathrm{out}(G)D^\mathrm{out}(G)-A(G)$并证明以 $k$ 为根的根向/叶向树形图个数可由对应主子式给出。矩阵树定理在本问题中的作用是给出秩的严格证明而非直接计数。定理 5.2对于一个强连通图 $G(V,E)$ 的转移矩阵 $P$$(I-P)$ 的秩为 $n-1$。证明因为对矩阵某一行乘上非零常数其秩不改变所以将 $(I-P)$ 的第 $i$ 行乘上 $v_i$ 的出度得到新矩阵 $L$只需证明 $L$ 的秩为 $n-1$。由于 $L$ 每行的和均为 $0$对 $L$ 的所有列向量求和会得到零向量即这些向量线性相关所以 $L$ 的秩不为 $n$。不难发现 $L$ 等于图 $G$ 的出度矩阵减去其邻接矩阵。由引理 5.1$L$ 去掉第 $i$ 行第 $i$ 列后的行列式表示以 $v_i$ 为根的有向生成树个数。由于 $G$ 是强连通的以任意点为根的有向生成树个数均不为 $0$即 $L$ 去掉第 $i$ 行第 $i$ 列之后仍然满秩。因为加上一列秩不会变小所以 $L$ 去掉第 $i$ 行后所有行向量线性无关故 $L$ 的秩为 $n-1$。特解与调整完成求解回到原问题将方程写成 $AXB$ 的形式其中 $A$、$B$ 已知需要求解 $X$。由于 $A$ 不满秩解有无数个首先求出一组特解。将 $A$ 和 $B$ 一起做高斯消元把 $A$ 的前 $n-1$ 行消成只有主对角线和第 $n$ 列有值的形式最后一行消成全 $0$即下列形式$$ \begin{bmatrix} 1 0 0 \cdots 0 a_1 \ 010\cdots0a_2\ 001\cdots0a_3\ \vdots\vdots\vdots\ddots\vdots\vdots\ 000\cdots1a_{n-1}\ 000\cdots00 \end{bmatrix} X \begin{bmatrix} b_{1,1}b_{1,2}b_{1,3}\cdotsb_{1,n-1}b_{1,n}\ b_{2,1}b_{2,2}b_{2,3}\cdotsb_{2,n-1}b_{2,n}\ b_{3,1}b_{3,2}b_{3,3}\cdotsb_{3,n-1}b_{3,n}\ \vdots\vdots\vdots\ddots\vdots\vdots\ b_{n-1,1}b_{n-1,2}b_{n-1,3}\cdotsb_{n-1,n-1}b_{n-1,n}\ 000\cdots00 \end{bmatrix} $$令 $X_{n,i}0$可以解出一组特解记为 $Y$。接下来将特解调整为真正的解。注意到 $X_{n,i}0$考虑组合意义有 $Y_{i,j}1Y_{j,j}P_{i,k}X_{k,j}$不难解出$$ X_{i,j}Y_{i,j}-Y_{j,j} $$最终在 $O(n^3)$ 的时间复杂度内解决了这个问题——即使面对 $n400$ 的规模与全部 $O(n^2)$ 个点对询问三次方级别的高斯消元依然可行。三种图结构解法的横向对比将本文三种策略放在一起可以清晰看到随机游走问题的算法选型逻辑图结构核心思想关键工具复杂度网格图朴素全量高斯消元期望转移方程$O(R^6)$网格图直接消元法利用系数稀疏性定向消元消元顺序 稀疏存储$O(R^4)$网格图主元法主元线性表出压缩规模主元选取 高斯消元$O(R^3)$稀疏图概率序列 最短递推式Cayley–Hamilton 定理、Berlekamp–Massey 算法、生成函数$O(nmn^2)$一般图矩阵方程 稳态分布有向图矩阵树定理、高斯消元$O(n^3)$三条路线的核心差异在于如何应对转移矩阵的环网格图上借助几何局部性压缩消元规模稀疏图上利用递推阶数不超过 $n$的代数性质绕过直接消元一般图上则用稳态分布与矩阵树定理给出方程的秩结构再以特解 调整完成求解。参考浅谈图模型上的随机游走问题。IOI2019 中国国家候选队论文集pp. 17-26。本文相关仓库资源Berlekamp–Massey 算法完整讲义见 docs/math/berlekamp-massey.md特征多项式与 Cayley–Hamilton 定理见 docs/math/linear-algebra/char-poly.md有向图矩阵树定理见 docs/graph/matrix-tree.md高斯消元见 docs/math/numerical/gauss.md。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考