SDSC6007 课程 2-确定性系统与最短路问题

确定性系统与最短路问题

#sdsc6007

English / 中文

简介

最短路径问题 (Shortest Path Problems)

问题定义

给定节点集合 $\{1,2,\dots,N,t\}$（$t$ 为目标节点），

• $a_{ij}$：从节点 $i$ 到 $j$ 的路径成本（$a_{ij} = \infty$ 表示无直接路径）

• 关键假设：所有环路成本非负（$\forall \text{循环路径 } i \to j_1 \to \cdots \to j_k \to i,\ \text{总成本} \geq 0$）

• 目标：寻找从任意节点 $i$ 到 $t$ 的最小成本路径

非负环路假设的重要性

核心意义：确保最优解存在且路径长度有限

1. 避免无限负成本：

   $$\text{若存在负成本循环 } \sum_{\text{cycle}} a_{ij} < 0 \Rightarrow \text{总成本可无限降低}$$

   例：反复经过负成本环路使总成本趋于 $-\infty$

2. 自环约束：

   $$a_{ii} \geq 0 \quad (\text{若允许节点停留})$$

3. 路径长度界限：

   $$\text{最优路径最多包含 } N \text{ 次移动}$$

   • 可通过设置 $a_{ii} = 0$ 强制路径恰好有 $N$ 次移动（允许停留）

动态规划建模

定义值函数：

$$J_k(i) = \text{从 } i \text{ 出发经 } k \text{ 步到 } t \text{ 的最小成本}$$

递推方程：

$$J_k(i) = \min_{j} \left[ a_{ij} + J_{k-1}(j) \right]$$

边界条件：

$$J_0(t) = 0, \quad J_0(i) = \infty \ (i \neq t)$$

​​非负环路假设的实际意义​​：

该假设保证了最短路径问题具有良好定义的最优解。若存在负成本环路，则算法可能陷入无限循环，无法收敛。

在路由选择、网络优化等实际应用中，该条件通常通过成本函数设计自然满足（如距离、时延等物理量非负）。

确定性动态规划问题

确定性系统特性

核心特征：无随机扰动 ($w_k$ 不存在或为已知常量)

1. 状态转移完全可预测：

   $$x_{k+1} = f_k(x_k, u_k)$$

   • 给定初始状态 $x_0$ 和策略 $\{\mu_0,\dots,\mu_{N-1}\}$，可精确计算状态轨迹

2. 闭环控制无优势：

   $$J^{\text{closed-loop}} = J^{\text{open-loop}}$$

   • 最优开环控制序列 $(u_0^*,u_1^*,\dots,u_{N-1}^*)$ 与闭环策略 $\mu_k^*(x_k)$ 成本相同

为什么闭环控制无优势：

在确定性系统中，未来状态完全由当前决策决定。一旦选定决策序列，状态轨迹即确定。实时状态反馈不提供新信息，因此闭环策略无法改进开环策略的成本。

有限状态系统建模

状态转移图表示：

• 节点：状态 $x_k \in \mathcal{S}_k$（有限集合）

• 有向边：控制决策 $u_k$ 驱动的状态转移

  $$x_k \xrightarrow{u_k} x_{k+1} = f_k(x_k, u_k)$$

• 边成本：阶段成本 $g_k(x_k, u_k)$

关键简化：对每个状态转移 $x_k \to x_{k+1}$，仅需保留最小成本决策：

$$c_k(x_k, x_{k+1}) = \min_{\substack{u_k \in U_k(x_k) \\ f_k(x_k,u_k)=x_{k+1}}} g_k(x_k, u_k)$$

动态规划方程

值函数递推：

$$J_k(x_k) = \min_{x_{k+1}} \left[ c_k(x_k, x_{k+1}) + J_{k+1}(x_{k+1}) \right]$$

边界条件：

$$J_N(x_N) = g_N(x_N)$$

计算意义：将原问题转化为多阶段图的最短路径问题

有限状态系统的本质：

通过状态转移图建模后，问题退化为寻找从初始状态到终端状态的最小成本路径。动态规划在此场景下本质是逆向搜索图的最优路径。

确定性有限状态系统与最短路径问题的等价关系

确定性系统 → 最短路径问题 (SPP)

转换方法：

1. 定义节点：

   • $s$：初始状态节点（对应 $x_0$）
   • $t$：终端节点（人工添加）

2. 边成本定义：

   • 阶段 $k$ 转移成本：$a_{ij}^k = \min_{u_k} g_k(i, u_k)$（当 $f_k(i,u_k)=j$）
     • $i$：当前状态
     • $j$：下一状态
     • $u_k$：控制决策
     • $g_k$：阶段成本函数
   • 终端成本：$a_{it}^N = g_N(i)$
     • $g_N$：终端成本函数

3. 路径成本：

   $$\text{总成本} = \sum_{k=0}^{N-1} a_{x_k x_{k+1}}^k + a_{x_N t}^N$$

核心等价：原问题最优成本 $= J_0(s) =$ 从 $s$ 到 $t$ 的最短路径长度

逆向动态规划算法

值函数定义：

$$J_k(i) = \text{从状态 } i \text{ 在阶段 } k \text{ 到终端 } t \text{ 的最小成本}$$

• $k$：当前阶段

• $i$：当前状态

递推方程：

$$\begin{aligned} J_N(i) &= a_{it}^N \quad \forall i \in S_N \\ & \quad \text{（终端成本：状态 } i \text{ 到 } t \text{ 的直接成本）} \\ J_k(i) &= \min_{j \in S_{k+1}} \left[ a_{ij}^k + J_{k+1}(j) \right] \quad k = N-1,\dots,0 \\ & \quad \text{（最小化：转移成本 } a_{ij}^k \text{ + 后续最优成本 } J_{k+1}(j) \text{）} \end{aligned}$$

