




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
信息工程大学算法设计与分析贪心法—活动安排问题国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版活动安排问题:
设有n个活动的集合S={1,2,…,n},其中每个活动都要求使用同一资源,如教室、会场等,而在同一时间内只有一个活动能使用这个资源。si,fi分别为活动i的开始和结束时间,且si<fi
。活动i与j相容
si
fj或sjfi。求:最大的两两相容的活动集A。
问题的解需要满足以下条件:是n个活动的一个子集任何两个活动都是相容的活动个数最多活动的属性:开始时间、结束时间、持续时间可能的贪心策略:尽早开始,优先安排开始时间早的活动占用时间短,优先安排持续时间短的活动使剩余时间更多,优先安排结束时间早的活动思考:活动安排问题可以用贪心法求解吗?选择题。你觉得以下哪种贪心选择策略可以得到活动安排问题的最优解?A.优先安排开始时间早的活动B.优先安排持续时间短的活动C.优先安排结束时间早的活动D.以上都不对策略1:优先安排开始时间早的活动错误该策略得到的解:活动1最优解:活动2、活动3策略2:
优先安排持续时间短的活动错误该策略得到的解:活动4、5最优解:活动1、2、3策略3:优先安排结束时间早的活动问题:该策略对所有实例都能得到最优解吗?该策略对两个实例都得到了最优解。
时间复杂度为O(nlogn)S={1,2,…,n}是活动集,且f1
…
fn
。
定理:算法GreedySelect执行到第k步,选择k项活动i1=1,i2,…,ik,那么存在最优解A包含i1=1,i2,…,ik。证明:归纳基础:k=1,存在最优解包含活动1。任取最优解A,A中的活动按结束时间递增排列。如果A的第一个活动为j,j
1,由于f1
fj,则有A′=(A
{j})
{1},且A′也是最优解,并含有活动1。
j…A1…A’归纳步骤:假设命题对k为真,证明对k+1也为真。算法执行到第k步,选择了活动i1=1,i2,…,ik,根据归纳假设存在最优解A包含i1=1,i2,…,ik。
最优解A中剩下的活动子集B来自集合S′={i|i
S,si
fk},且A={i1,i2,…,ik}B。其中B是S′的最优解。若不然,设S′的最优解为B*,B*的活动比B多,那么B*
{1,i2,…,ik}是S的最优解,且比A的活动多,与A的最优性矛盾。待选集合S′1,i2,…,ik不相容活动集BAB*B={ik+1,…}?将S′看做一个子问题,根据归纳基础,存在S′的最优解B′含有S′中的第一个活动,即ik+1,且|B′|=|B|,于是也是原问题的最优解.待选集合S′1,i2,…,ikBB’ik+1活动安
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 医学科研课题申报书
- 2025年注册会计师备考的资源利用与试题及答案
- 银行从业资格证考试切入点分析试题及答案
- 精心准备2025年特许金融分析师考试试题及答案
- 项目管理考试的心理素质要求试题及答案
- 财务与审计的关联与差异试题及答案
- 项目目标验证与跟踪机制的构建试题及答案
- 注册会计师计算题试题及答案解析
- 教师课题研申报书
- 理财师与投资者的信任关系2025年国际金融理财师考试试题及答案
- 技术转让合同备忘录协议备忘录(2024年版)
- 注册会计师财务成本管理章节练习题三
- 第十一单元课题1化学与人体健康-2024-2025学年九年级化学人教版(2024)下册
- 《子宫内膜异位》课件
- 文旅场所安全培训课件
- 《商标侵权案例分析》课件
- 脑梗死的护理查房
- 导游讲解的常用技巧教案
- 车位租赁协议
- 肺结节诊治中国专家共识(2024年版)解读
- 地震监测设备使用安全检查表
评论
0/150
提交评论