简单的贪心算法ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,贪心算法详解与应用举例,班级：软件12-1,组长：孟洁,组员：王明桃 赵强,9/14/2024,1,详解：算法思想算法过程算法分析应用举例：常见应用,9/14/2024,2,算法思想,找钱的方法,：,25+25+10+5+1+1,我们,有种直觉的倾向,：,在找零钱时，直觉告诉我们,使用面值大的硬币，剩余的金额就越少。,假设提供了数目不限的面值为2 5美分、1 0美分、5美分、及1美分的硬币。,假设一个小孩买了33美分的糖果（需要找给小孩67美分）。,引例,找零钱,9/14/2024,3,算法思想,在现实生活中，我们经常为下意识的做贪心的选择，例如在购买商品时候总是寻求物美价廉的物品，在质量相同情况下，价格低的首选,。,9/14/2024,4,算法思想,将问题的求解过程看作是一系列选择,，,每次选择一个输入,，,每次选择都是当前状态下的,最好选择,(,局部最优解,),。,每作一次选择后,，,所求问题会简化为一个规模更小的子问题,。,从而通过每一步的最优解逐步达到整体的最优解,。,9/14/2024,5,算法过程,顾名思义，,贪心算法总是,作出在当前看来最好的选择,。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的,局部最优选择,。,找的硬币总数最少使剩余金额最少,找硬币的时候：,【标准转化】,贪心猜想（贪心策略）,原,现,9/14/2024,6,算法过程,贪心算法步骤,从问题的某一初始解出发；,while,能朝给定总目标前进一步,do,求出可行解的一个解元素；,由所有解元素组合成问题的一个可行解；,真正意义要求解原问题,将原问题变成更小子问题的步骤,理解,9/14/2024,7,算法过程,【贪心算法一般步骤】,1、设计数据找规律,2、进行贪心猜想,3、正确性证明（严格证明和一般证明）,严格证明：数学归纳和反证法,一般证明：列举反例,4、程序实现,若无法证明，此证明可省,9/14/2024,8,算法分析,【适用问题】 具备,贪心选择,和,最优子结构,性质的最优化问题,【常见应用】背包问题,最小生成树,最短路径,作业调度等等,【算法优点】求解速度快,时间复杂性有较低的阶.,【算法缺点】需证明是最优解.,整体的最优解可通过一系列局部最优解达到. 每次的选择可以依赖以前作出的选择, 但不能依赖于后面的选择,问题的整体最优解中包含着它子问题的最优解,9/14/2024,9,常见应用,1、活动安排问题,【,问题陈述,】,设有n个活动E=1,2,n要使用同一资源,同一时间内只允许一个活动使用该资源. 设活动i的起止时间区间si, fi) ,如果选择了活动i,则它在时间区间si, fi)内占用该资源;若,si, fi),与,sJ, fJ),不相交 , 则称活动 i 与 j 是 相容 的 . 求解目标是在所给的活动集合中选出最大相容活动子集.,【,算法思路,】,将n个活动按结束时间非减序排列,依次考虑活动i, 若i与已选择的活动相容,则添加此活动到相容活动子集.,【例】设待安排的11个活动起止时间按结束时间的非减序排列,事件编号,1,2,3,4,5,6,7,8,9,10,1,1,发生时刻,1,3,0,5,3,5,6,8,8,2,1,2,结束时刻,4,5,6,7,8,9,1,0,1,1,1,2,1,3,1,4,9/14/2024,10,常见应用,活动安排问题贪心算法：,void GreedySelector(int n, Type s, Type f, bool A),A1=true;,int j=1;,for (int i=2;i=fj,) Ai=true; j=i; ,else Ai=false;,9/14/2024,11,常见应用,2、多机调度问题,多机调度问题要求给出一种作业调度方案，使所给的,n,个作业在尽可能短的时间内由,m,台机器加工处理完成。,约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。,例如，设,7,个独立作业,1,2,3,4,5,6,7,由,3,台机器,M1,，,M2,和,M3,加工处理。各作业所需时间为,2,14,4,16,6,5,3,。按算法,greedy,产生的作业调度如下图所示，所需的加工时间为,17,。,采用,最长处理时间作业优先,的贪心选择策略可以设计出解多机调度问题的较好的近似算法。,14,9/14/2024,12,常见应用,3、排队问题,在一个医院B 超室，有n个人要做不同身体部位的B超，已知每个人需要处理的时间为ti，（0i=n）,请求出一种排列次序，使每个人排队等候时间总和最小。,本题贪心算法：,n个人时间从小到大排序，就是这n个人最佳排队方案。求部分和的和即为所求。,9/14/2024,13,谈谈自己的想法,9/14/2024,14,选择需慎重,贪心算法,在对问题求解时，总是作出在当前看来是最好的选择。也就是说，不从整体上加以考虑，它所作出的仅仅是在某种意义上的局部最优解。,eg：数字三角形问题：有一个数字三角形（如下图）。现有一只蚂蚁从顶层开始向下走，每走下一级时，可向左下方向或右下方向走。求走到底层后它所经 过的数的最大值。,解：,如果用贪心法，每次向最大的方向,走，得到结果为1+6+8+2+3=20。可是明明还有另一条路，1+3+6+6+7=23。,问题出在哪？每次的选择对后面的步骤会有影响！第三级选了8，就选不到第四、五级较大的数了。,1,6 3,8 2 6,2 1 6 5,3 2 4 7 6,9/14/2024,15,综述,贪心算法是一种分级处理方法，它得到某种度量意义下一个问题的最优解，所做的每一次选择都是当前状态下的贪心选择，通过一系列的选择来得到最终解。这种策略是一种很简洁的方法，适用于许多问题,，但并不能依赖于它，因为它还有一下不足：,（1）,不能保证求得的最后解是最佳的,，由于贪心策略总 是从局部看来是最优的选择，因此从整体上考虑并不一定是最优解；,（2）贪心算法,只能用来求某些最大或最小解的问题,；,（3）贪心算法,只能确定某些问题的可行性范围,。,因此，,贪心算法具有局限性，并不是总能得到最优解。,9/14/2024,16,谢谢观看！,9/14/2024,17,