最优解：$J_0(s)$ 为最短路径长度（初始状态 $s$ 到终端 $t$ 的最小成本）

最短路径问题 → 确定性系统

转换方法：

1. 固定阶段数 $N$（由非负环路假设保证）

2. 定义值函数：

   $$J_k(i) = \text{从 } i \text{ 经 } N-k \text{ 步到 } t \text{ 的最小成本}$$

   • $N-k$：剩余步数

3. 递推关系：

   $$\begin{aligned} J_{N-1}(i) &= a_{it} \\ & \quad \text{（一步转移成本）} \\ J_k(i) &= \min_{j=1,\dots,N} \left[ a_{ij} + J_{k+1}(j) \right] \quad k=0,\dots,N-2 \\ & \quad \text{（最小化：当前转移成本 } a_{ij} \text{ + 后续最优成本 } J_{k+1}(j) \text{）} \end{aligned}$$

关键点：$J_0(i)$ 给出从 $i$ 到 $t$ 的最短路径成本

前向动态规划算法（特殊性质）

仅适用于确定性SPP问题：

• 值函数定义：

  $$\tilde{J}_k(j) = \text{从 } s \text{ 到 } j \text{（阶段 } k \text{）的最小成本}$$

  • $k$：当前阶段
  • $j$：当前状态

• 递推方程：

  $$\begin{aligned} \tilde{J}_1(j) &= a_{sj}^0 \quad \forall j \in S_1 \\ & \quad \text{（初始状态 } s \text{ 到阶段1状态 } j \text{ 的成本）} \\ \tilde{J}_k(j) &= \min_{i \in S_{k-1}} \left[ a_{ij}^{N-k+1} + \tilde{J}_{k-1}(i) \right] \quad k=2,\dots,N \\ & \quad \text{（最小化：转移成本 } a_{ij}^{N-k+1} \text{ + 前序最优成本 } \tilde{J}_{k-1}(i) \text{）} \\ \tilde{J}_0(t) &= \min_{i \in S_N} \left[ a_{it}^N + \tilde{J}_N(i) \right] \\ & \quad \text{（终端成本：状态 } i \text{ 到 } t \text{ + 到达 } i \text{ 的最优成本）} \end{aligned}$$

对比说明：
逆向DP计算"剩余成本"（cost-to-go），前向DP计算"到达成本"（cost-to-arrive）。
因路径对称性，两者在确定性SPP中等价，但前向方法不适用于随机问题。

最短路径应用：关键路径分析

问题描述

应用场景：项目管理中活动调度优化

核心目标：

1. 确定项目最短完成时间

2. 识别关键活动（延迟会导致项目整体延迟的活动）

案例研究：杨博士的日程优化

活动分解：

活动	描述
与助教会面	必须完成
回复邮件
午餐
与博士生会面
硕士项目工作
教学

阶段划分：

• 节点表示日程阶段（$N=5$）

• 边 $(i,j)$ 表示活动，权重 $t_{ij}>0$ 为持续时间

• 节点1：日程开始（无入边）

• 节点5：日程结束（无出边）

关键路径算法

变量	符号表示	定义说明
路径持续时间	$D_p$	路径 $p$ 的总持续时间 计算：$D_p = \sum_{(i,j)\in p} t_{ij}$
最早完成时间	$T_i$	节点 $i$ 的最早完成时间 计算：$T_i = \max_{\text{所有路径 } p \text{ 从 1 到 } i} D_p$
活动持续时间	$t_{ji}$	活动 $(j,i)$ 的持续时间 （从节点 $j$ 到 $i$ 的边权重）
前驱节点集合	$\text{Pred}(i)$	节点 $i$ 的直接前驱节点集合 （有边直接指向 $i$ 的节点）
关键活动判定	$T_i = T_j + t_{ji}$	活动 $(j,i)$ 为关键活动的充要条件 （满足此等式时活动无时差）
时差（松弛时间）	$\text{Slack}_{ji}$	非关键活动的可延迟时间 计算：$\text{Slack}_{ji} = T_i - (T_j + t_{ji})$

路径持续时间计算：

$$D_p = \sum_{(i,j)\in p} t_{ij} \quad \text{（路径 } p \text{ 的总持续时间）}$$

阶段最早完成时间：

$$T_i = \max_{\text{所有从1到}i\text{的路径}p} D_p \quad \text{（节点 } i \text{ 的最早完成时间）}$$

关键路径定义：

$$\text{关键路径} = \arg\max_{p} D_p \quad \text{（从节点1到节点5的最长路径）}$$

动态规划求解

值函数定义：

$$T_i = \text{节点 } i \text{ 的最早完成时间}$$

递推方程：

$$T_i = \max_{j \in \text{Pred}(i)} \left( T_j + t_{ji} \right)$$

其中 $\text{Pred}(i)$ 是节点 $i$ 的直接前驱集合

边界条件：

$$T_1 = 0$$

关键活动识别：活动 $(j,i)$ 是关键活动当且仅当：

$$T_i = T_j + t_{ji}$$

算法特性

1. 无环图保证：

   • 项目网络无循环 → 有限路径数
   • 确保 $\max$ 运算有定义

2. 关键活动特性：

   • 关键路径上的活动均为关键活动
   • 非关键活动有时差（slack time）：

     $$\text{时差} = T_i - (T_j + t_{ji})$$

管理启示：
优化关键活动可缩短总工期，非关键活动可灵活调度资源

---