分治
基本概念
- 基本思想
- 将原始问题分解为若干子问题
- 逐个解决各个子问题
- 得到原始问题的解
- 情况分类
- 原始问题的解在分解出的子问题中
- 原始问题的解需要各个子问题的解再经过综合处理得到
- 如果分解出的子问题和原始问题类型相同，就可以用递归的方法做了
算法示例
- 查找最大值最小值 O(logn)
- 二分搜索 O(logn)
- 合并排序 O(nlogn)
减治
- 思想：利用一个问题给定实例的解和同样问题较小实例的解之间的关系
- 具体做法
- 减去一个常量
- 减去一个常数因子：an=(an/2)2
- 减去规模可变：欧几里德算法
变治
- 类型
- 实例化简
- 改变表现
- 问题归约
动态规划
- 解决多阶段决策过程最优化的一种方法
- 过程划分为若干互相联系的阶段
- 每一个阶段都要作出决策，而且会影响下一个阶段的决策
- 从终点逐段向始点方向寻找最短路线，如果倒过来也一样就叫可逆
- 基本概念
- 阶段：把问题的过程划分为若干相互联系的阶段
- 状态：某段出发的位置，包含若干个状态
- 用xk表示第k段的某一状态
- 决策：某阶段状态给定以后，从该状态演变到下一阶段的选择
- 用uk(xk)表示第k段当状态处于xk时的决策变量
- 用Dk(xk)表示第k段当状态处于xk时的允许决策集合
- 指标函数
- 最优指标函数fk(xk)
- 构成动态规划模型的条件
- 状态变量无后效性
- 确定决策变量和允许决策集合
- 写出状态转移方程xk+1=Tk(xk,uk)
- 列出指标函数关系并满足递推性
回溯
- 用深度优先算法搜索状态空间树，满足一定条件的情况下搜索回溯
- 有组织的穷尽搜索
分支定界
- 主要思想
- 对状态空间树每一个节点代表的部分解，计算部分解之后的解在目标函数上的最佳值边界
- 求出目前最佳解的值
- 用某个阶段的边界值和目前的最佳解值比较
贪心算法
- 可行、局部最优、不可取消
理论基础：拟阵
- 一个拟阵是一个满足如下条件的有序对M=(S, I)
- S是非空有限集
- I是S的子集的一个非空族，这些子集称为S的独立子集，即I满足遗传性质：若B∈I，且A⊆B，则A∈I
- I满足交换性质：若A∈I，B∈I且|A|<|B|，则存在某个元素x∈B-A，使得A∪{x}∈I
- 若x不属于A，A∪{x}∈I，则称x是A的一个扩展；如果A不存在扩展，则A是最大独立子集，或拟阵的基
- 一个拟阵的所有最大独立子集具有相同大小
- 如果给拟阵关联一个加权函数w，使得对于任意x∈S，有w(x)>0，则称拟阵为加权拟阵
- 贪心算法求解的问题可以表示为加权拟阵的最大权独立子集问题
NP完全
- NP完全问题还未解决
- 只要一个NP完全问题有高效算法，所有的NP完全问题都有高效算法
- 证明一个问题没有高效算法：证明该问题的NP难问题
预备知识：判定问题、最优化问题
判定问题
- 只有两种答案：“是”（1）或“否”（0）
- 判定问题Q对应一个从Q的实例集I到{0,1}的一个函数fQ
- 也就是，给函数输入一个东西，函数回答0和1代表否和是
- 判定问题Q的实例集I=YI∪NI
最优化问题
- 每个可行解都有一个相关值，最优化问题的目标就是找到具有最佳值的可行解
- 一个最优化问题通常有对应的判断问题
- 判定问题不会比对应的最优化问题更难
预备知识：编码方案
-
设∑是非空字母集合，编码方案e: I→∑*是一个函数，将一个实例x∈I映射到一个∑上的字符串e(x)
- 也就是把一个输入用有限的字母表示出来
- 二进制编码的字母表是
-
二进制编码方案：字母表是{0,1}的编码方案
- 实例x的规模为x的二进制编码e(x)的长度，记为|x|
P问题：多项式时间可解的问题
- 多项式时间可解：设问题的具体实例x的输入规模|x|=n
- 如果存在一个算法能在O(nk)（k为常数）时间内解决问题，那么该问题是多项式时间可解
- 采用合理编码方案时，输入规模是多项式相关的
- 如果存在两个多项式时间可计算的函数f和f'，可以让f(e1(x))=e2(x)，f'(e2(x))=e1(x)，那么两种编码是多项式相关的
- P问题：多项式时间可解的问题
- 设Q是抽象问题，I是Q的实例集，e1和e2是两个多项式相关的编码方案，那么e1∈P当且仅当e2∈P
NP问题：多项式时间可判定的问题
- 证书：判断具有某个条件的事物是否存在
- 验证算法A：以输入串x和证书y作为输入，如果存在一个证书y满足A(x,y)=1，则算法A验证了输入串x
- NP问题：一个判定问题Q是判定问题，记作Q∈NP
- 当且仅当存在一个两输入的多项式时间验证算法A和常数c使得：
- 对任意实例x∈YI，存在一个证书y且|y|=O(|x|c)，满足A(x,y)=1
- 称算法A在多项式时间内验证了判定问题Q
- P⊆NP
- 多项式可解的判定问题一定是多项式可验证的
- NP问题例子
- 生成树判定问题（DMST）
- 布尔公式的可满足性问题（SAT）
- 3-CNF的可满足性问题（3SAT）
- 0-1背包问题（0-1 Knapsack）
近似算法
优化问题
- 四元组：实例集合、可行解集合、评估函数（计算可行解的值）、优化目标（最大还是最小）
- 对应的判定问题
- NPO问题：实例集多项式时间内可识别，多项式时间可判断可行解，多项式时间可计算评估函数
- PO问题：Q是NPO问题，如果存在多项式时间算法能求出最优解，那么Q是PO问题
- 如果NPO问题Q的判定问题是NP难问题，则Q是NP难优化问题
近似算法
- 相对误差：可行解和最优解之间相差的百分比（0到1之间）
- 精度/性能比：可行解和最优解之间的比值（大于1），等于1的时候是最优解
- r-近似算法