【免费】lab-4-贪心算法实现最佳任务调度实验1_设计贪心算法实现作业调度,要求按作业调度顺序输出作业序列,使得该条件下的效率最资源-CSDN文库

需积分: 0 124 浏览量 2022-08-03 13:06:19 上传评论收藏 124KB PDF 举报

资源详情

资源评论

资源推荐

实验四贪心算法实现最佳任务调度实验

一、实验原理（详细请参考课本第 16 章）

1. 活动选择问题：

对几个互相竞争的活动进行调度，它们都要求以独占的方式使用某一公共资

源。而在同一时间内只有一个活动能使用这一资源。假设有一个需要使用某一资

源的 n 个活动组成的集合 S={a1,a2,a3,...,an}。每个活动 ai 都有一个要求使用该资

源的起始时间 si 和一个结束时间 fi,且 si <fi。如果选择了活动 i，则它在半开时间

区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交,则称活动 i 与活动 j 是兼

容的。

活动选择问题就是要选择出一个由互不兼容的问题组成的最大子集合。

2. 贪心策略

动态规划是贪心算法的基础。

贪心算法即通过做一系列的选择来给出某一问题的最优解。对算法中的每一

个决策点，做一个当时最佳的选择。

贪心算法的使用条件：贪心选择性质和最优子结构是两个关键的特点。如果

我们能够证明问题具有这些性质，那么就可以设计出它的一个贪心算法。

 贪心选择性质：一个全局最优解可以通过局部最优（贪心）选择来达到。

 最优子结构：对一个问题来说，如果它的一个最优解包含了其子问题的

最优解，则称该问题具有最优子结构。

贪心算法的基本思路：

 建立对问题精确描述的数学模型，包括定义最优解的模型；

 将问题分解为一系列子问题，同时定义子问题的最优解结构；

 应用贪心原则确定每个子问题的局部最优解，并根据最优解的模型，用

子问题的局部最优解堆叠出全局最优解。

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余1页未读，立即下载

评论0

内容反馈

VashtaNerada

粉丝: 18
资源: 297

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip