1 试卷分发算法：串行纵列传递法 vs. 辐射广播树法

教室设置： 50名学生，排列为 10行 × 5列 计时规则（真实模型）： - 拿走自己的试卷： 1秒 - 将整叠试卷传递给一位相邻同学（单一方向）： 1秒 - 每人每秒只能执行一个动作——不能在同一秒内既拿走自己的试卷又传递试卷，也不能同时向两个方向传递（毕竟只有一双手）。 - 所有空闲的学生都在同一时刻并行行动（同步轮次）。

1.1 算法一：串行纵列传递法（传统方法）

1.1.1 伪代码

for col in 1..C:                      # 老师一次处理一列
    老师将试卷交给该列第一排学生            # 1秒

对每一列并行执行：
    student = 该列第一排学生
    while student 手中有试卷:
        student 拿走自己的试卷              # 1秒
        if student 不是该列最后一位:
            student 将剩余试卷传给下一位       # 1秒
        student = 该列下一位学生

1.1.2 示意图 —— 试卷如何移动

老师
  │ 1秒 2秒 3秒 4秒 5秒   （老师依次将试卷交给每一列）
  ▼   ▼   ▼   ▼   ▼
 [生] [生] [生] [生] [生]   ← 第1排（最前排）
  ↓   ↓   ↓   ↓   ↓     拿自己的(1秒) → 传给后面(1秒)，重复
 [生] [生] [生] [生] [生]   ← 第2排
  ↓   ↓   ↓   ↓   ↓
  ⋮   ⋮   ⋮   ⋮   ⋮
  ↓   ↓   ↓   ↓   ↓
 [生] [生] [生] [生] [生]   ← 第10排（最后排）

1.1.3 计时

老师依次将试卷交给 C = 5 列的第一排学生 → 5秒
一列共 R = 10 名学生：除最后一人外，每人都要拿(1秒) + 传(1秒)，最后一人只需拿(1秒) → 2(R−1) + 1 = 2R − 1 = 19秒（5列并行进行）
各列起始时间错开（老师最后才轮到第5列），因此最后一列完成时间为：

列	收到试卷时刻	完成时刻
1	t = 1	t = 20
2	t = 2	t = 21
3	t = 3	t = 22
4	t = 4	t = 23
5	t = 5	t = 24

1.1.4 总用时：24秒

1.2 算法二：辐射广播树法

1.2.1 伪代码

老师将试卷交给正中央的学生                    # 1秒

function 分发(学生, 试卷叠):
    方向 = 该学生尚未服务的相邻方向（前/后/左/右）
    按各方向仍需覆盖的子树大小排序，
        最大/最远的子树排在最前面              # 贪心调度
    for d in 方向:
        向 d 方向的邻座传递一叠试卷              # 每次1秒，依次进行
        分发(邻座_d, 该子叠)                    # 递归，各分支并行推进
    该学生拿走自己的试卷                        # 1秒（放在最后做，
                                               #  因为这一步不影响其他人）

每位收到试卷的学生都成为一个新的局部”枢纽”：他们依次向尚未服务的相邻同学（最多3个方向，若是最初的中心学生则最多4个方向）传递试卷，每秒一次，最后再拿走自己的一份。为了尽快完成，每个枢纽都应优先向最远/剩余任务最大的分支传递——这是在树形网络中最小化广播完成时间的标准最优策略。

1.2.2 示意图 —— 从中心向外扩散的波前

数字 = 每位学生收到试卷的那一秒（中心学生 = 第5排第3列座位）：

 9  8  6  7  8
 9  8  5  7  8
 8  7  4  6  7
 7  6  3  5  6
 6  5  1  4  5   ← 中心学生在 t = 1 收到
 6  5  2  4  5
 7  6  3  5  6
 8  7  4  6  7
 9  8  5  7  8
 9  8  6  7  8

数字 = 每位学生拿完自己试卷（完全完成）的那一秒：

10 10  9  9  9
10 10  9  9  9
 9  9  8  8  8
 8  8  7  7  7
 7  7  6  6  6
 7  7  6  6  6
 8  8  7  7  7
 9  9  8  8  8
10 10  9  9  9
10 10  9  9  9

1.2.3 广播树（按层级，从中心出发）

flowchart TD
    T[老师] -->|1秒| C0["中心 (t=1)"]
    C0 -->|1秒| L1a["右侧 (t=2)"]
    C0 -->|1秒| L1b["左侧 (t=3)"]
    C0 -->|1秒| L1c["前方 (t=4)"]
    C0 -->|1秒| L1d["后方 (t=5)"]
    L1a --> L2a["3个后续邻座 (t=3..5)"]
    L1b --> L2b["3个后续邻座 (t=4..6)"]
    L1c --> L2c["3个后续邻座 (t=5..7)"]
    L1d --> L2d["3个后续邻座 (t=6..8)"]
    L2a --> Ln["……波前持续向外扩散……"]
    L2b --> Ln
    L2c --> Ln
    L2d --> Ln
    Ln --> Corner["距离最远的角落学生完成: t=10"]

1.2.4 总用时：10秒

1.3 对比与节省时间

	串行纵列传递法（传统）	辐射广播树法
总用时	24秒	10秒
瓶颈所在	最后一列、最后一排	距中心最远的角落
并行方式	仅在各列之间并行	四个方向同时并行，每个枢纽都在分流

1.3.1 节省时间：24 − 10 = 14秒（约快 58%）

1.3.2 为什么差距这么大

传统分发方式只在各列之间并行；单列内部仍是一条长达19秒的一维链条。
辐射广播树法在四个方向同时并行推进，并在每个枢纽处持续分流，因此任何一张试卷从中心传到最远角落最多只需9跳（10×5网格），而传统方法最差路径需要多达13跳（横向5跳 + 纵向9跳）。
教室越大、越接近”正方形”，这一优势就会越明显：广播树法的完成时间大致随网格半径增长，而纵列传递法的完成时间则随列数+行数增长。