贪心算法.ppt

1计算机算法——设计与分析导论南开大学计算机科学与技术系刘璟 2 Chapter 5. Chapter 5. 贪心( 贪心( Greedy Greedy )技术)技术? 贪心策略的思想? 背包(Knapsack) 问题? Huffman 编码? 多机调度问题的近似解法? 单源最短路径的 Dijkstra 算法 贪心策略的思想? 付款问题已知: 现有的钞票面额和付款额 int m[ ]={ 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1}; int V; (可以由操作者输入) 输出: 各种币值的钞票数 int n[12]; 使得且最小。算法 付款问题的贪心算法 Pay (实际应用中,只是尽可能最少,但不一定最少) V]i[m]i[n 121i?????? 121i]i[n4 ? 铺砖问题有若干不同规格的砖,要铺满一块平台,总是希望用较少的砖。例如,有三种规格的砖: 2×2、 × 、 × ,要铺满 ×( m 2)的平面。采用贪心策略,需一块 2×2 的大砖及 25× 5+20 × 5=225 块 × 小砖。显然这不是最优解,用 × 的中砖加上 × 的小砖就可以了,需 58 块,小于贪心法的结果 226 块。>>>>>( 图着色等问题)? 贪心算法的基本思想贪心算法把一个整体最优问题分解为一系列的最优选择问题,但结果一般为近似最优。另一方面,贪心算法一般都比较简单,计算量小。它具有两种性质: 贪心选择性质和最优子结构性质。 5 ( Greedy-choice )性质整体最优解可以通过一系列局部最优的选择来完成(即贪心选择过程)。 2. 最优子结构( Optimal substructure )性质整体最优解中包含子问题的最优解或:问题解的整体最优性依赖于其局部子问题解的最优性。 3. 活动安排( Activity Selection )问题问题: 有n 种活动( 例如报告、会议) 的集合 A={1,2, … n}, 都需要占用某场地(报告厅或会议室),该场地同一时间只能安排一项活动。(也是一种调度问题,尽可能接多个定单) 已知: 活动 i 需要在时间段[S i,f i] 占用该场地,其中 S i与f i 是活动 i占用的起始时间和结束时间,且 S i<f i(i =1,2, …n)。 6 求解: 安排尽量多项活动在该场地进行,即求 A 的最大相容子集。这里的相容( patible ) 指活动的时间不相重叠。即活动 i,j 相容,当且仅当时间区间 [S i,f i]与[S j,f j] 不相交,即必须有 S i≥f j或S j≥f i成立。思路: 如果希望安排尽量多的活动,显然这里的贪心选择可以有两种不同的处理: ·选S i最小的,这样可以增大场地的利用率; ·选f i最小的,使得下一个活动可以更早开始。由于活动的占用时间长度没有限制,因此后一选择更合理。 7 为了在每一次选择时取当前可以安排的活动中最早结束的活动,应首先把 n 项活动按结束时间的先后进行升序排序。即,使 f 1≤f 2≤…≤f n, 然后在 S i值不小于当前时刻的活动中取 f i值最小者。算法: (1) 对活动集 A中的活动按 f i值排序(胜序), 得到数组 S[1..n] , f[1..n] ,其中 f[1] ≤ f[2] ≤…≤ f[n] ; (2) 集合 B={1} ; j=1 ; i=2 ; //活动 1肯定被选(3) if(S[i]>=f[j]){ B+={i} ; j=i ; } (4) i++ ; if(i<=n) goto (3) ; (5) end 。实例: 设 n=11 ,经过对结束时间按升序排序之后, S[1..n] 和 f[1..n] 的值为: 经计算,被选的活动集合 B={1,4,8,11} 。 i1 2 3 4 5 6 7 8 9 10 11 S[i] 1 3 0 5 3 5 6 8 8 2 13 f[i] 4 5 6 7 8 9 10 11 12 13 14 8 4. 讨论(1) 正确性:上述算法可转为下面的递推过程: 为证明算法的正确性,只需说明活动 1 肯定包含在最优活动子集B中即可,可以用归纳法证明。 1° n=1 时, A={1} , B={1} ,算法正确; f 1最小 9 2°设||