没有合适的资源？快使用搜索试试~ 我知道了~

文库首页课程资源C/C++中科大算法导论课件（全套10）贪心算法

中科大算法导论课件（全套10）贪心算法

算法导论

4星 · 超过85%的资源需积分: 0 29 下载量 146 浏览量 2011-05-09 15:41:07 上传评论收藏 1.63MB PDF 举报

温馨提示

试读

54页

中国科学技术大学算法导论课件计算机相关专业必修

资源推荐

资源详情

资源评论

University of Science and Technology of China

主讲人：庄连生

Email: { lszhuang@ustc.edu.cn }

Spring 2010

，

USTC

算法基础

University of Science and Technology of China

2010-5-19 2

第十讲贪心算法

内容提要：

 理解贪心算法的概念

 掌握贪心算法的基本要素

 理解贪心算法与动态规划算法的差异

 通过范例学习动态规划算法设计策略

University of Science and Technology of China

10.1 活动安排问题

2010-5-19 3

 当一个问题具有最优子结构性质时，可用动态规划法求解，但有

时用贪心算法求解会更加的简单有效。

 顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说

贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义

上的局部最优选择。当然，希望贪心算法得到的最终结果也是整

体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但

对许多问题它能产生整体最优解。如单源最短路经问题，最小生

成树问题等。在一些情况下，即使贪心算法不能得到整体最优解

，其最终结果却是最优解的很好近似。

University of Science and Technology of China

10.1 活动安排问题

2010-5-19 4

 设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一

资源，如演讲会场等，而在同一时间内只有一个活动能使用这一

资源。每个活动i都有一个要求使用该资源的起始时间s

和一个结

束时间f

,且s

。如果选择了活动i，则它在半开时间区间[s

, f

)

内占用资源。若区间[s

, f

)与区间[s

, f

)不相交，则称活动i与活动j

是相容的。也就是说，当s

≥f

或s

≥f

时，活动i与活动j相容。

 问题：选出最大的相容活动子集合。

University of Science and Technology of China

10.1 活动安排问题

2010-5-19 5

 （用动态规划方法）

 步骤1：分析最优解的结构特征

— 构造子问题空间:

={ a

∈S: f

≤s

}

包含了所有与a

和a

相兼容的活动，并且与不迟于a

结束和不早

于a

开始的活动兼容。此外，虚构活动a

和a

n+1

，其中f

=0,

n+1

=≦。原问题即为寻找S

0,n+1

中最大兼容活动子集。

剩余53页未读，继续阅读

评论收藏

内容反馈

资源评论

资源反馈

评论星级较低，若资源使用遇到问题可联系上传者，3个工作日内问题未解决可申请退款~

weien9606110

2012-09-15

全套9在哪里
Mars尘

2014-01-03

还行，不错的资源

hbhdytf

粉丝: 0
资源: 32

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

中科大 算法导论 课件（全套10）贪心算法

中科大算法导论

科大算法导论上课ppt完整版

中科大软件学院算法导论PPT

中科大 顾乃杰 算法导论课件

中科大算法导论期末复习

中科大 算法导论 课件（全套8）红黑树及其扩张

中科大 算法导论 课件（全套3）递归式

中科大算法导论期末试卷及答案

中科大算法导论期末考试试卷

中科大算法导论答案1-13次全部 中科大算法导论答案1-13次全部

中科大算法导论课件

中科大研究生算法导论课件

中科大软院算法导论课件及考试资料

中科大 算法导论 课件（全套11）回溯法

中科大算法导论第一二次和第四次作业答案PPT课件.pptx

中科大 算法导论 课件（全套12）分支限界法

中科大 算法导论 课件（全套1）

中科大 算法导论 课件（全套5）概率分析与随机算法

中科大 算法导论 课件（全套7）顺序统计学

中科大 算法导论 课件（全套4）递归和分治策略

中科大 算法导论 课件（全套2）函数的增长

中科大 算法导论 课件（全套6）排序

中科大 算法导论 课件（全套14）有关数轮的算法

中科大 算法导论 课件（全套13）随机化算法

MIT算法导论课件

中科大2015年算法导论课堂练习

最新scratch3.编程课件+源码.zip

数据挖掘导论（完整版）PPT.

linux 课件 linux全套学习资料

最新资源

中科大算法导论课件（全套10）贪心算法

中科大顾乃杰算法导论课件

中科大算法导论课件（全套8）红黑树及其扩张

中科大算法导论课件（全套3）递归式

中科大算法导论答案1-13次全部中科大算法导论答案1-13次全部

中科大算法导论课件（全套11）回溯法

中科大算法导论课件（全套12）分支限界法

中科大算法导论课件（全套1）

中科大算法导论课件（全套5）概率分析与随机算法

中科大算法导论课件（全套7）顺序统计学

中科大算法导论课件（全套4）递归和分治策略

中科大算法导论课件（全套2）函数的增长

中科大算法导论课件（全套6）排序

中科大算法导论课件（全套14）有关数轮的算法

中科大算法导论课件（全套13）随机化算法