JUFE • SSCE__Dr. Aihua Yin 第5章 贪心算法 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 考核方式调整 1、每周收取上周的 手绘 算法流程图描述，每次计 2 分 2、每月收取 2个 算法 实现的程序，每次记 6 分 3、期末完成大作业，记 40分 4、课堂点名记 10分，其他分数稍作调整 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin Content 贪心算法原理 算法实例 单源最短路径问题 最小耗费生成树(Kruskal) 最小耗费生成树(Prim) 文件压缩 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 小样例：背包问题 0-1背包问题： 给定 n 种物品和一个背包。物品 i 的体积是vi，其价值为 si，背包的容量为 C。应如何使得装入背包中物品的总价值最大？ 普通背包问题： 可以选择物品 i 的一部分装入背包。 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 贪心算法思路 对普通背包问题而言，计算每种物品单位体积的价值 yi = si / vi 将尽可能多的单位体积价值最高的物品装入背包。 两个自然要做的事情是： 1、计算 yi ，i = 1, 2, …, n 2、给 yi 排序 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 贪心算法 对普通背包问题而言，计算每种物品单位体积的价值 yi = si / vi 将尽可能多的单位体积价值最高的物品装入背包。 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin … un v1 v2 v3 … vn s1 s2 s3 … sn y1 y2 y3 … yn yi = si / vi, i = 1, 2, 3, …, n Y1  Y2  Y3  …  Yn yi i1 i2 i3 … in JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin void Knapsack(int n, int M, int V[], int S[], int X[], f Y[]){ Sort(n, V, S, Y); //将各种物品按单位体积价值排序 int i; for(i=1; i<=n; i++) X[i] = 0; //将解向量初始化为零 int C = M; // 将背包剩余容量初始化为 M for(i=1; i<=n; i++){ if( V[i]>C ) break; X[i] = 1; C -= V[i]; } if(i<=n) X[i] = C/V[i]; JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 注意下标的对应关系！ 算法正确吗？ 考察 C 的单位空间的物品价值，就不难证明其正确性！ 贪心算法就是一个局部搜索！ JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 单源最短路径问题 设：G = (V, E) 为一个有向图，每一条边都具有非负长度，有一个特异顶点 s 称为源。 求：从 s 到 V 中每一个其他顶点 v 的距离，即最短路径 d(v) 。 假设：V = {1, 2, …, n}，并且 s = 1。 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 实例 3 2 1 6 4 5 7 3 & 10 7 12 11 6 1 8 4 9 2 5 13 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin Dijkstra 算法的基本思想 一开始，将顶点分为两个集合 X 和 Y，其中 X 包含的是距离已经确定的顶点， Y 则相反。令 λ(y) 为 Y 中顶点 y 只经过 X 中顶点的最短路径的长度，则 初始时 X = {1}，Y = {2, 3, …, n}； 从 Y 中选定距离已经确定的顶点 y，移至 X； 更新 Y 中与 y 相邻的其他顶点的标记，找出该值最小者； 迭代直至 Y 为空。 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin “钓鱼”算法 站位——确定 y 下饵——更新标记 咬钩——选中最小标记顶点 起竿、入篓——被选中的顶点进入“已确定距离的点集” JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 小样例 1 ∞ 4 1 2 3 4 5 6 12 9 13 15 17 19 ∞ ∞ 10 12 8 17 13 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin Dijkstra 算法步骤 输入: 含权有向图 G = (V，E) ，V = (1，2， ··· ，n)。 输出: G 中顶点 1 到其他顶点的距离。 1. X=｛1｝; Y = V-｛1｝; [1] = 0 2. for y = 2 to n 3. if y 相邻于 1 then [y]= length（1，y） 4. else [y] = 5. end if 6. end for JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 7. for j = 1 to n - 1 8. 令 yY，使得 [y]为最小 9. X = X∪{y} // 将顶点 y 加入 X 10. Y = Y - {y} //将顶点 y 从 Y 中删除 11. for 每条边( y，w ) , wY 12. [w] > [y] + length（y, w） then 13. [w] = [y] + length（y, w） 14. end for 15. end for JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 引理 在 Dijkstra 算法中，设顶点 y 在第 8 步中被选中，如果标记 [y] 是有限的，那么 [y] = d[y] 任务：画出 Dijkstra 算法流程图，编写其代码 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 时间复杂度 第8步： 执行了 n-1 次，每次时间是 Θ(n) 共需时间 Θ(n2) 第11步： For 循环执行了m 次，m = |E| 共需时间 Θ(m) 算法的时间复杂度： Θ(n2+m) JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 定理 1 给出一个边具有非负权的有向图 G 和源顶点 s，Dijkstra 算法在时间 θ(n2)内找出从 s 到其他每一顶点 距离的长度。 有人想过 Dijkstra 算法的 Step8 中，如果有多个 y 满足被选中条件，算法该如何进行吗？ 对算法的任何小小质疑都意味着进步！！！ JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin Dijkstra算法改进 思路：用最小堆数据结构来保持集合Y 中的顶点，使 Y 组中离V-Y 最近的顶点 y 可以在 O(log n) 时间内被选出。 堆定义：是一个几乎完全的二叉树，总是保持父节点的键值不小于子节点的键值。 堆运算：SIFT-UP、SIFT-DOWN、 DELETEMAX、DELETE、INSERT、MAKEHEAP JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 输入: 含权有向图 G = (V，E) ，V = (1，2， ··· ，n)。 输出: G 中顶点 1 到其他顶点的距离，假设已有一个空堆H。 1. Y = V -｛1｝; [1] = 0; key(1) = [1] 2. for y ←2 to n DG Dijkstra 算法 3. if y 邻接于 1 then 4. [y]= length（1，y）； key (y) = [y] 5. INSERT (H，y) 6. else 8. [y] = ; key (y) = [y] 9. end if 10. end for JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 11. for j = 1 to n - 1 12. y = DELETEMIN(H) 13. Y = Y -{y} // 将顶点 y 从 Y 中删除 14. for 每个邻接于 y 的顶点 w Y 15. if [y] + length（y, w） < [w] then 16. [w]= [y] + length（ y ，w）； key (y) = [y] 17. end if 18. if w H then INSERT(H，w) 19. else SIFT-UP( H ，POSIT-1 (w)) 20. end if 21. end for 22. end for JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 时间复杂度 运行时间主要取决于堆运算： DELETE: n-1 INSERT: n-1 SIFT-UP: m-n+1 每个堆运算用 Ο(log n) 时间，得到总共需要Ο(m log n) 时间。 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 堆排序： 建堆 j = , …, 1 while i = 1, …, n-1 对换节点 k = n+1-i 与节点 k = 1 Sift-down(H-i, 1) // 序列最后的 i 个元素已经排好序 end while return JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 堆的运算——上筛 Sift-up(H, i) 目标：上移 H[i] 使得它的键值不大于其父节点的 flag = 0; if(i = 1) then exit; //节点 i 为根节点 while i = 1 or flag = 1 if( H(i) > H( ) ) then 对换这两个节点 else flag = 1 i = end while return JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 堆的运算——下筛 Sift-down(H, i) 目标：下移 H[i] 使得它的键值不大于其父节点的 flag = 0; if( 2i > n ) then exit; //节点 i 为叶子节点 while 2i > n or flag = 1 i = 2i if (i+1n && H(i+1) > H( i ) ) then i = i+1 if( H(i) > H( ) ) then 对换这两个节点 else flag = 1 end while return JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 堆的运算——插入 Insert(H, x) 目标：向堆 H 中插入一个元素 x n = n+1; //增加 H 的大小 H[n] = x Sift-up(H, n) JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 堆的运算——删除 Delete(H, i) 目标：删除堆中元素 H[i] x = H[i]; y = H[n]; n = n-1 //减少 H 的大小 if( i=n+1) then exit; H[i] = y if( yx ) then Sift-up( H, i ) else Sift-down( H, i ) end if JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 堆的运算——删除最大值 DeleteMax( ) 目标：删除堆中最大元素 x x = H[1]; n = n-1 //减少 H 的大小 delete( H, 1) H[i] = y return x JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 堆的运算——建堆 MakeHeap(A) 目标：将一个 n 元数组 A，转化为一个堆 for i = down to 1 Sift-down( A, i ) end for JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 定理 2——高级论题 给出具有非负权重的边和源顶点 s 的图 G， “DG Dijkstra 算法”可在 O(mlogn) 时间内找出从 s 到其他每一顶点的距离。 如果 图是稠密的，即对于某个  > 0，m  n1+，那么它可以被改善为在时间 O(m /) 内运行。 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 最小生成树问题 设 G = (V, E) 是一个具有加权边的连通无向图。G 的一棵生成树 (V,T) 是 G 的作为树的子图。 如果给 G 加权并且 T 的各边的权的和为最小值，那么 (V, T) 就称为 最小耗费生成树，或简称为 最小生成树。 问题背景：设计要求：在 n 个城市之间建设网络，只需保证连通即可，求最经济的架设方法。 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin Kruskal 算法概要 假设：G 为连通的； 基本步骤： 设 (V,T) 为当前构建的森林，其初始为 (V, {}); 对 G 的边以非降序权重排列； 按序考察每一条边 e，如果把 e 加入T 中不会构成回路，则加入；否则丢弃。 迭代直至 |T| = n-1。 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 算例 1 2 3 4 5 6 11 9 13 7 1 2 3 4 5 6 1 3 9 2 4 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin Kruskal 算法描述 输入: 包含 n 个顶点的加权连通无向图 G ＝(V，E)。 输出: 由 G 生成的最小耗费生成树 T 组成的边的集合。 1. 按非降序权重将 E 中的边排序 2. for 每个顶点 v V 3. MAKESET( {v} ) 4. end for JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 5. T ＝ { } 6. while |T| < n - 1 7. 令 (x，y) 为 E 中的下一条边 8. if FIND(x) ≠ FIND(y) then 9. 将 (x，y) 加入 T 10. UNION (x，y) 11. end if 12. end while JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin Kruskal 算法实现关键处 1. Step 1 中，排好序的边的集合 如何存储？ 2. Step 3 中， MAKESET( {v} ) 的含义是什么？ 3. Step 8 中， FIND(x) 与 FIND(y) 的含义是什么？ 4. Step 10 中， UNION (x，y) 的含义是什么？ JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin Kruskal 算法实现提示 1. Step 1 中，排好序的边的集合 存储：点对，二维数组 2. Step 3 中， MAKESET( {v} ) 的含义：森林，一维数组 3. Step 8 中， FIND(x) 与 FIND(y) 的含义： 顺着下标找 4. Step 10 中， UNION (x，y) 的含义：联合森林成树 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 边按权重排序如下 （边起点,边终点,边权重） 1 2 3 4 5 6 11 9 13 7 (1, 2, 1) (1, 3, 2) (4, 6, 3) (5, 6, 4) (2, 3, 6) (4, 5, 7) (3, 4, 9) (2, 4, 11) (3, 5, 13) 最小支撑树边集 T={ } 1 2 3 4 5 6 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 边按权重排序如下（边起点, 边终点, 边权重） ：(1,2,1)， (1,3,2)，(4,6,3)，(5,6,4)，(2,3,6)，(4,5,7)，(3,4,9)，(2,4,11)，(3,5,13) 考察边(1,2,1) (Find(1)=1)≠(Find(2)=2) T={(1,2,1)} Union(1,2) 1 2 3 4 5 6 ② 2 ① ③ ④ ⑤ ⑥ 考察边(1,3,2) (Find(1)=2)≠(Find(3)=3) T={(1,2,1),(1,3,2)} Union(1,3) 1 2 3 4 5 6 ② 2 ① ③ ④ ⑤ ⑥ JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 边按权重排序如下（边起点, 边终点, 边权重） ：(1,2,1)， (1,3,2)，(4,6,3)，(5,6,4)，(2,3,6)，(4,5,7)，(3,4,9)，(2,4,11)，(3,5,13) 考察边(4,6,3) (Find(4)=4)≠(Find(6)=6) T={(1,2,1),(1,3,2),(4,6,3)} Union(4,6) 1 2 3 4 5 6 2 6 ② ⑥ ① ③ ④ ⑤ JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 边按权重排序如下（边起点, 边终点, 边权重） ：(1,2,1)， (1,3,2)，(4,6,3)，(5,6,4)，(2,3,6)，(4,5,7)，(3,4,9)，(2,4,11)，(3,5,13) 考察边(5,6,4) (Find(5)=5)≠(Find(6)=6) T={(1,2,1),(1,3,2),(4,6,3),(5,6,4)} Union(5,6) 1 2 3 4 5 6 1 2 3 4 5 6 2 6 2 6 ② ⑥ ② ⑥ ① ③ ④ ⑤ ① ③ ④ ⑤ JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 边按权重排序如下（边起点, 边终点, 边权重） ：(1,2,1)， (1,3,2)，(4,6,3)，(5,6,4)，(2,3,6)，(4,5,7)，(3,4,9)，(2,4,11)，(3,5,13) 考察边(2,3,6) (Find(2)=2)＝(Find(3)=2) 丢弃边 (2,3,6) T={(1,2,1),(1,3,2),(4,6,3),(5,6,4)} 1 2 3 4 5 6 2 6 ② ⑥ ① ③ ④ ⑤ JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 边按权重排序如下（边起点, 边终点, 边权重） ：(1,2,1)， (1,3,2)，(4,6,3)，(5,6,4)，(2,3,6)，(4,5,7)，(3,4,9)，(2,4,11)，(3,5,13) 考察边(4,5,7) (Find(4)=6)＝(Find(5)=6) 丢弃边(4,5,7) T={(1,2,1),(1,3,2),(4,6,3),(5,6,4)} 1 2 3 4 5 6 2 6 ② ⑥ ① ③ ④ ⑤ JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 边按权重排序如下（边起点, 边终点, 边权重） ：(1,2,1)， (1,3,2)，(4,6,3)，(5,6,4)，(2,3,6)，(4,5,7)，(3,4,9)，(2,4,11)，(3,5,13) 考察边(3,4,9) (Find(3)=2)≠(Find(4)=6) T={(1,2,1),(1,3,2),(4,6,3),(5,6,4),(3,4,9)} Union(3, 4) 1 2 3 4 5 6 1 2 3 4 5 6 2 6 2 6 ⑥ ② ⑥ ② ④ ⑤ ① ③ ① ③ ④ ⑤ JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 思考？ 如何实现 Step 8 中， FIND(x) 与 FIND(y) ？ 讨论尝试如何分支完成？ 如何实现 Step 10 中， UNION (x，y) ？ 任务与要求 数据标准：节点数 > 10，边数 > 100 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 时间复杂度 第1步：O(m log m) 第2步：Θ(n) While循环： 第7步： Θ(n) 第8步： O(m) 第10步：Θ(n) 算法时间：O(m log m) JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 定理 在一个有 m 条边的加权无向图中，算法 Kruskal 可以在 O(m logm) 时间内找出最小耗费生成树 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin Prim 算法 与算法 Kruskal 完全不同。 与算法 Dijkstra 非常相似。 其改进算法也与 ShortestPath 算法类似。 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin PRIM 算法的基本思想 1. T ={}; X = {1}; Y = V-{1}; 2. while Y ≠{} 3. 设 (x, y) 是最小权重的边，其中，xX, yY 4. X = X ∪ { y } 5. Y = Y - { y } 6. T = T ∪ { (x, y) } 7. end while JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 实例 11 9 1 ∞ 2 4 11 1 3 ∞ 1 6 9 7 6 3 2 4 13 3 5 ∞ 13 2 2 4 7 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin Prim 算法步骤 输入: 含权有向图 G = (V，E) ，V = (1，2， ··· ，n)。 输出: G 中顶点 1 到其他顶点的距离（已有一个空堆H） 1. T ← { }; X ←{1}; Y ← V - {1} 2. for y ←2 to n 3. if y 邻接于 1 then // 这是扫描，站在 “1” 处 4. N[y]← 1 // 这是“反制”，y 将作用于 1 5. C[y] ← c [y，1] //体现“反制”，刷标签 6. else C[y] ← //“反制”失效，标个“无穷” 7. end if 8. end for JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 9. for j ← 1 to n – 1 //寻找 n – 1 条边 10. 令 y  Y ，使得 C[y] 最小 11. T ← T ∪ {(y，N[y])} //将边 (y, N[y]) 加入T 12. X ← X ∪ {y} // 将顶点 y 加入 X 13. Y ← Y – {y} // 从 Y 删除顶点 y 14. for 每个邻接于 y 的顶点 w  Y ///扫描，立足点 y 15. if c[y，w] < C[w] then //“反制”、“贴标签”有条件！ 16. N[w] ← y 17. C[w] ← c[y，w] 18. end if 19. end for 20. end for JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 定理 在一个有 m 条边的加权无向图中，算法 PRIM 可以在 Θ(n2) 时间内找出最小耗费生成树 课堂练习：用PRIM算法求右图的最小耗费生成树 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 答案： JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 算法MST 步骤 下面讨论算法MST 输入: 含权连通无向图 G = (V，E) ，V = (1，2， ··· ，n)。 输出: 由 G 生成的最小耗费生成树 T 组成的边的集合。 1. T ← {}; Y ← V - {1} 2. for y ←2 to n 3. if y 邻接于 1 then 4. N[y]← 1 5. key[y] ← c [1，y] 6. INSERT(H，y) 7. else key[y] ← 8. end if 9. end for JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 10. for j ← 1 to n – 1 //查找 n – 1 条边 11. y ← DELETEMIN(H) 12. T ← T ∪ {(y，N[y])} //将边(y,N[y])到T 13. Y ← Y – {y} //从 Y 删除顶点 y 14. for 每个邻接于 y 的顶点 w  Y 15. if c[y，w] < key[w] then 16. N[w] ← y 17. key[w] ← c[y，w] 18. end if 19. if w H then INSERT(H，w) 20. else SIFTUP(H，H-1(w) ) 21. end for 22. end for JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 定理 在一个有 m 条边的加权无向图中，算法 MST 可以在 O( m logn) 时间内找出最小耗费生成树。 如果 图是稠密的，即对于某个  > 0，m  n1+，那么它 可以被改善为在时间 O(m /) 内运行。 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 文件压缩问题 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 方法1：定长比特数表示每个字符 方法2：变长比特数表示每个字符 频度大的字符用短编码 频度小的字符用长编码 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin Prefix Restriction 一个字符的编码不能是另一个字符编码的前缀。 例如：若字符a的编码是01， 则字符b就不能编码为010， 否则当遇到01时，无法判断。 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin Huffman 编码 C={a,b,c,d,e} f(a)=20 f(b)=7 f(c)=10 f(d)=4 f(e)=18 编码 a=01,b=110,c=10,d=111,e=00 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 基本原理： 总是选择频度最小的两个节点ci和cj构建一个新节点c，c为ci和cj的父节点，其频度为两个子节点的频度和。 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 满二叉树： 内部节点都恰好有两个分支，标记为0和1 树叶对应于文件中的字符 从根到叶的每一条路径上的0和1的序列对应相关字符的编码 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 2. V = C ; T = {} 3. for j = 1 to n - 1 4. c = DELETEMIN(H) 5. c' = DELETEMIN(H) 6. f(v)=f(c) + f(c') //v是一个新节点 7. INSERT(H，v) 8. V = V∪{v} //添加 v 到 V T=T∪{(v，c)，(v，c')} //使 c 和 c' 成为 T 中 v 的孩子 10. end for JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 课堂练习： 假设一个文本文件TFile中只包含7个字符{A，B，C，D，E，F，G}，这7个字符在文本中出现的次数为{5，24，7，17，34，5，13}，利用哈夫曼树可以为文件TFile构造出符合前缀编码要求的不等长编码。 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 答案： JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 贪心算法特征 贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。 即使贪心算法不能得到整体最优解，其最终结果却是 最优解的很好近似。 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 影响因素 贪心选择性质 对一个具体问题，必须证明每一步所作的贪心选择最 终导致问题的一个整体最优解。 贪心选择后，问题简化为规模更小的类似子问题【最 优子结构性质】。 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin 最优子结构性质 一个问题的最优解包含着它的子问题的最优解， 称此问题具有最优子结构性质。 JUFE • SSCE__Dr. Aihua Yin 2019/4/16

JUFE • SSCE__Dr. Aihua Yin GA 和 DP的区别 都具有最优子结构性质。 动态规划算法，每步所作的选择往往依赖于相关子 问题的解，只有解出相关子问题才能作出选择。 贪心算法，仅在当前状态下作出最好选择，即局部 最优选择，但不依赖于子问题的解。 JUFE • SSCE__Dr. Aihua Yin 2019/4/16