- 1、本文档共15页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
002算法设计的两个例子
两个例子:调度
问题与投资问题
.
例1:调度问题
问题 有n 项任务,每项任务加工时间已知.
从0时刻开始陆续安排到一台机器上加工.
每个任务的完成时间是从0 时刻到任务加工
截止的时间.
求: 总完成时间(所有任务完成时间之和)
最短的安排方案.
实例
任务集 S = {1, 2, 3, 4, 5},
加工时间: t =3, t =8, t =5, t =10, t =15
1 2 3 4 5
2
贪心法的解
算法:按加工时间(3,8,5,10,15) 从小到大安排
解:1, 3, 2, 4, 5
3 5 8 10 15
0 3 8 16 26 41
总完成时间:
t = 3+(3+5)+(3+5+8)+(3+5+8+10)+(3+5+8+10+15)
= 3×5 + 5×4 + 8×3 + 10×2 + 15
= 94
3
问题建模
输入: 任务集:S= {1, 2, … , n},
+
第j 项任务加工时间: t ∈Z , j =1,2,…,n.
j
输出:调度I ,S 的排列 i , i , …, i ,
1 2 n
n
目标函数:I 的完成时间,t (I ) ∑(n −k +1)tik
k 1
解I *:使得 t(I*) 达到最小,即
t(I * ) min{ t(I )|I 为S 的排列}
4
贪心算法
设计策略:加工时间短的先做
算法:根据加工时间从小到大排序,依次加工
算法正确性:对所有输入实例都得到最优解
证:假如调度f 第i, j 项任务相邻且有逆序,
即t t . 交换任务i 和j 得到调度g ,
i j
f t t
i j
g t t
j i
总完成时间 t(g) −t(f ) = t −t 0
j i
您可能关注的文档
- (2017.3.1)预防诺如病毒PPT课件.ppt
- (上课用)我敬佩的一个人_写作指导课教案.doc
- (中学)班主任基本功大赛面试参考题目.docx
- 01118.1-电功、电能习题及答案.doc
- 05-新修订药品GMP中药饮片附录解读-李亚武.ppt
- 05第四章 叶蛋白.pdf
- 06 UPS计算和配置方法.pdf
- 07航天概论.doc
- 07递归.pptx
- 1 归类总规则讲解.docx
- AN024_星历原始观测数据协议.pdf
- APM32F051x6x8数据操作说明 V1.6中文.pdf
- AN1086_APM32F4xx_ISP应用笔记中文.pdf
- APM32F051R8 EVAL Board使用调试操作说明V1.0中文.pdf
- APM32F4xxx用户操作说明 V2.2中文.pdf
- APM32F411xCxE 数据操作说明 V1.3中文.pdf
- AN019_NMEA0183协议说明_北云科技.pdf
- AGP21系列电容式薄膜真空规说明书 A1-20240628.pdf
- AHT40温湿度传感器说明书中文版 A1-202406.pdf
- AN1096_APM32F035_HvMOTOR EVAL无感矢量控制方案_V1.1中文.pdf
文档评论(0)