贪心算法几个经典例子,贪心算法的关键

注：本学期zjdmy课程内容知识点整理。

贪婪算法不一定正确，需要证明

事件调度问题

算法正确性证明：

贪心算法的基本要素：

选择贪婪性和最佳亚结构性

因贪婪而挑脾气

:矩阵连乘，0-1背包vs评分背包，比较活动安排

算法的第一基本要素主要不同于DP

==自顶向下计算==

OSP:最优策略的子策略也是最优//动规、贪婪

正确性证明一般流程：==

选择贪婪OSP数学归纳法

条件：子问题与原问题相似，但相对独立吗？ 需要别的方法

子问题的最优解和贪婪选择综合整体最优解

一般设计过程：

将问题描述为贪婪选择和待解决子问题形式的贪婪选择性3360证明贪婪选择是正确的最佳子结构性：

使子问题的最优解与贪婪选择相结合，可以得到原问题的最优解。

事件调度问题

选择贪婪：最早结束的活动

子问题： T1={ (开始时间晚于f1的活动}最佳编码问题(Huffman编码) ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) )。

确定解的结构的：二叉树

好的编码：

大频率编码短

小频率符号长

二叉树

相对平衡

贪心选择性质：

最优解存在频率最小的两叶节点的深度最大

最优解存在频率最小的两叶节点是兄弟

最佳编码问题

贪婪选择：频率最低的两个字是兄弟.子问题吗？

原始问题： 6个符号将被编码

子问题： 5个符号将被编码

输入C[1:n]、f[1:n]/字符集c和频率f 1. Q=C //优先队列q，为o(n ) i=1:n-1 //循环n-1次分配3 .新节点z 4。 设q中f的最小x为z的左孩子////o(logn ) 5。 q中f的最小y为z的右孩子/////o ) logn )6.f[z]=f的短路问题

全点对最短路（APSP)DP :

1. D[i，j][0]=w[i，j]，不存在的边的值取无穷大2.k=1:n3.I=1:n，j=1:n 4 .情况D[i，k][k-1] D[k

减少存储？ D[i，k][k]=D[i，k][k-1]？

任何最短路径至多经过k一次

0 .当w [ I，j]无限大时，p[i，j]=i1. D[i，j]=w[i，j]2.对k=1:n 3 .对i=1:n，对j=1:n 4 .对D[i //求解标记原因.==结构解.==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 .各边

不是动态的计划，不是贪婪

设s连接所有点

负电路：侧权和0

正确性证明：

Dijktra(无负权）

1 .初始d[s]=0，其他点d[u]=INF，s空，Q=V 2不为空时取出3.q中d[u]最小的u，加入S 4。 对于u的每个邻居v，松弛[u，v]记u的邻居是n[u]3360VN (

用累计法估计时间的复杂性。

)1) q按普通序列存放。 累计所有步骤5 (每边放宽一次，共计o(|e|)； 累计所有步骤3，一次寻找最小d[u]需要o(|V|)时间，共计|v|次。 合计o(|v|2|e|) ) ) )。

)2) q用最小堆内存。 累计的步骤5 (所有边放松一次。 放松后，从点到最小堆添加，使最小堆的

时间O(log|V|)，合计O(|E|log|V|)；累计所有第3步，执行一次O(log|V|)，共|V|次。总计O((|V|+|E|)log|V|)=O(|E|log|V|).仅当边数没有达到c|V|2，才有必要用最小堆。

Dijkstra贪心算法正确性证明

最小生成树(MST)

无向连通带权图G=(V,E,w).
G的生成树是G的包含所有顶点的一颗子树
若G的生成树T在所有G的生成树中各边权总和最小,
则T称为G的最小生成树(MST, minimum spanning tree)

这里的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. 若 vQ 且 w[u,v] < key[v]6. 则 key[v] = w[u,v], p[v] = u Q一般数组O(|V|^2+|E|) = O(|V|^2)

使用累计法估计时间复杂度。
Q用一般数组存储。累计所有第456步：每条边都会处理一次，合计O(|E|)；累计所有第3步，执行一次O(|V|)，共|V|次。总计O(|V|2+ |E|)
用优先队列：

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

这是一般人能看懂的？？？
反正我看不懂
[怕孤独的月亮n个节点, m次操作, O((n+m)log*n)

多机调度问题

最优化课上学了随机化算法解决，但不一定得到最优解。