随机汇流算法

约 963 字大约 3 分钟

2025-2-22

符号

我们记 $\operatorname{choice}(S)$ 代表在集合中随机选取一个元素的结果。

给定一个有向无环图 $G=(V,E)$ ，且存在唯一的汇点 $T$ 使得 $\operatorname{od}(T)=0$ .

对于每个非汇点 $v$ ，从它的出边集 $E(v)$ 中随机选择一条边，形成新边集 $E'$ ；
形式化地， $E'=\set{\operatorname{choice}(E(v)) \mid v \in V\setminus\{T\}}$ .

我们得到的 $G'=(V,E')$ 一定是一颗树，证明如下：

由于 $G'$ 是 $G$ 的生成子图， $G'$ 是一个 DAG；
$|E'| = |V\setminus\{T\}| = |V|-1$ ；
任意顶点在 $G'$ 中必定与 $T$ 连通。否则设另一连通块中拓扑序最大的为 $T'$ ，于是有 $\operatorname{od}(T')=0$ ，与 $G$ 的定义矛盾。

根据定义， $G'$ 是以 $T$ 为根的内向树。

由于每个点选择独立，总的组合数为：

M = \displaystyle\prod_{v \in V\setminus\{T\}} \operatorname{od}(v)

我们将 $M$ 称为这个图的多样性，代表根据该算法可生成的不同树的数量。

如果 $\operatorname{choice}(S)$ 函数的实现是均匀的，那么生成每一种树的概率都是均等的，都为 $\dfrac{1}{M}$ .

无法生成所有迷宫。

在游戏《Minecraft》中，用简单的机械只能实现 0-1 随机数，且远距离通信严重受限。此时，我们可以选择一个满足以上条件的 DAG，即可无需远距离通信，实现随机迷宫生成。进一步地，若限制 $\operatorname{od}(v)\le2$ ，则每次只需在即可只用 0-1 随机数实现该算法。

我们设迷宫是 $N \times N$ 的网格图的生成子图，在我们选择的 DAG 中有 $n$ 个出度为 $2$ 的节点，则有 $M=2^n$ .

由于 $|E| \le 2N^2-2N$ ，且 $|E| = 2n + (N^2-n-1) = N^2+n-1$ ，整理可得

n \le (N-1)^2

即 $M_{\max}=2^{(N-1)^2}$ .

容易想到，将 $(x,y)$ 向 $(x+1,y), (x,y+1)$ 连边是一种使 $M$ 最大的方案，然而使用这种方案的迷宫都太过简单。

因此，我们不能只将多样性看作评估 DAG 好坏的指标，随机性也应该是这样的指标。

分治建图适用于建 $2^n\times2^n$ 的图，且具有较大的随机性。

步骤：

递归建四个 $2^{n-1} \times 2^{n-1}$ 的块；
随机选择源块和汇块，并由此确定块间连接方向；
注：确定了源块与汇块之后，连接方向只有两种模式：
$\begin{array}{c|c} \text{相对} & \text{相邻} \\ \hline A \rightarrow B & A \rightarrow B\\ \downarrow \qquad \downarrow & \downarrow \qquad \uparrow\\ C \rightarrow D & C \rightarrow D \end{array}$
将非汇块的块内汇点旋转至该块的出边方向（若有多个出边方向，则旋转至随机一个），将汇块的块内汇点旋转至图形外侧；
按照相邻块的块间连接方向，尽可能地将相邻的节点相连，除非节点的出度为 $2$ ；
连接完成之后，汇块的块内汇点就会成为大块的新汇点。

最近，网络上出现了一种叫做希尔伯特前瞻算法的 Minecraft 随机迷宫生成算法，随机汇流算法也正是受到了该算法的启发。

事实上，希尔伯特前瞻算法相当于用希尔伯特曲线序作为 DAG 拓扑序的随机汇流算法。因此，它可以看作是一个随机汇流算法的巧妙特例。