注：本学期刘老师上课内容知识点整理。
贪心算法
贪心不一定正确，需要证明
活动安排问题
算法正确性证明：
贪心算法的基本要素：
贪心选择性质和最优子结构性质
贪心选择性质
对比: 矩阵连乘, 0-1背包 vs 分数背包,活动安排
贪心算法第一基本要素, 与DP主要区别
==自顶向下计算 ==
OSP: 最优策略的子策略也是最优 //动规, 贪心
== 正确性证明一般过程: ==
贪心选择+OSP+数学归纳法
条件: 子问题与原问题类似, 相对独立 //不类似? 则需要另外方法
子问题的最优解和贪心选择联合得整体最优解
一般设计过程：
- 将问题描述为贪心选择和一个待解决子问题的形式
- 贪心选择性质: 证明贪心选择是正确的
- 最优子结构性质:
确保若将子问题的最优解和贪心选择结合, 则能得到原问题的最优解.
活动安排问题
贪心选择: 最早结束的活动
子问题: T1 = { 开始时间晚于f1的活动 }
最优编码问题（Huffman编码）
确定解的结构: 二叉树
好的编码：
大频率编码短
小频率编码长
正则二叉树
相对平衡
贪心选择性质：
存在最优解其频率最小两叶节点深度最大
存在最优解其频率最小两叶节点是兄弟
输入C[1:n], f[1:n] //字母集C和频率f 1. Q=C //建优先队列Q, O(n) 2. 对 i = 1:n-1 //循环n-1次 3. 分配新节点z 4. 取Q中f最小x作为z的左孩子//O(log n) 5. 取Q中f最小y作为z的右孩子//O(log n) 6. f[z] = f[x] + f[y] 7. 将z插入Q中 //O(log n) 8. 取出Q中节点作为树根 //? 最短路问题
- 全点对最短路（APSP)
DP：
1. D[i,j][0] = w[i,j], 不存在的边值取无穷大 2. 对k=1:n 3. 对i=1:n, 对j=1:n 4. 若D[i,k][k-1]+D[k,j][k-1] < D[i,j][k-1] 5. 则 D[i,j][k] =D[i,k][k-1]+D[k,j][k-1]; 6. 否则 D[i,j][k] = D[i,j][k-1] Floyd-Warshall算法
减少存储? D[i,k][k]=D[i,k][k-1]?
任何最短路径至多经过k一次
0. 若w[i,j]<无穷大, 则p[i,j]=i 1. D[i,j] = w[i,j] 2. 对k=1:n 3. 对i=1:n, 对j=1:n 4. 若 D[i,k]+D[k,j] < D[i,j] 5. 则 D[i,j] = D[i,k]+D[k,j]; 6. p[i,j] = p[k,j]; //解标记 原因.== 构造解.== O(n3).
p[i,j]: 在i到j的最短路上j的前驱
- 单源最短路
函数d和松弛操作
Bellman-Ford(含负权[C])
初始d[s]=0, 其它点d[u]=INF, 1. 对i =1: |V|-1 //松弛|V|-1遍 2. 对每条边(u,v), 松弛(u,v) 3. 对每条边(u,v), //检查负回路 4. 若d[v]>d[u]+w(u,v), 返回假 5. 返回真 1. 初始d[s]=0, 其它点d[u]=INF, S空, Q=V 2. 当Q非空 3. 取出Q中d[u]最小的u, 加入S 4. 对u的每个邻居v, 松弛(u,v) 记u的邻居为N(u): vN(u) 
Dijkstra贪心算法正确性证明
最小生成树(MST)
这里的MST性质证明不太懂（贪心选择+归纳）
昨天看不懂 今天看懂了。。。就是假设一个MST不含（u,v)但若如此它不是MST
MST算法正确性证明
Prim算法：
用一般数组
key[u]记u到U的最小距离, p[u]记u与U最小距离对应点 1. 初始p[u]=NIL, key[r]=0, 其它key[u]=INF, Q=V, U空 2. 当Q非空 3. 取出Q中u使得key[u]最小, 加入U 4. 对u的每个邻居v, 5. 若 vQ 且 w[u,v] < key[v] 6. 则 key[v] = w[u,v], p[v] = u Q一般数组O(|V|^2+|E|) = O(|V|^2) key[u]记u到U的最小距离, p[u]记u与U最小距离对应点 1. 初始p[u]=NIL, key[r]=0, 其它key[u]=INF, Q={
r}, U空 2. 当优先队列(最小堆)Q非空 3. 删除Q堆顶元素u. 若u在U中,则continue; 否则加入U. 4. 对u的每个邻居v, 5. 若 w[u,v] < key[v] 6. 则 将v按键值key[v]=w[u,v]插入Q, p[v] = u Q优先队列O(|E|log|V|+|E|log|E|) = O(|E|log|V|) Q用最小堆存储。累计所有第456步：每条边都会处理一次，处理后添加一个点到最小堆中，维护一次最小堆的时间O(log|V|)，合计O(|E|log|V|)；累计所有第3步，执行一次O(log|V|)，共|V|次。总计O((|V|+|E|)log|V|)=O(|E|log|V|).仅当边数没有达到c|V|2，才有必要用最小堆。
Kruskal算法
1. A为空, Q=E按边权升序排列 2. 当Q非空 3. 顺序取Q中边(u,v) 4. 若u,v在A的不同连通分支(检查), 5. 则添(u,v)到A, (且合并u,v所在连通分支) 6. 输出A 并查集算法处理连通分支, O(|E|log|E|+|E|log*|V|) 1. A为空, Q=E按边权升序排列, x Make(x) 2. 当Q非空 3. 顺序取Q中边(u,v) 4. 若Find(u)Find(v), 则添(u,v)到A, Union(u,v), 5. 输出A 多机调度问题
最优化课上学了随机化算法解决，但不一定得到最优解。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/209252.html原文链接：https://javaforall.net
