《算法设计》学习笔记-贪心算法
贪心算法可以说是最容易被人想到的算法之一，它非常符合人类在面对复杂问题时的思维方式。它大概可以描述成：如果一个算法以小步骤来构建解，在每个步骤中目光短浅地选择一个决策来优化某些基础判据，那它就是贪心的。是不是能够联想到市场经济能够形成看不见的手？自然界才是真正的算法大师，或者说，自然界是高等生物用算法设计的？如果一个问题能够被贪心算法成功地解决了，通常意味着问题本身的结构存在一个有趣且有用的东西：存在一个局部决策，可以用来构建（整体）最优解。
区间调度问题
描述：有一组请求{1,2,…,n}；第i个请求对应于一个时间区间，从s(i)开始到f(i)结束。如果在一个请求的子集中，没有两个请求在时间上重叠，我没说这个子集是相容的。我们的目标是接受尽可能大的相容子集，成为最优子集。思考过程：选择最早开始的请求？选择最小时间的请求？选择最小冲突的请求？最后发现，应该首先接受最先完成的请求。证明（略）。时间复杂度O(n log n)
最小化延迟的调度
描述：我们有一个资源和一组n个请求，假设资源在时间s开始可用，请求i有一个截止时间d(i)，它需要一个长度为t(i)的连续时间区间，不同的请求分配不能重叠。求最优子集。思考过程：按照长度t(i)增加的顺序安排作业？按照增加的宽裕时间d(i)-t(i)来排序作业？最后，只按照截止时间d(i)递增的顺序对作业进行排序。证明（略）。这种不顾及作业长度的决策，居然可以提供最优解。
最优缓存的调度
考虑存储在主存中的n个数据集合U。还有一个更快的内存（即缓存），可以在任何时候保存k<n个数据项。假设缓存最初保存k个数据项。从U中提取一系列数据项D=d1,d2,..dm提供给我们，在处理它们时，必须决定在缓存中保留哪k项。当需要提供数据项di时，如果在缓存中，就可以非常快地访问它。如果缓存已满，则逐出其他数据，为di腾出空间。我们希望缓存未命中的情况尽可能少。结论：当di需要载入缓存时，逐出最远未来需要用到的数据项。证明（略）
求解图的最短路径
给定有向图G=(V,E)，以及一个起始节点s。假设s具有到G中每个其他节点的路径。每条边e具有长度L>=0，表示经过e所需要花费的时间。对于路径P，P的长度L(P)是P中所有路径长度之和。确定从s到图中每个其他节点的最短路径。Dijkstra算法：
Dijkstra算法(G,L)
令S是要探索的节点集
For 每个u ∈ S，保存一个距离d(u)
初始 S={s}且d(s)=0
While S ∉ V
选择一个节点v ∉ S，使得从S到v至少有一条边，且
d'(v) = min d(u)+L最小
将v加入S并定义d(v)=d'(v)
EndWhile有没有发现这个贪心算法和梯度下降多么神似！
求解最小生成树
对于有一组位置V={v1,v2,…vn}，我们希望在它们之上构建一个通信网络。网络应该联通，且尽可能便宜地构建它。Kruskal算法：从没有任何边的情况下开始，并通过增加开销的书序连续插入边，从而构建一个生成树。按此顺序加入时，只要没有产生环，就插入它，如果产生环，就抛弃并继续。另外，通过Dijkstra算法思想也可以生成最小生成树，称为Prim算法。还可以运行Kruskal算法的“后向”版本，按照开销降低的顺序删除边。这三种算法都可以达到最优解，证明略。
聚类问题
假设有集合U，包含n个对象，标记为p1,p2,…pn。对于每一对pi和pj，有一个数值距离d(pi,pj)，且d(pi,pj) > 0，并且距离是对称的。给定一个参数k，将U中的对象划分成k个组，我们说U的k聚类，表示把划分成k个非空集合C1,C2,…Ck。将k聚类的间隔定义为不同聚类之间任何一对点之间的最小距离。如果寻找最大可能间隔的k聚类。通过Kruskal算法生成最小生成树时，把已经联通的节点视为一个聚类，那么当到达k个聚类时，既可以停止。
哈夫曼码与数据压缩
最优前缀码：对于指定的字母表和这些字母的频率集合，我们希望产生尽可能高效的前缀码，即每个字母的平均位数达到最小的前缀码。前缀码可以用二叉树来表示，且对应于最优前缀码的二叉树是满的。哈夫曼改进了香农-法诺码，算法如下：
对于给定频率的字母表S构建前缀码
IF S有两个字母 then
将一个字母编码为0，另一个字母编码为1
Else
令y*和z*史频率最低的两个字母
通过删除y*和z*，并用一个新字母w代替它们，其频率是fy*+fz*，构建一个新字母表S'
递归第为S'构建前缀码，使用树T'
定义S的前缀码如下：
从T'开始
取标记为w的叶节点，并在它下面加上标记为y*和z*的两个子节点
Endif证明哈夫曼算法的最优性（略），时间复杂度O(klogk)