查看源代码：
random-flow-maze-gen-algo.md

---
title: 随机汇流算法
createTime: 2025/2/22
categories: 
    - IT
tags:
    - maths
---

## 符号

我们记 $\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')$ 一定是一颗树，证明如下：

### 证明

1. 由于 $G'$ 是 $G$ 的生成子图，$G'$ 是一个 DAG；
2. $|E'| = |V\setminus\{T\}| = |V|-1$；
3. 任意顶点在 $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

在游戏《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$ 的图，且具有较大的随机性。

步骤：

1. 递归建四个 $2^{n-1} \times 2^{n-1}$ 的块；
2. 随机选择源块和汇块，并由此确定块间连接方向；
   > 注：确定了源块与汇块之后，连接方向只有两种模式：
   $$
   \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}
   $$
3. 将非汇块的块内汇点旋转至该块的出边方向（若有多个出边方向，则旋转至随机一个），将汇块的块内汇点旋转至图形外侧；
4. 按照相邻块的块间连接方向，尽可能地将相邻的节点相连，除非节点的出度为 $2$；
5. 连接完成之后，汇块的块内汇点就会成为大块的新汇点。

## 关联

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

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