动态规划(3)：图中DP

本文为SJTU-AI2615算法课程的知识点复习，主要复习内容为图中的动态规划，包括所有点对最短路径、旅行商问题、树上的最大独立集等问题。

所有点对最短路径问题

问题描述

• ​输入：带权有向图 $G(V,E)$，边权函数 $d(u,v)$
• ​输出：所有顶点对之间的最短路径距离 $dist(u,v)$

Bellman-Ford 算法回顾

• ​子问题定义：$dist[k,v]$ 表示从起点 $s$ 到 $v$ 最多经过 $k$ 条边的最短距离
• 状态转移：

$$dist[k,v] = \min_{(u, v) \in E}\{dist[k-1,v], dist[k-1, u] + d(u,v)\}$$

• 时间复杂度：$O(|V|^2|E|)$

Floyd-Warshall 算法

• 子问题定义：$dist[k,u,v]$ 表示允许使用前 $k$ 个顶点作为中间点时，$u$ 到 $v$ 的最短距离
• 状态转移：

$$dist[k,u,v] = \min\{ dist[k-1, u, v], dist[k-1, u, k] + dist[k-1, k, v]\}$$

• 时间复杂度：$O(|V|^3)$

旅行商问题（TSP）

问题描述

• ​输入：完全加权无向图 $G$，顶点间距离 $d(u,v)>0$
• ​输出：访问所有顶点恰好一次的最小权重回路

动态规划解法

• 子问题定义：$f[S, u, v]$ 表示恰好使用 $S \subset V$ 作为中间点时，$u$ 到 $v$ 的最短距离（或固定起点 $u$，状态表示为 $f[S, v]$）
• 状态转移：

$$f[S, u, v] = \min_{k \in S} f[S - \{k\}, u, k] + d(k, v)$$

• 时间复杂度：$O(n^22^n)$

树上的最大独立集

问题描述

• 输入：无向树 $T=(V,E)$
• 输出：顶点集合 $S \subseteq V$，满足任意两顶点不相邻，且 $|S|$ 最大

动态规划解法

• ​子问题定义：$f[u]$ 表示以 $u$ 为根的子树的最大独立集大小
• 状态转移：

$$f[v] = \max \left\{ \sum_{u \in children(v)} f[u], 1 + \sum_{u \in grandchildren(v)} f[u] \right\}$$

• 时间复杂度：$O(n)$

贪心解法

• 算法步骤：
  1. 选择所有叶子节点
  2. 删除这些叶子的父节点
  3. 重复步骤1
• 时间复杂度：$O(n)$

树分解与树宽

基本概念

• ​树分解：将图 $G$ 分解为树结构，每个树节点对应一个顶点集合（bag）
• ​树宽：最大bag的大小减1
• ​分离性质：任意两个子树通过共享bag分离

注：本文中所有图片均来自张宇昊老师的课程PPT。