第2章 贪心法.ppt

《第2章 贪心法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章贪心法张阳信息工程学院第2章贪心法目录概述会场安排问题单源最短路径问题哈夫曼编码最小生成树第2章贪心法贪心算法总是作出在当前看来最好的选择并不从整体最优考虑局部最优选择不能对所有问题都得到整体最优解对许多问题它能产生整体最优解不能得到整体最优解，有时也是近似最优解。偷金块问题所有的金块大小一样，成色不一样背包的容积有限怎样偷，最划算？假设有四种硬币，它们的面值分别为：2角5分，1角，5分，1分。现在要找给顾客6角3分。怎样找使得给顾客的硬币最少。找硬币问题找硬币问题要找给顾客1角5分，硬币的面

2、值分别为：1角1分，5分和1分。贪心算法：一个1角1分和四个1分最优解：三个5分不是对所有问题都能得到整体最优解贪心法的基本思想基本思想在每一个阶段都根据贪心策略来做出当前最优的决策，逐步降低问题的规模（难度），逐渐逼近目标。得出的结论每次面临选择时,都采用对眼前最有利的选择选择一旦做出不可更改根据贪心策略来逐步构造问题的解贪心法的基本要素最优子结构性质当一个问题的最优解一定包含其子问题的最优解时采用反证法证明贪心选择性质所求问题的整体最优解可以通过一系列局部最优的选择获得，即通过一系列的逐步局部最

3、优选择使得最终的选择方案是全局最优的贪心法的解题步骤分解：将原问题分解为若干个相互独立的阶段。解决：对于每个阶段依据贪心策略进行贪心选择，求出局部的最优解。合并：将各个阶段的解合并为原问题的一个可行解。会场安排问题设有n个会议的集合C={1,2,…,n}，其中每个会议都要求使用同一个资源（如会议室），而在同一时间内只能有一个会议使用该资源。每个会议i都有要求使用该资源的起始时间bi和结束时间ei，且bi

4、会议重叠的会议选择使用时间最短且不与已安排会议重叠的会议选择具有最早结束时间且不与已安排会议重叠的会议设有11个会议等待安排，11个会议按结束时间的非减序排列表：会议i1234567891011开始时间bi130535688212结束时间ei4567891011121314会议集合为{1,4,8,11}会场安排问题步骤1：初始化。步骤2：根据贪心策略，A[1]=true；步骤3：找到下一个与前面不冲突的会议；会场安排问题VoidGreedySelector(intn,structtimeb[],st

5、ructtimee[],boolA[]){//起始时间bi，结束时间ei//e中元素按非递减序排列，b中对应元素做相应调整;intI,j;A[1]=true;//初始化选择会议的集合A，只包含会议1；j=1;i=2;//从第二(i)个会议开始寻找与会议1(j)相容的会议；while(i<=n)if(b[i]>=e[j]){A[i]=true;j=I;}elseA[i]=false;}会场安排问题时间复杂度：O(nlogn)空间复杂度：O(1)问题存在从贪心选择开始的最优解贪心选择性质一步一步的贪心选

6、择能够得到问题的最优解最优子结构性质采用反证法会场安排问题使用贪心算法并不能保证最终的解就是最优解，但是对会场安排问题，该贪心算法却总能求得问题的最优解。证明贪心选择性质采用归纳法证明最优子结构性质采用反证法会场安排问题单源最短路径问题给定一个有向带权图G=(V，E)，其中每条边的权是一个非负实数。给定V中的一个顶点，称为源点。现在要计算从源点到所有其它各个顶点的最短路径长度。如下的有向带权图中，求源点0到其余顶点的最短路径及最短路径长度。单源最短路径问题单源最短路径问题按各个顶点与源点之间路径长度

7、的递增次序，生成源点到各个顶点的最短路径的方法，即先求出长度最短的一条路径，再参照它求出长度次短的一条路径，依此类推，直到从源点到其它各个顶点的最短路径全部求出为止。单源最短路径问题u:源点。集合S中的顶点到源点的最短路径的长度已经确定，集合V-S中所包含的顶点到源点的最短路径的长度待定。特殊路径：从源点出发只经过S中的点到达V-S中的点的路径。贪心策略：选择特殊路径长度最短的路径，将其相连的V-S中的顶点加入到集合S中。单源最短路径问题SV-Sdist[1]dist[2]dist[3]dist[4

8、]t初始{0}{1,2,3,4}832maxmax11{0,1}{2,3,4}-2423max32{0,1,3}{2,4}-24-3023{0,1,3,2}{4}---3044{0,1,3,2,4}{}01234初始-100-1-11-1011-12-101133-101134-10113前驱数组P变化情况源点0到顶点4的最短路径为：0，1，3，4；源点0到顶点3的最短路径为：0，1，3；源点0到顶点2的最短路径为：0，1，2；源点0到顶点1的最短路径为：0，1。顶点