问题分析

这是一个在有向无环图上的二人零和博弈问题：

• 阿燐（逃跑方）：初始位置 $s_r$，目标是最大化游戏时间
• 阿空（追捕方）：初始位置 $s_k$，目标是最小化游戏时间
• 游戏在 $t$ 时刻强制结束（如果之前未被抓住）
• 双方完全信息，同时移动，不能预知对方下一步

算法思路

核心思想：动态规划 + 线性规划

使用逆序动态规划，从游戏结束时刻向前推导，每个状态用线性规划求解最优策略。

状态定义

设 $f(x, y, k)$ 表示：

• 阿燐在节点 $x$
• 阿空在节点 $y$
• 剩余时间 $k$（即最多还能进行 $k$ 步）
• 在此状态下游戏的期望剩余时间

边界条件

1. 被抓住：$x = y$ 时，$f(x, y, k) = 0$（游戏立即结束）
2. 时间耗尽：$k = 0$ 时，$f(x, y, 0) = 1$（再持续1个时间单位后强制结束）

状态转移

对于状态 $(x, y, k)$：

• 阿燐有 $n_x$ 种移动选择（包括停留）
• 阿空有 $n_y$ 种移动选择（包括停留）
• 双方同时选择行动，形成 $n_x \times n_y$ 种可能结果

转移方程：

$$f(x, y, k) = 1 + \min_{a \in \text{moves}(y)} \max_{b \in \text{moves}(x)} f(b, a, k-1) $$

这体现了：

• 阿燐选择最大化剩余时间
• 阿空选择最小化剩余时间
• 加1表示当前时间步

线性规划求解

将 minimax 问题转化为线性规划：

阿空的线性规划（追捕方）：

$$\begin{align} \min &\quad v \\ \text{s.t.} &\quad v \geq \sum_{j} p_j \cdot f(x_i, y_j, k-1), \quad \forall i \\ &\quad \sum_{j} p_j = 1, \quad p_j \geq 0 \end{align}$$

其中 $p_j$ 是阿空选择移动 $j$ 的概率。

代码解析

主要函数

double gt(int x, int y, int z) {  // f(x, y, z)
    if (x == y) return 0;        // 被抓住
    if (!z) return 1;            // 时间耗尽
    
    if (res[x][y][z] > -1)       // 记忆化
        return res[x][y][z];
    
    // 递归计算所有可能转移
    for (auto next_x : ed[x])
        for (auto next_y : ed[y])
            gt(next_x, next_y, z - 1);
    
    // 构建线性规划矩阵
    int nm = ed[x].size(), nn = ed[y].size();
    for (int i = 1; i <= nm; i++)
        dd[i][0] = 1;            // 约束条件
    for (int i = 1; i <= nn; i++)
        dd[0][i] = 1;            // 目标函数系数
    
    // 填充收益矩阵
    for (int i = 1; i <= nm; i++)
        for (int j = 1; j <= nn; j++)
            dd[i][j] = -gt(ed[x][i-1], ed[y][j-1], z-1);
    
    // 求解线性规划
    init(nn, nm);
    return res[x][y][z] = wkot(nn, nm) + 1;
}

线性规划求解器

代码包含完整的单纯形法实现：

• pivot(): 执行转轴操作
• init(): 处理初始可行解
• wkot(): 主优化循环

复杂度分析

• 状态数量: $O(n^2 \cdot t)$，其中 $n \leq 20, t \leq 20$
• 每个状态: 需要求解 $O(n^2)$ 规模的线性规划
• 总复杂度: 在可接受范围内（题目提示对耗时要求不高）

算法正确性

博弈论基础

• 这是完全信息零和博弈
• 存在混合策略纳什均衡
• 线性规划能正确求解 minimax 问题

动态规划合理性

• 有向无环图保证状态转移无环
• 逆序计算确保子问题先被解决
• 记忆化避免重复计算

样例分析

样例1

3 2 1 2 10
1 3
2 3

输出：11.000

解释：阿燐在节点1，阿空在节点2。阿燐选择停留，阿空无法到达节点1，游戏持续到强制结束时间11。

样例2

6 8 2 1 2
...

输出：2.333

解释：在双方最优策略下，期望游戏时间为2.333。

总结

本题通过结合动态规划和线性规划，优雅地解决了图上的追逃博弈问题。算法充分利用了：

• 动态规划处理时序结构
• 线性规划求解混合策略均衡
• 记忆化优化重复计算

该解法能够处理题目给定的数据规模，体现了博弈论与优化算法的完美结合。

标签: 动态规划 线性规划 博弈论 追逃问题 纳什均衡