北京大学屈婉玲算法设计与分析最新课件0r4.pdf

《北京大学屈婉玲算法设计与分析最新课件0r4.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第4章贪心法（GreedyApproach）4.1贪心法的设计思想4.2贪心法的正确性证明4.3对贪心法得不到最优解情况的处理444.4贪心法的典型应用4.4.1最优前缀码4.4.2最小生成树4.4.3单源最短路径14.1贪心法的设计思想活动选择问题输入：S={12{1,2,…,n}为n项活动的集合，s,f分别为活动iii的开始和结束时间，活动i与j相容⇔s≥f或s≥f.ijji求：最大的两两相容的活动集A实例i12345678910s1325456882if45679910111213i策略1：排序使得s≤s≤…≤s，从前向后挑

2、选12n策略2：排序使得f－s≤f－s≤…≤f－s，从前向后挑选1122nn策略3：排序使得f≤f≤…≤f，从前向后挑选12n以上策略中的挑选都要注意满足相容性条件2两个反例策略1：S={1,2,3}，s=0,f=20,s=2,f=5,s=8,f=15112233策略2：S={1,2,3}，s=0,f=8,s=7,f=9,s=8,f=1511223323102581015202130258101520贪心算法算法GreedySelect输入：活动集S，s，f,i=12=1,2,…,n，且f≤…≤fii1n输出：A⊆S，选中的活动子

3、集1.n←length[S]//]//活动个数2.A←{1}3.j←1/1///已选入的最后一个活动的标号4.fori←2tondo5.ifs≥f//判断相容性ij6.thenA←A∪{i}7.j←i8.returnA最后完成时间t=max{f:k∈A}k4算法运行实例输入：S={1,2,…,10}i12345678910s1305356882if45678910111213i解:A={1,4,8},t=11时间复杂度：排序+活动选择=O(nlogn)+O(n)=O(nlogn)问题：如何证明该算法对所有的实例都能得到正确的解？5

4、算法的正确性证明定理1算法Select执行到第k步,选择k项活动i=1,i,…,12i,那么存在最优解A包含i=1,i,…,ik12k根据定理：算法至多到第n步得到最优解证：S={1,2,…,n}是活动集，且f≤…≤f1n归纳基础：k=1,证明存在最优解包含活动1任取最优解A,A中的活动按截止时间递增排列.如果A的第一个活动为j，j≠1,令A’=(A−{j})∪{1},由于f≤f,A’也是最优解，且含有1.1j6算法正确性证明（续）归纳步骤：假设命题对k为真,证明对k+1也为真.算法执行到第k步,选择了活动i=1,i,…,i,根据

5、归纳假设12k存在最优解A包含i=1,i,…,i,12kA中剩下的活动选自集合S’={i

6、i∈S,s≥f},且ikA={i,i,…,i}∪B12kB是S’的最优解.（若不然,S’的最优解为B*,B*的活动比B多，那么B*∪{1,i,…,i}是S的最优解，且比A的活动多,2k与A的最优性矛盾.）根据归纳基础，存在S’的最优解B’含有S’中的第一个活动，即i,且

7、B’

8、=

9、B

10、,于是k+1{i,i,...,i}∪B'={i,i,...i,i}∪(B'−{i})12k12kk+1k+1也是原问题的最优解.7贪心算法的特点设计要素：(1)

11、贪心法适用于组合优化问题，该问题满足优化原则.(2)求解过程是多步判断过程，最终的判断序列对应于问题的最优解.(()3)判断依据某种“短视的”贪心选择性质，性质的好坏决定了算法的成败.(()4)贪贪法须行确心法必须进行正确性性明证明贪心法的优势：算法简单，时间和空间复杂性低84.2贪心法的正确性证明数学归纳法1.叙述一个描述算法正确性的命题P(n)，n为算法步数或者问题规模2.归纳基础：P(1)或P(n)为真,n为某个自然数003.归纳步骤：P(k)⇒P(k+1)第一数学归纳法∀k(k

12、1.分析算法的解的结构特征2.从一个最优解逐步进行结构变换(替换成分、交换次序等)3.证明上述变换最终得到算法的解、变换有限步结束、变换保持最优性不降低、9最优装载Loading问题：n个集装箱1,2,…,n装上轮船，集装箱i的重量w,轮船装i载重量限制为C，无体积限制.问如何装使得上船的集装箱最多？不妨设w≤c.inmax∑xii=1n∑wixi≤Ci=1x=0,1i=1,2,...,ni贪心法：将集装箱按照从轻到重排序，轻者先装10正确性证明命题：对装载问题任何规模为n的输入，算法得到最优解.对问题规模归纳，设集装箱从轻到重记

13、为1,2,…,n.证：k=1,只有1个箱子，算法显然正确.假设对于k个集装箱的输入，贪心法都可以得到最优解，考虑输入N={1,2,…,k+1},其中w≤w≤…≤w.12k+1由归纳假设，对于N’={2,3,…,k+1}，C’=C−w,贪心法得到1最