简单的贪心算法ppt.ppt

《简单的贪心算法ppt.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、贪心算法详解与应用举例班级：软件12-1组长：孟洁组员：王明桃赵强8/25/20211※详解：算法思想算法过程算法分析※应用举例：常见应用8/25/20212ﻻ算法思想找钱的方法：25+25+10+5+1+1我们有种直觉的倾向：在找零钱时，直觉告诉我们使用面值大的硬币，剩余的金额就越少。假设提供了数目不限的面值为25美分、10美分、5美分、及1美分的硬币。假设一个小孩买了33美分的糖果（需要找给小孩67美分）。引例——找零钱8/25/20213ﻻ算法思想在现实生活中，我们经常为下意识的

2、做贪心的选择，例如在购买商品时候总是寻求物美价廉的物品，在质量相同情况下，价格低的首选。8/25/20214ﻻ算法思想将问题的求解过程看作是一系列选择，每次选择一个输入，每次选择都是当前状态下的最好选择(局部最优解)。每作一次选择后，所求问题会简化为一个规模更小的子问题。从而通过每一步的最优解逐步达到整体的最优解。8/25/20215ﻻ算法过程顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。找的硬币总数最少→使剩余金额最

3、少找硬币的时候：【标准转化】贪心猜想（贪心策略）原现8/25/20216ﻻ算法过程[贪心算法步骤]从问题的某一初始解出发；while能朝给定总目标前进一步do求出可行解的一个解元素；由所有解元素组合成问题的一个可行解；真正意义要求解原问题将原问题变成更小子问题的步骤理解8/25/20217ﻻ算法过程【贪心算法一般步骤】1、设计数据找规律2、进行贪心猜想3、正确性证明（严格证明和一般证明）·严格证明：数学归纳和反证法·一般证明：列举反例4、程序实现}若无法证明，此证明可省8/25/20218ﻻ算法分析【

4、适用问题】具备贪心选择和最优子结构性质的最优化问题【常见应用】背包问题,最小生成树,最短路径,作业调度等等【算法优点】求解速度快,时间复杂性有较低的阶.【算法缺点】需证明是最优解.整体的最优解可通过一系列局部最优解达到.每次的选择可以依赖以前作出的选择,但不能依赖于后面的选择问题的整体最优解中包含着它子问题的最优解8/25/20219ﻻ常见应用1、活动安排问题【问题陈述】设有n个活动E={1,2,…,n}要使用同一资源,同一时间内只允许一个活动使用该资源.设活动i的起止时间区间[si,fi),如果选择

5、了活动i,则它在时间区间[si,fi)内占用该资源;若[si,fi)与[sJ,fJ)不相交,则称活动i与j是相容的.求解目标是在所给的活动集合中选出最大相容活动子集.【算法思路】将n个活动按结束时间非减序排列,依次考虑活动i,若i与已选择的活动相容,则添加此活动到相容活动子集.【例】设待安排的11个活动起止时间按结束时间的非减序排列事件编号1234567891011发生时刻130535688212结束时刻45678910111213148/25/202110ﻻ常见应用活动安排问题贪心算法：voidGr

6、eedySelector(intn,Types[],Typef[],boolA[]){A[1]=true;intj=1;for(inti=2;i<=n;i++){if(s[i]>=f[j]){A[i]=true;j=i;}elseA[i]=false;}}8/25/202111ﻻ常见应用2、多机调度问题多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。例如，设

7、7个独立作业{1,2,3,4,5,6,7}由3台机器M1，M2和M3加工处理。各作业所需时间为{2,14,4,16,6,5,3}。按算法greedy产生的作业调度如下图所示，所需的加工时间为17。采用最长处理时间作业优先的贪心选择策略可以设计出解多机调度问题的较好的近似算法。148/25/202112ﻻ常见应用3、排队问题在一个医院B超室，有n个人要做不同身体部位的B超，已知每个人需要处理的时间为ti，（0

8、排序，就是这n个人最佳排队方案。求部分和的和即为所求。8/25/202113谈谈自己的想法——8/25/202114选择需慎重贪心算法在对问题求解时，总是作出在当前看来是最好的选择。也就是说，不从整体上加以考虑，它所作出的仅仅是在某种意义上的局部最优解。eg：数字三角形问题：有一个数字三角形（如下图）。现有一只蚂蚁从顶层开始向下走，每走下一级时，可向左下方向或右下方向走。求走到底层后它所经过的数的最大值。解：如果用贪心法，每次向最大的方向走，得到结果为1