目录
- 1.贪心算法步骤
- 2.两个关键要素
- 3.两种背包问题
3.1 0-1背包问题（适用于动态规划，不满足贪心选择性质）
3.2 分数背包问题（适用于贪心算法） - 4.实例
4.1 活动选择问题
4.2 霍夫曼编码
4.3 最小生成树算法
参见最小生成树
4.4 最短路径Dijkstra算法
参见最短路径专题
4.5 最小生成树与最短路径问题的比较
1.贪心算法步骤
step1.将最优化问题转换为这样的形式：对其最初一次选择后，只剩下一个子问题需要求解
step2.证明做出贪心选择后，原问题总是存在最优解，即贪心选择总是安全的
step3.证明做出贪心选择后，剩余的子问题满足性质：其最优解与贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构。
2.两个关键要素
1）贪心选择性质
可以通过做出局部最优（贪心）选择来构造全局最优解。
动态规划方法中，每个步骤都要进行一次选择，但选择通常依赖于子问题的解。一般以一种自底向上的方式求解动态规划问题。
贪心算法中，在进行第一次选择之前不求解任何子问题，只是做出当时看来最佳的选择。贪心算法通常是自顶向下的，进行一次又一次选择，将给定问题实例变得更小。
证明每个步骤做出贪心选择能生成全局最优解。这种证明通常首先考察某个子问题的最优解，然后用贪心选择来修改此解，从而得到一个相似的最优解。
2）最优子结构
一个问题的最优解包含其子问题的最优解。
全部证明：将子问题的最优解与贪心选择组合在一起就能生成原问题的最优解。（数学归纳法）
一个问题：贪心选择性质和最优子结构的区别?
贪心算法问题的最优解包括两部分：贪心选择 + 子问题的最优解
a.贪心选择性质针对的是贪心选择部分
b.最优子结构针对的是子问题的最优解
这两个合起来，就构成了贪心问题的最优解，缺一不可
3.两种背包问题
3.1 0-1背包问题（适用于动态规划，不满足贪心选择性质）
3.2 分数背包问题（适用于贪心算法）
4.实例
4.1 活动选择问题
1）最优子结构
Sij表示在ai结束后开始，在aj开始前结束的那些活动的集合；
Aij是Sij的一个最大相互兼容的活动子集
ak属于Aij
求解Aij分解为两个子问题：寻找Sik中的兼容活动，以及寻找Skj中的兼容活动：
证明：
使用c[i,j]表示集合Sij的最优解大小，可得：
2）贪心选择性质（如下定理是基于fi排列顺序而言的）
贪心选择：选择最先结束的活动（或者选择最晚开始的活动）
特别注意：这里构造出来的也是一个最大兼容活动子集，并非是唯一一个！
3）贪心算法
4.2 霍夫曼编码
编码问题：根据字符出现的频率，构造出字符的最优二进制表示，使得压缩率最优。
变长编码：赋予高频字符短字码，赋予低频字符长字码
前缀码：既没有任何字码是其他字码的前缀。前缀码可以简化解码过程。
文件的最优编码方案总是对应一颗满二叉树。若C为字母表且所有字符的出现频率均为正数，则最优前缀码对应树恰有|C|个叶节点，每个叶节点对应字母表中一个字符，且恰有|C| - 1个内部节点。
证明：
对于一颗满二叉树而言：
1）最简单情况：一个根节点+两个叶子，满足情况
2）一颗满二叉树可以由最简单情况重复衍生而来：将一个叶子替换为一个子树（一个根，两个叶子）
此时叶子增加1（增加两个，减少一个），内部节点增加1（叶子节点转变而来的）
因此，有|C|-1个内部节点，|C|个叶子节点
1）算法代码
2）贪心选择性质（图是象征性的，不是一定的）
关键在于：用贪心选择去修改最优编码树，得到的还是一颗最优编码树
3）最优子结构（反证法，一般用cut-paste方法）
4.3 最小生成树算法
4.3.1 最小生成树问题
4.3.2 贪心选择性质
贪心策略：
该算法的理解：
a.集合A总保持无环状态，因为是一棵树；因此对于集合A为安全的边(u, v)所连接的是GA中不同的连通分量；因此，每执行一次循环，减少一棵树
b.算法执行的任意时刻，图GA = (V, A)是一个森林，GA中的每个连通分量是一棵树
算法开始时，集合A为空，森林中包含|V|棵树，每棵树只有一个节点；
c.由a, b可知，while循环总共执行|V| - 1次，当整个森林仅包含一棵树时，终止
循环不变式：
在每次循环之前，A是某棵最小生成树的一个子集。
安全边：满足如下条件的边称之为安全边。
将边(u, v)加入到集合A中，使得A不违反循环不变式，即AU{(u, v)}也是某棵最小生成树的子集。
切割：无向图G=(V, E)的一个切割(S, V-S)是集合V的一个划分
横跨：边(u, v)横跨切割(S, V-S)表示一个端点在集合S，一个在V-S
尊重：如果集合A中不存在横跨该切割的边，则称该切割尊重集合A
轻量级边：在横跨一个切割的所有边中，权重最小的边称为轻量级边
贪心策略中辨认安全边的规则：
一个推论：
一个问题：为什么该切割尊重集合A
根据定义：因为集合A中不存在横跨该切割的边
该切割区分了C，将集合A分为两部分，C和A-C，但是C和A-C并不连通。
所以不存在横跨该切割的一条轻量级边。
4.3.3 最优子结构
如果一个问题的最优解中包含了子问题的最优解，则该问题具有最优子结构。
最小生成树是满足最优子结构的，下面会给出证明：
最优子结构描述：假设我们已经得到了一个图的最小生成树(MST) T，(u, v)是这棵树中的任意一条边。如图所示：
现在我们把这条边移除，就得到了两棵子树T1和T2，
如图：
T1是图G1=(V1, E1)的最小生成树，G1是由T1的顶点导出的图G的子图，E1={(x, y)∈E, x, y ∈V1}
同理可得T2是图G2=(V2, E2)的最小生成树，G2是由T2的顶点导出的图G的子图，E2={(x, y)∈E, x, y ∈V2}
现在我们来证明上述结论：使用剪贴法。w(T)表示T树的权值和。
首先权值关系满足：w(T) = w(u, v)+w(T1)+w(T2)
假设存在一棵树T1'比T1更适合图G1，那么就存在T'={(u,v)}UT1'UT2'，那么T'就会比T更适合图G，这与T是最优解相矛盾。得证。
- 特别注意，上图中(u, v)这条边是连接两棵树的最小边（安全边）
4.3.4 Kruskal算法
4.3.5 Prim算法
该算法的一个简要分析：
初始化：r.key = 0，其余节点u.key = 无穷大
第一次循环：将r从Q中剔除，并更新r的所有邻节点的key
以此类推
4.4 最短路径Dijkstra算法
4.4.1 最短路径问题
4.4.2 最优子结构
4.4.3 Dijkstra算法的适用条件以及贪心选择性质
前提条件：Dijkstra算法解决的是带权重的有向图上单源最短路径问题，该算法要求所有边的权重都为非负值。
算法说明1.松弛操作
1）最短路径的表示（v.Π）
对每个结点，维持一个前驱结点v.Π。该前驱结点可能是另一个结点或者NIL。
设G=(V, E)是一个带权重的有向图，其权重函数为w，假定G不包含从s可以到达的权重为负值的环路，因此，所有的最短路径都有定义。一棵根节点为s的最短路径树是一个有向子图G' = (V', E')
2）松弛操作（v.d）
对于每个结点v，维持一个属性v.d，用来记录从源节点s到结点v的最短路径权重的上界。
松弛操作是唯一导致最短路径估计和前驱结点发生变化的操作。
Dijkstra算法对每条边仅松弛一次。
3）最短路径和松弛操作的一些性质
1.三角不等式
证明：最短路径性质，最短路径是最短的，那必须成立
2.上界性质
证明：归纳法
基础步：显然成立
归纳步：根据归纳假设，松弛前，成立；松弛后，唯一可能发生改变只有v.d
v.d = u.d + w(u, v) >= δ(s, u) + w(u, v) >= δ(s, v)
因为是下界，所以取到下界肯定不会变化
3.收敛性质
1）根据上界性质，松弛前有u.d = δ(s, u)，松弛后仍成立
2）对(u, v)松弛后
v.d <= u.d + w(u, v)
= δ(s, u) + w(u, v)
= δ(s, v) (根据最优子结构，前提是s->u->v是一条最短路径)
根据上界性质，v.d >= δ(s, v)，因此有v.d = δ(s, v)
其中为什么进行松弛后v.d <= u.d + w(u, v)?
因为：
a. 如果v.d <= u.d + w(u, v)，松弛操作不会改变u.d和v.d的值
b. 如果v.d > u.d + w(u, v)，松弛操作后，v.d = u.d + w(u, v)
4.路径松弛性质
使用归纳法，根据收敛性质可以证明
5.前驱子图性质，需要证明三条性质都满足
1）VΠ是从源节点s可以到达的结点的集合
因为VΠ中的点δ(s, v)都是有限值，因此都可以到达
2）GΠ形成一棵根节点为s的树
a. 首先证明GΠ是无环路的
b. 证明对于属于VΠ的每个结点v，在图GΠ中存在一条从源点s到结点v的唯一简单路径
3）对于所有属于VΠ的结点v，图GΠ中从结点s到结点v的唯一简单路径是图G中从结点s到结点v的一条最短路径。
5-2 GΠ形成一棵根节点为s的树
5-3 对于所有属于VΠ的结点v，图GΠ中从结点s到结点v的唯一简单路径是图G中从结点s到结点v的一条最短路径。
首先搞清楚前驱子图的定义：
证明如下：
算法导论证明是不是有误？
1）对于最优子结构，可以用cut-paste来证明：如果不是G中的最短路径，那么还有一条更短的路径，与v.d = δ(s, d)矛盾
2）对算法道路中的证明稍微修改，将>=号改为=，是否可行？
因为每次松弛后有δ(s, v) = δ(s, u) + w(u, v)；
这里有一个特别说明：对于一条简单路径上的结点，因为只有松弛操作才可以改变前驱结点和v.d，所以在GΠ中的边，都有>=；否则不会有松弛操作，因此这里的>=是满足的。
算法说明2.算法的操作
Dijkstra算法在运行过程中维持的关键信息是一组结点集合S。从源节点s到该集合中每个结点之间的最短路径已经被找到。算法重复从结点集V-S中选择最短路径估计最小的结点u，将u加入到集合S，然后对所有从u出发的边进行松弛。
使用一个最小优先队列Q来保存结点集合，每个结点的关键值是其d值。
算法说明3.贪心选择性质的证明
特别说明：
第一次看的时候有一个地方不懂：在将u加入到集合S时，y.d = δ(s, y)
这个是根据收敛性质来的
-
Dijkstra算法的贪心选择性质：
1）加入集合S的，都有u.d = δ(s, u)；此时与S中点相邻的点v都已经被松弛过了。并且s到最小的v必然存在一条最短路径，并且已经被松弛过了，因此v.d=δ(s, v)肯定成立。
2）为什么s到最小的v存在一条最短路径，而且必然是s~u-v，因为所有的路径是非负的，并且v还未加入到S中，所以任何经过其他路径再到v的路径都要比这条路径长。
4.5 最小生成树与最短路径问题的比较
4.5.1 问题定义的区别
1）最小生成树（带权重无向图）
2）最短路径（带权重有向图；Dijkstra解决的是单源最短路径问题）
4.5.2 Prim和Dijkstra算法
目的不一样：
Prim求的是整个生成树的连接最小，所以一直找最小的边加入
Dijkstra求的是从源点到其他所有点的最短距离，所以要不断relax更新（减小）源点到各个点的距离
1）最小生成树的Prim算法
2）单源最短路径的Dijkstra算法
