算法201404-贪心案例分析.ppt

* 最优子结构性质 设T是表示C的一个最优前缀码的完全二叉树， C中字符c的频率为f(c)。设x,y是T中两个叶子结点且为兄弟，z为它们的父结点。若将z看作是具有频率f(x)+f(y)的字符，则树T’=T-{x,y}表示字符集C’=C-{x,y}+{z}的一个最优前缀码。 证明： 首先T的平均码长B(T)可用T’的平均码长B(T’)表示。 * 若T’表示的C’的前缀码不是最优的，则存在T’’表示的C’的最优前缀码，Ｂ(T’’)B(T’). z作为Ｃ’ 中的一个字符，故z作为T’’中的一个叶子，若将x,y加入T’’中，作为z的儿子结点，得到表示C的前缀码的二叉树Ｔ’’’， 与Ｔ最优矛盾 T’表示的C’的前缀码是最优的 满足最优子结构性质 * 哈夫曼编码的实现 教材上给出的算法huffmanTree中，编码字符集中每一字符c的频率是f(c)。以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。经过n－1次的合并后，优先队列中只剩下一棵树，即所要求的树T。 算法huffmanTree用最小堆实现优先队列Q。初始化优先队列需要O(n)计算时间，由于最小堆的removeMin和put运算均需O(logn)时间，n－1次的合并总共需要O(nlogn)计算时间。因此，关于n个字符的哈夫曼算法的计算时间为O(nlogn)。 构造哈夫曼树 * Note 1 ) 贪心算法求解问题的类型 2）贪心算法求解问题的关键 3）贪心算法求解问题的贪心选择策略（算法正确性证明） 4）贪心算法的复杂度 5）贪心与分治之间的关系（是否可以递归？） 贪心算法的复杂度往往不在贪心算法的执行，而多数在于确定贪心选择策略后如何对输入进行预处理，例如按照某种策略进行排序的算法选择 步步为“赢” 子问题都是先选择再求解，若不知道怎样选择怎么办？ 在已求解的基础上进行选择 动态规划 * 1） 设有一个文本T，它的字母表为 ，各个字符在T中出现的概率如下表4.1所示，求T中各个字符的哈夫曼编码。 表4.1 中各字符在文本T中出现的概率 字符 A B C D E F 出现概率 0.48 0.21 0.01 0.03 0.25 0.02 作业 2）试证明：若T为图G的一棵最小生成树，S为G的一个联通子图，则T?S属于S的某棵最小生成树。 * 3） 删数问题 键盘输入一个高精度的正整数ｎ（=240位），去掉任意ｓ个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的ｎ和ｓ，寻找一种方案，使得剩下的数最小。 输入：ｎｓ输出：最后剩下的最小数｛样例输入}1785434｛样例输入}13 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Dijkstra算法的计算复杂性 Dijkstra 算法有两层循环，外层循环为n次，内层有两个循环：一个是选出最小的w(第5行)，另一个是修订dis[v](第7、8行)。它们的次数都是n/2，所以内层循环的时间为O(n)。 因此Dijkstra算法的时间复杂度为 O(n2) Dijkstra 算法能求出从源到其它各顶点的最短通路的长度，但是却并没有给出其最短通路。 如何构造？（思考） Procedure Dijkstra { (1) S:={1}; //初始化S (2) for i:= 2 to n do //初始化D (3) dist[i] =C[1, i] ; //初始时为源到顶点i一步的距离 (4) for i :=1 to n-1 do { (5) 从V-S中选取一个顶点u使得dist[u]最小； (6) 将u加入到S中；//将新的最近者加入S (7) for ?w∈V-S do //依据最近者u修订dist[v] (8) dist[w] := min(dist[w] , dist[u]+C[u ,w] } } * 作业 1 （1）求以下情况背包问题的最优解：n=7,M=15,(p1,…p7)=(10,5,12,7,6,16,3)和,(w1,…w7)=(2,3,5,7,1,4,1)。 （2）将以上数据情况的背包问题记为I。设FG(I)是物品按照pi的非递增顺序输入时由GREEDY-KNAPSACK所生成的解， FO(I)是一个最优解，问FO(I) /FG(I) 是多少？ （3）当物品按照wi的非降