简单的贪心算法课件.ppt

1、2023-1-221贪心算法简谈与应用举例贪心算法简谈与应用举例组员：组员：学院：通信与信息工程学院：通信与信息工程2023-1-222简谈：简谈：算法思想算法思想算法过程算法过程算法分析算法分析应用举例：应用举例：常见应用常见应用2023-1-223?算法思想算法思想找钱的方法找钱的方法：25+25+10+5+1+1我们有种直觉的倾向我们有种直觉的倾向：在找零钱时，直觉告诉我们使用面值大的硬币，剩余的金额就越少，这样找的硬币数目最少。假设提供了数假设提供了数目不限的面值为目不限的面值为2 2 5 5美分、美分、1 01 0美分、美分、5 5美分、及美分、及1 1美分美分的硬币。的硬币。假设一

2、个小孩买了3333美分的糖果（需要找给小孩6767美分）。引例引例找零钱找零钱2023-1-224?算法思想算法思想 在现实生活中，我们经常为下意在现实生活中，我们经常为下意识的做贪心的选择，例如在购买商品识的做贪心的选择，例如在购买商品时候总是寻求物美价廉的物品，在质时候总是寻求物美价廉的物品，在质量相同情况下，价格低的首选。量相同情况下，价格低的首选。贪心贪心抱歉我找不到更好的词去形抱歉我找不到更好的词去形容容是个好东西。贪心是对的，贪是个好东西。贪心是对的，贪心是奏效的。心是奏效的。电影电影华尔街华尔街2023-1-225?算法思想算法思想 将问题的求解过程看作是一系列选择，每次选择一个

3、输入，每次选择都是当前状态下的最好选择(局部最优解)。每作一次选择后，所求问题会简化为一个规模更小的子问题。从而通过每一步的最优解逐步达到整体的最优解。2023-1-226?算法过程算法过程 顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。找的硬币总数最少找的硬币总数最少使剩余金额最少使剩余金额最少找硬币的时候：找硬币的时候：【标准转化】贪心猜想（贪心策略）贪心猜想（贪心策略）原现2023-1-227?算法过程算法过程 贪心算法步骤 从问题的某一初始解出发；从问题的某一初始解出发；whilewhile 能朝给定总

4、目标前进一步能朝给定总目标前进一步dodo 求出可行解的一个解元素；求出可行解的一个解元素；由所有解元素组合成问题的一个由所有解元素组合成问题的一个可行解；可行解；真正意义要求解原问题真正意义要求解原问题将原问题变成更小将原问题变成更小子问题的步骤子问题的步骤理解理解2023-1-228?算法过程算法过程【贪心算法一般步骤】1 1、设计数据找规律、设计数据找规律2 2、进行贪心猜想、进行贪心猜想3 3、正确性证明（严格证明和一般证明）、正确性证明（严格证明和一般证明）严格证明：数学归纳和反证法严格证明：数学归纳和反证法 一般证明：列举反例一般证明：列举反例4 4、程序实现、程序实现2023-1

5、-229?算法分析算法分析【适用问题】具备贪心选择贪心选择和最优子结构最优子结构性质的最优化问题【常见应用】会议安排问题,哈夫曼编码问题,等等【算法优点】求解速度快,时间复杂性有较低的阶.【算法缺点】需证明是最优解.整体的最优解可通过一系列整体的最优解可通过一系列局部最优解达到局部最优解达到.每次的选择每次的选择可以依赖以前作出的选择可以依赖以前作出的选择,但但不能依赖于后面的选择不能依赖于后面的选择问题的整体最优解问题的整体最优解中包含着它子问题中包含着它子问题的最优解的最优解2023-1-2210?常见应用常见应用1、会议安排问题、会议安排问题【问题陈述】设有【问题陈述】设有n个会议个会议

