贪心法的应用
摘要:课程实验报告课程名算法分析与设计班级实验日期学号实验成绩称姓名实验名实验5：贪心算法的应用称实1．理解贪心算法的概念；2．掌握贪心算法的基本思想。验目的及要求实操作系统：WindowsIDE：VisualC++验环境（1）活动安排问题设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该实验资源的起始时间si和一个结束时间fi，且si<fi。如果选择了活动i，则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交，则称活动i与活动j是相容的。随机生成n个任务（n=8,16,32…）,用贪心法求近似解，任 内选一种其它方法求最优解。做出图像，比较贪心法和你所选的另外一种方法的执行时间随n的变化曲线。比较计算结果，说明对该问题，贪心法是否一定会容得到最优解，如果是，请给出证明或者说明理由，如果不是，请根据实验结果说明理由。（2）线段覆盖问题描述：在一维空间中随机生成N（N=8,16,32…）条线段的起始坐标与终止坐标，要求求出这些线段一共覆盖了多大的长度（重叠区域只算一次）。分析算法的时间复杂度，画出算法的执行时间随N变化的曲线图。贪心算法初步：调试过程运行到一定规模：线段覆盖 我们容易验证贪心算法：在对问题求解时，总是做出在当前看来是最好的选择。总也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，结选择的贪心策略必须具备无后效性，即某个状态以前的过
温馨提示：当前文档最多只能预览
8 页，若文档总页数超出了
8 页，请下载原文档以浏览全部内容。
本文档由 匿名用户 于 2020-01-29 17:03:29上传分享
