2006 算法设计qiu-lec9

《2006 算法设计qiu-lec9》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、贪婪算法(GreedyAlgorithms)•Similartodynamicprogramming,butsimplerapproach算法设计与分析–Alsousedforoptimizationproblems(与动态规划方法相似，但更简单的解决优AlgorithmsDesign&Analysis化问题的方法，通常用于求解优化问题）•Idea:Whenwehaveachoicetomake,maketheonethatlooksbestrightnow（如有选择，选择眼下看起来最优的那个）第九讲：贪婪算法–Makealocallyoptimalchoice

2、inhopeofgettingagloballyoptimalsolution（局部最优→全局最优）华中科技大学软件学院•Greedyalgorithmsdon’talwaysyieldanoptimalsolution（贪婪算法不能保证一定得到最优解）邱德红主讲•Whentheproblemhascertaingeneralcharacteristics,greedy2005年4月algorithmsgiveoptimalsolutions（对于具有某些特征的问题，贪婪算法有最优解）12作业选择问题(ActivitySelection作业选择问题(Activi

3、tySelection)Problem)•SchedulenactivitiesthatrequireexclusiveuseofacommonSelectthelargestpossiblesetofnonoverlapping(mutuallyresource(对n个作业进行排程，这些作业在执行期间需要专用某个共compatible)activities.（选出最多个不冲突的作业）同的资源）E.g.:S={a1,...,an}–setofactivities（作业集合）•aineedsresourceduringperiod[si,fi)（作业执行时间）i1

4、234567891011–si=starttime（起始时刻）andfi=finishtimeofactivityaisi130535688212（完成时刻）–0≤si

5、结束。二、ai在aj结束后的先后顺序排列）发生）•Asubsetofmutuallycompatibleactivities:{a3,a9,a11}（可协调作业fi≤sjfj≤si集合的例子）ijji•Maximalsetofmutuallycompatibleactivities:{a1,a4,a8,a11}and{a2,a4,a9,a11}（最多可协调作业的集合）34优化基础（OptimalSubstructure）问题描述(RepresentingtheProblem)•Definethespaceofsubproblems:(定义子问题空间)•Inase

6、tSijweassumethatactivitiesaresortedinS={a∈S:f≤s

7、radictionwithfi≥fj!（互相矛盾）•AddfictitiousactivitiesS=Sentirespaceofactivities0,n+1⇒Sij=∅(thesetSijmustbeempty!)–a0=[-∞,0)（假设作业）（完整问题空间）•WeonlyneedtoconsidersetsSijwith–an+1=[∞,“∞+1”)0≤i

8、lem:（子问题）Aij