6、E=1,2,n要使用同一资源要使用同一资源,同一时间内同一时间内只允许一个会议使用该资源只允许一个会议使用该资源.设会议设会议i的起止时间区间的起止时间区间si,fi),如果选如果选择了会议择了会议i,则它在时间区间则它在时间区间si,fi)内占用该资源内占用该资源;若若si,fi)与与sj,fj)不不相交相交,则称会议则称会议 i 与与 j 是是 相容相容 的的.求解目标是在所给的会议集合中求解目标是在所给的会议集合中选出最大相容会议子集选出最大相容会议子集.【算法思路】将【算法思路】将n个会议按结束时间非减序排列个会议按结束时间非减序排列,依次考虑会议依次考虑会议i,若若i与已选择的会议相

7、容与已选择的会议相容,则添加此会议到相容会议子集则添加此会议到相容会议子集.【例】设待安排的【例】设待安排的11个会议起止时间按结束时间的非减序排列个会议起止时间按结束时间的非减序排列事件编号12 3 4567891011发生时刻13 0 535688212结束时刻45 6 78910111213142023-1-2211?常见应用常见应用会议安排问题贪心算法：会议安排问题贪心算法：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;2

8、023-1-22122023-1-2212?常见应用常见应用2、哈夫曼编码、哈夫曼编码【问题陈述】【问题陈述】哈夫曼编码是广泛地用于数据文件压缩的十分有效的哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在编码方法。其压缩率通常在20%90%之间。哈夫曼编码算法用字之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表串表示各字符的最优表示方式。示方式。【算法思路】【算法思路】（1）以）以n个字母为结点构成个字母为结点构成n棵仅含一个点的二叉树集合，字母的棵仅含一个点的二叉树集合，字母的频率即为结点的权。频率即

9、为结点的权。（2）每次从二叉树集合中找出两个权最小者合并为一棵二叉树：）每次从二叉树集合中找出两个权最小者合并为一棵二叉树：增加一个根结点将这两棵树作为左右子树。新树的权为两棵子树的增加一个根结点将这两棵树作为左右子树。新树的权为两棵子树的权之和。权之和。（3）反复进行步骤）反复进行步骤（2）直到只剩一棵树为止。直到只剩一棵树为止。a:0000 b:11c:1000 d:1001e:101 f:01g:0001 h:001有八种字符：有八种字符：a b c d e f g h，其在通信联络中出现的概率分别为：，其在通信联络中出现的概率分别为：0.05 0.29 0.07 0.08 0.14 0

10、.23 0.03 0.11,试设计哈夫曼编码。试设计哈夫曼编码。设权设权 w=(5,29,7,8,14,23,3,11)n=8 构造过程：构造过程：529781423311538297814231178152923111411191429234229581000000000111111129232914232023-1-2214谈谈自己的谈谈自己的想法想法2023-1-2215 选择需慎重 贪心算法在对问题求解时，总是作出在当前看来是最好的选择。也就是说，不从整体上加以考虑，它所作出的仅仅是在某种意义上的局部最优解。eg：数字三角形问题：有一个数字三角形（如右图）。现有一只蚂蚁从顶层开始向下走

11、，每走下一级时，可向左下方向或右下方向走。求走到底层后它所经 过的数的最大值。解：如果用贪心法，每次向最大的方向 走，得到结果为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 62023-1-2216综述 贪心算法是一种分级处理方法，它得到某种度量意义下一个问题的最优解，所做的每一次选择都是当前状态下的贪心选择，通过一系列的选择来得到最终解。这种策略是一种很简洁的方法，适用于许多问题，但并不能依赖于它，因为它还有一下不足：（1）不能保证求得的最后解是最佳的，由于贪心策略总 是从局部看来是最优的选择，因此从整体上考虑并不一定是最优解；（2）贪心算法只能用来求某些最大或最小解的问题；（3）贪心算法只能确定某些问题的可行性范围。因此，贪心算法具有局限性，并不是总能得到最优解。2023-1-2217欢迎老师和同学们批评指正！谢谢观看 选择=结果汇报结束 谢谢观看！欢迎提出您的宝贵意见！