简单的贪心算法ppt.ppt

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