JUFE • SSCE__Dr. Aihua Yin

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

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

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

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

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

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

… 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

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

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

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

实例 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

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

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

小样例 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

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

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

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

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

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

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

输入: 含权有向图 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 算法 if y 邻接于 1 then [y]= length（1，y）； key (y) = [y] INSERT (H，y) else [y] = ; key (y) = [y] end if 10. end for JUFE • SSCE__Dr. Aihua Yin 2019/4/16

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

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

堆排序：建堆 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

堆的运算——上筛 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

堆的运算——下筛 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

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

堆的运算——删除 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

堆的运算——删除最大值 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

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

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

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

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

算例 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

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

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

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

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

边按权重排序如下（边起点,边终点,边权重） 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={ } JUFE • SSCE__Dr. Aihua Yin 2019/4/16

边按权重排序如下（边起点, 边终点, 边权重）：(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) ② 2 ① ③ ④ ⑤ ⑥ 考察边(1,3,2) (Find(1)=2)≠(Find(3)=3) T={(1,2,1),(1,3,2)} Union(1,3) ② 2 ① ③ ④ ⑤ ⑥ JUFE • SSCE__Dr. Aihua Yin 2019/4/16

边按权重排序如下（边起点, 边终点, 边权重）：(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) 2 6 ② ⑥ ① ③ ④ ⑤ JUFE • SSCE__Dr. Aihua Yin 2019/4/16

边按权重排序如下（边起点, 边终点, 边权重）：(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) 2 6 2 6 ② ⑥ ② ⑥ ① ③ ④ ⑤ ① ③ ④ ⑤ JUFE • SSCE__Dr. Aihua Yin 2019/4/16

边按权重排序如下（边起点, 边终点, 边权重）：(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)} 2 6 ② ⑥ ① ③ ④ ⑤ JUFE • SSCE__Dr. Aihua Yin 2019/4/16

边按权重排序如下（边起点, 边终点, 边权重）：(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)} 2 6 ② ⑥ ① ③ ④ ⑤ JUFE • SSCE__Dr. Aihua Yin 2019/4/16

边按权重排序如下（边起点, 边终点, 边权重）：(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) 2 6 2 6 ⑥ ② ⑥ ② ④ ⑤ ① ③ ① ③ ④ ⑤ JUFE • SSCE__Dr. Aihua Yin 2019/4/16

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

时间复杂度第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

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

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

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

实例 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

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

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

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

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

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

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

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

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

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

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

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

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

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

2019/4/16

2. V = C ; T = {} 3. for j = 1 to n - 1 c = DELETEMIN(H) c' = DELETEMIN(H) f(v)=f(c) + f(c') //v是一个新节点 INSERT(H，v) 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

课堂练习：假设一个文本文件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 2019/4/16

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

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

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

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

JUFE • SSCE__Dr. Aihua Yin

Similar presentations

Presentation on theme: "JUFE • SSCE__Dr. Aihua Yin"— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

JUFE • SSCE__Dr. Aihua Yin

Similar presentations

Presentation on theme: "JUFE • SSCE__Dr. Aihua Yin"— Presentation transcript:

Similar presentations

About project

反馈