算法分析与设计2004春.课件.第04讲

《算法分析与设计2004春.课件.第04讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Lecture4.GreedyAlgorithm¢动态规划回顾¢活动问题选择分析¢贪婪算法要点¢拟阵概念清华大学软件学院宋斌恒1动态规划要点回顾¢最优子结构¢生产安排¢矩阵链乘¢LCS¢PrintNeatly¢最优二叉搜索树清华大学软件学院宋斌恒21最优子结构的关键步骤1.关键过程（点）选择，例如¢装配问题选择经过的装配站¢乘法问题选择括号分界线¢LCS问题如何确定子问题¢Printneatly问题选择在什么地方断（分）行做完选择后留下若干子问题清华大学软件学院宋斌恒3续2.最优选择成立假设：只需要假设其中的关键点假设成立

2、即可，如何选择、先不管3.子问题空间：在上述选择决定后，留下什么样的子问题才能保证上述问题的选择是最优的4.证明你的方案是最优的，方法：“Cut-and-paste”清华大学软件学院宋斌恒42AnalyzingPrintingneatlyagain¢断句点¢断句点确定后留下两类问题¢一类问题的不优美度要考虑最后一行数值；另一类问题的不优美度不考虑最后一行的数值；¢说明上述选择方法、证明上述选择方法的正确性。¢递归公式准备工作如何做？【见下页】清华大学软件学院宋斌恒5RecursiveFormula¢请问：如果C(i,j)表

3、示从第i个词开始到第j个词结束段落包括最后一行的不优美度，如果D(i,j)表示从第i个词开始到第j个词结束段落不包括最后一行的不优美度，假设有n个词，原问题的不优美度为¢D(1,n)！递归公式？¢C(i,j)=mini

4、j)=0¢如果编程：请问最严重的异常情况是什么？¢思考：如果字符宽度不同，上述方法有效否？¢进一步：如果字符宽度不同，其宽度可以无级缩放，每行两头完全对齐，如何定义优美度？清华大学软件学院宋斌恒7GreedyAlgorithm¢Sample1.活动选择问题¢Severalcompetingactivitiesthatrequireexclusiveuseofcommonresources(Sameplaceatafixedperiodoftime),withthegoalisofselectingamaximum-size

5、setofmutuallycompatibleactivitiesthatwishtousearesource(aperiodoftimeintheplace)清华大学软件学院宋斌恒84Mathematicalmodel¢Eachactivityaihasastarttimesiandfinishtimefi,where0≤si

6、.,ai,ajarecompatibleifsi≥fjorsj≥fi)¢S={a1,a2,…,an}¢Problem:Theactivity-selectionproblemistoselectamaximum-sizesubsetofScontainsmutuallycompatibleactivities清华大学软件学院宋斌恒9DefinitionofSolution¢AsubsetAofSisasolutionifalltheactivitiesinAaremutuallycompatible.¢Wecallasol

7、utionAisoptimalifitisasolutionwhosesizeisoneofthelongest.清华大学软件学院宋斌恒105Aninstanceoftheproblem¢S={[1,4),[3,5),[0,6),[5,7),[3,8),[5,9),[6,10),[8,11),[8,12),[2,13),[12,14)}¢Notice!Theelementsaresortedbytheendtime清华大学软件学院宋斌恒11一般概念讲解p.5¢Whatisanalgorithm:Awell-defined(

8、适定)computationalprocedurewhichtakesomevalue,orsetofvalues,asinput,andproducesomevalue,orsetofvalues,asoutput.Itisansequenceofcomputationalstepstransform