算法设计与分析Capture01-北航

VIP免费

2025-01-13 2 0 1.69MB 100 页 5.9玖币

侵权投诉

(一)

算法及时间复杂度

李东禹

北京航空航天大学

Special Acknowledgements to Prof. Wanling Qu’s group from Peking University

算法设计与分析

算法设计两个例子

2024-9-19

例1：调度问题

问题有n项任务，每项任务加工时间已知.

从0时刻开始陆续安排到一台机器上加工.

每个任务的完成时间是从0 时刻到任务加工

截止的时间.

求: 总完成时间（所有任务完成时间之和）最

短的安排方案.

实例

任务集 S = {1, 2, 3, 4, 5}，

加工时间: =3, =8, =5, =10, =15

算法设计两个例子

2024-9-19

贪心法的解

算法：按加工时间 (3,8,5,10,15) 从小到大安排

解：1，3，2，4，5

总完成时间：

t =3+(3+5)+(3+5+8)+(3+5+8+10)+(3+5+8+10+15)

= 3x5 + 5x4 + 8x3 + 10x2 + 15

= 94

算法设计两个例子

2024-9-19

问题建模

输入：任务集：S={1, 2, … , n}，

第j项任务加工时间: ∈ ，j=1,2,…,n.

输出：调度

，S的排列，， ，

目标函数：I的完成时间，

t(I)=

     

解 ：使得t()达到最小，即

t()=min{t(

为S的排列}

算法设计两个例子

2024-9-19

贪心算法

设计策略：加工时间短的先做

算法：根据加工时间从小到大排序,依次加工

算法正确性：对所有输入实例都得到最优解

证：假如调度f 第 i,j 项任务相邻且有逆序，

即 ti >tj . 交换任务 i 和j 得到调度 g，

总完成时间 t(g) − t(f ) = tj − ti < 0

算法设计两个例子

2024-9-19

直觉不一定是正确的

反例

有4 件物品要装入背包, 物品重量和价值如下:

背包重量限制是 6，问如何选择物品，使得不

超重的情况下装入背包的物品价值达到最大?

算法设计两个例子

2024-9-19

实例的解

贪心法：单位重量价值大的优先，总重不超 6

按照 







从大到小排序：1, 2, 3, 4

贪心法的解： { 1, 4 }，重量 5，价值为 9.

更好的解：{ 2, 4 }，重量 6，价值 11.

> >

算法设计两个例子

2024-9-19

算法设计

1. 问题建模

2. 选择什么算法？如何描述这个

方法？

3. 这个方法是否对所有实例都得

到最优解？如何证明？

4. 如果不是，能否找到反例？

算法设计两个例子

2024-9-19

例2：投资问题

问题：m元钱，投资 n 个项目. 效益函数fi (x)，

表示第 i 个项目投 x 元的效益， i =1, 2, …, n.

求如何分配每个项目的钱数使得总效益最大？

实例： 5 万元，投资给 4 个项目，效益函数：

算法设计两个例子

2024-9-19

建模

输入：n, m,fi(x), i =1,2, ..., n, x = 1,2, ..., m

解： n 维向量<x1, x2, … , xn>, xi 是第 i 个项

目的钱数，使得下述条件满足：

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

(一)算法及时间复杂度李东禹北京航空航天大学SpecialAcknowledgementstoProf.WanlingQu’sgroupfromPekingUniversity算法设计与分析2算法设计两个例子2024-9-19例1：调度问题问题有n项任务，每项任务加工时间已知.从0时刻开始陆续安排到一台机器上加工.每个任务的完成时间是从0时刻到任务加工截止的时间.求:总完成时间（所有任务完成时间之和）最短的安排方案.实例任务集S={1,2,3,4,5}，加工时间:t�=3,t� =8,t� =5,t� =10,t� =153算法设计两个例子2024-9-19贪心法的解算法：按加工时间(3,8,...

展开>> 收起<<

算法设计与分析Capture01-北航.pdf

共100页,预览20页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

算法设计与分析Capture01-北航

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: