算法设计与分析.08.NP 完全性理论 (4)
NP 完全性理论 (4)
- intractability
求解 NPC 问题
- 实际设计算法
- 只能解决部分实例
- 牺牲最优性
- 可接受非多项式时间
- 策略
- 特殊情形
- 近似算法、启发式算法
- 优化指数级别算法
树
- 树上问题的特例
树上的独立集
- 点数最多
- 观察:如果 v 是叶子节点,则存在一个最大独立集,包含这个节点
贪心算法
- 适用于森林(树的集合)
- 算法:将叶子节点加入独立集,删除叶子节点及其父节点之后,重复上面步骤
- \(O(n)\)
最大权重独立集
- 每一个节点都带权,找到一个权重和最大的独立集(不一定点数最多)
- 树上 DP
- \(OPT_{in}(r)\) :子树 \(r\) 包含根节点的最大权重独立集
- \(OPT_{out}(r)\) :子树 \(r\) 不包含根节点的最大权重独立集
- 原始问题:\(\max\{OPT_{in}(R),OPT_{out}(R)\}\)
- 转移方程
- 实现:树的后序遍历
树的优势
- 能够将原始问题划分为若干不相关的子问题
- 通过某个节点断开
- 普通图不行
平面图
- 同构于某个在平面上没有两条边相交的图
- 没有同构于 \(K_{3,3},K_{5}\) 的子图
- 判断是否为平面图:\(O(n)\)
- Efficient Planarity Testing
- [Hopcroft–Tarjan 1974]
- 简单平面图的性质:\(m\le3n\)
平面图3着色
- 顶点着色
- 平面区域3着色 \(\equiv_{p}\) 平面图3着色
- 平面图3着色 \(\in\) NPC
- 图3着色 \(\le_{p}\) 平面图3着色
- 平面图3着色 \(\in\) NP 是显然的
- 如何对任意实例 \(G\) 构造一个平面图
构造
- gadget
- 对于如上的 gadget,只有上面两种 3 着色方案
- 从中间开始向外着色
- 都保证对角的两个点着色相同(最左最右,最上最下)
- 对于任意的一个交叉进行如下构造
- 如果有多个交叉,则进行连接
平面图k着色
- Every planar map is 4-colorable
- [Appel–Haken 1976]
- \(O(n^4)\)
- First major theorem to be proved using computer.
- 现在的最优算法
- 平面图4着色:\(O(n^2)\)
- 平面图5着色:\(O(n)\)
特殊图
- bounded treewidth
近似算法
点覆盖
- k-近似算法
- 多项式时间
- 能够处理任意输入
- 算法找到的结果是最优解的 \(k\) 比率
- 例如,点覆盖2-近似算法
- 找到的点数 \(\le\) 2x最小点覆盖的点数
贪心算法
- 随机找和当前选中的点不相关联的边,加入这些顶点
- \(O(m+n)\)
- 是 2-近似算法
- \(S'\):最小点覆盖
- 算法:\(\vert{S}\vert=2\vert{M}\vert\le2\vert{S'}\vert\)
- 任意点覆盖 \(S_0\),任意匹配 \(M_0\)
- \(\vert{M_0}\vert\le\vert{S_0}\vert\)
k-近似算法
- 猜想:不存在 \(\rho<2\)
背包问题
- NPC
- 子集和 \(\le_{p}\) 背包问题
- 输入规模:\(n,\log W\)
DP1
- \(OPT(i,w)\):前 i 个物体,重量限制为 w 的最大价值
- 原始问题:\(OPT(n,w)\)
- \(O(nW)\)
- 当 \(w_i\) 很小的时候,可以认为是多项式时间的
DP2
- \(OPT(i,v)\):前 i 个物体,达到价值 v 的最小权重
- 原始问题:最大的 v 满足 \(OPT(n,v)\le W\)
- \(O(n\cdot nv_{max})=O(n^2v_{max})\)
- 当 \(v_i\) 很小的时候,可以认为是多项式时间的
近似算法
- \(\epsilon\in(0,1]\)
- \(v_{max}\)
- \(\theta=\dfrac{\epsilon v_{max}}{2n}\):放缩因子
\[ \bar{v}_i=\lceil\dfrac{v_i}{\theta}\rceil\theta,\hat{v_i}=\lceil\dfrac{v_i}{\theta}\rceil \]
- 使用 \(\bar{v}_i,\hat{v}_i\) 两者是等价的
- 直观
- \(\bar{v}\) 是近似的,结果也是近似最优的
- \(\hat{v}\) 比较小,DP2 算法较快
- 使用 \(\bar{v}\) 是 \((1+\epsilon)\)-近似的
- 价值不是整数如何处理
- \(\theta=\lfloor\dfrac{\epsilon v_{max}}{2n}\rfloor\)(证明的时候倒数第二行换成 \(\le\) )
- 原始问题可行解 \(S^{\ast}\),\(\bar{v}\) 的可行解 \(S\)
- 等价性:\(\hat{v}\) 也满足
- \(O(n^2\hat{v}_{max})=O(n^3/\epsilon)\)
指数算法
3SAT
- \(n\) 个变元,\(m\) 个语句
- 暴力枚举:\(O((m+n)2^n)\)
递归算法
- 分配律
- 复杂度
\[ \begin{array}{c} T(n)\le3T(n-1)+poly(n)\\ \Rightarrow T(n)=O(poly(n)3^{n}) \end{array} \]
- 上面 3 种情况不是互斥的,修改为互斥的情况
- 这样让子问题不重叠,效率更高
\[ \begin{array}{c} T(n)\le3T(n-1)+T(n-2)+T(n-3)+O(m+n)\\ \Rightarrow T(n)=O(1.84^{n}) \end{array} \]
- \(1.84:r^3=r^2+r+1\)
- 最优:\(O(1.33334^{n})\)
- 其他算法
- DPPL:Highly-effective backtracking procedure.
- Chaff:sota
TSP
- traveling salesperson problem:货郎问题
- 完全图中找到权重小于等于 D 的哈密顿回路
- 哈密顿回路 \(\le_{p}\) TSP
- 有边:权重 1
- 无边:权重 2
- DP: TSP can be solved in \(O(n^22^n)\) time.
- [Held–Karp, Bellman 1962]
DP
- \(c(s,v,X)\):从 s 出发,经过 X
中所有的点有且只有一次,到达 v 的最小代价
- \(v\ne s\)
- 原始问题
\[ \min_{v\in V}\{c(s,v,V)+c(v,s)\} \]
- 转移方程
- 子问题个数:\(\le n2^n\)
- 子集个数:\(2^n\)
- 每个子集选择一个终点
Euclidean TSP
- 距离函数使用欧拉函数定义
- 近似算法