第2章-贪心法课件

第第2章章 贪心法贪心法目录目录概述概述会场安排问题会场安排问题单源最短路径问题单源最短路径问题哈夫曼编码哈夫曼编码最小生成树最小生成树第第2章章 贪心法贪心法n贪心算法总是作出在当前看来最好的选择v并不从整体最优考虑v局部最优选择n不能对所有问题都得到整体最优解v对许多问题它能产生整体最优解v不能得到整体最优解，有时也是近似最优解。偷金块问题n所有的金块大小一样，成色不一样n背包的容积有限n怎样偷，最划算？n假设有四种硬币，它们的面值分别为：2角5分，1角，5分，1分。现在要找给顾客6角3分。怎样找使得给顾客的硬币最少。找硬币问题找硬币问题要找给顾客1角5分，硬币的面值分别为：1角1分，5分和1分。n贪心算法：一个1角1分和四个1分n最优解：三个5分n不是对所有问题都能得到整体最优解贪心法的基本思想贪心法的基本思想n基本思想基本思想v在每一个阶段都根据贪心策略来做出当前最优在每一个阶段都根据贪心策略来做出当前最优的决策，逐步降低问题的规模（难度），逐渐的决策，逐步降低问题的规模（难度），逐渐逼近目标。逼近目标。n得出的结论得出的结论v每次面临选择时每次面临选择时,都采用对眼前最有利的选择都采用对眼前最有利的选择 v选择一旦做出不可更改选择一旦做出不可更改v根据贪心策略来逐步构造问题的解根据贪心策略来逐步构造问题的解 贪心法的基本要素贪心法的基本要素n最优子结构性质最优子结构性质v当一个问题的最优解一定包含其子问题的最优解时当一个问题的最优解一定包含其子问题的最优解时 v采用反证法证明采用反证法证明n贪心选择性质贪心选择性质v所求问题的整体最优解可以通过一系列局部最优的选所求问题的整体最优解可以通过一系列局部最优的选择获得，即通过一系列的逐步局部最优选择使得最终择获得，即通过一系列的逐步局部最优选择使得最终的选择方案是全局最优的的选择方案是全局最优的 贪心法的解题步骤贪心法的解题步骤n分解分解：将原问题分解为若干个相互独：将原问题分解为若干个相互独立的阶段。立的阶段。n解决解决：对于每个阶段依据贪心策略进：对于每个阶段依据贪心策略进行贪心选择，求出局部的最优解。行贪心选择，求出局部的最优解。n合并合并：将各个阶段的解合并为原问题：将各个阶段的解合并为原问题的一个可行解。的一个可行解。会场安排问题会场安排问题n设有n个会议的集合C=1,2,n，其中每个会议都要求使用同一个资源（如会议室），而在同一时间内只能有一个会议使用该资源。每个会议i都有要求使用该资源的起始时间bi和结束时间ei，且bi ei。n在所给的会议集合中选出最大的活动子集，互相不冲突。会场安排问题会场安排问题n选择选择最早开始时间最早开始时间且不与已安排会议重叠的且不与已安排会议重叠的会议会议n选择选择使用时间最短使用时间最短且不与已安排会议重叠的且不与已安排会议重叠的会议会议n选择具有选择具有最早结束时间最早结束时间且不与已安排会议重且不与已安排会议重叠的会议叠的会议 设有设有11个会议等待安排，个会议等待安排，11个会议按结束时间的非减序排列表：个会议按结束时间的非减序排列表：会议集合为会议集合为1,4,8,11 会场安排问题会场安排问题n步骤步骤1：初始化。：初始化。n步骤步骤2：根据贪心策略，：根据贪心策略，A1=true；n步骤步骤3：找到下一个与前面不冲突的会议；：找到下一个与前面不冲突的会议；会场安排问题会场安排问题Void GreedySelector(int n,struct time b,struct time e,bool A)/起始时间起始时间bi，结束时间，结束时间ei /e中元素按非递减序排列，中元素按非递减序排列，b中对应元素做相应调整中对应元素做相应调整;int I,j;A1=true;/初始化选择会议的集合初始化选择会议的集合A，只包含会议，只包含会议1；j=1;i=2;/从第二从第二(i)个会议开始寻找与会议个会议开始寻找与会议1(j)相容的会议；相容的会议；while(i=ej)Ai=true;j=I;else Ai=false;会场安排问题会场安排问题时间复杂度：O(nlogn)空间复杂度：O(1)n问题存在从贪心选择开始的最优解问题存在从贪心选择开始的最优解v贪心选择性质贪心选择性质n一步一步的贪心选择能够得到问题的最优解一步一步的贪心选择能够得到问题的最优解v最优子结构性质最优子结构性质采用反证法采用反证法会场安排问题会场安排问题n使用贪心算法并不能保证最终的解就是最优解，但是对会场安排问题，该贪心算法却总能求得问题的最优解。n证明贪心选择性质v采用归纳法n证明最优子结构性质v采用反证法会场安排问题会场安排问题单源最短路径问题单源最短路径问题 n给定一个有向带权图给定一个有向带权图 G=(V，E)，其中每，其中每条边的权是一个非负实数。条边的权是一个非负实数。n给定给定V中的一个顶点，称为源点。中的一个顶点，称为源点。n现在要计算从源点到所有其它各个顶点的现在要计算从源点到所有其它各个顶点的最短路径长度。最短路径长度。如下的有向带权图中，求源点0到其余顶点的最短路径及最短路径长度。单源最短路径问题单源最短路径问题 单源最短路径问题单源最短路径问题 n按各个顶点与源点之间路径长度的按各个顶点与源点之间路径长度的递增递增次序，次序，生成源点到各个顶点的最短路径的方法，生成源点到各个顶点的最短路径的方法，即先求出长度最短的一条路径，再参照它即先求出长度最短的一条路径，再参照它求出长度次短的一条路径，依此类推，直求出长度次短的一条路径，依此类推，直到从源点到其它各个顶点的最短路径全部到从源点到其它各个顶点的最短路径全部求出为止。求出为止。单源最短路径问题单源最短路径问题 nu:源点。集合源点。集合S中的顶点到源点的最短路径中的顶点到源点的最短路径的长度已经确定，集合的长度已经确定，集合V-S中所包含的顶点中所包含的顶点到源点的最短路径的长度待定。到源点的最短路径的长度待定。n特殊路径：从源点出发只经过特殊路径：从源点出发只经过S中的点到达中的点到达V-S中的点的路径。中的点的路径。n贪心策略：选择特殊路径长度最短的路径，贪心策略：选择特殊路径长度最短的路径，将其相连的将其相连的V-S中的顶点加入到集合中的顶点加入到集合S中。中。单源最短路径问题单源最短路径问题 前驱数组P变化情况源点0到顶点4的最短路径为：0，1，3，4；源点0到顶点3的最短路径为：0，1，3；源点0到顶点2的最短路径为：0，1，2；源点0到顶点1的最短路径为：0，1。顶点迭代单源最短路径问题单源最短路径问题 void dijkstra(int n,int u,float dist,int p,int cnn)bool sn;/如果如果si等于等于true，说明顶点，说明顶点i已经加入集合已经加入集合s；/否则，顶点否则，顶点i属于集合属于集合v-s for(int i=1;i=n;i+)disti=cui;si=false;/初始化源点初始化源点u到其他各个顶点的最短路径长度到其他各个顶点的最短路径长度 if(disti=Float.Max_Value)pi=-1 /说明顶点说明顶点i与源点与源点u不相邻不相邻 else pi=u;/说明顶点说明顶点i与源点与源点u相邻相邻 distu=0;su=true;/初始时，集合初始时，集合s中只有源点中只有源点u 见下页。见下页。单源最短路径问题单源最短路径问题 单源最短路径问题单源最短路径问题 for(int i=1;i=n;i+)float temp=Float.Max_Value;int t=u;for(int j=1;j=n;j+)/在集合在集合v-s中寻找距离源点中寻找距离源点u最近的顶点最近的顶点tif(!s j)&(dist jtemp)t=j;temp=dist j;if(t=u)break;/找不到找不到t，跳出循环，跳出循环st=true;/否则，将否则，将t加入集合加入集合sfor(int j=1;j=n;j+)/更新与更新与t相邻接的顶点到源点相邻接的顶点到源点u的距离的距离if(!s j)&(ct j(distt+ct j)dist j=distt+ct j;p j=t;n时间复杂性为时间复杂性为O(n2)n实现该算法所需的辅助空间包含为数组实现该算法所需的辅助空间包含为数组s和和变量变量i、j、t和和temp所分配的空间所分配的空间v空间复杂性为空间复杂性为O(n)n算法证明：证明贪心选择性质和最优子结构算法证明：证明贪心选择性质和最优子结构性质性质单源最短路径问题单源最短路径问题 哈夫曼编码哈夫曼编码n已知某系统在通信联络中只可能出现已知某系统在通信联络中只可能出现8种字种字符，分别为符，分别为a，b，c，d，e，f，g，h，其使用频率分别为其使用频率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试，试设计编码。设计编码。n 不等长编码方法：不等长编码方法：v任何一个字符的编码都不能是其它字符编码的前任何一个字符的编码都不能是其它字符编码的前缀（即缀（即前缀码特性前缀码特性），否则译码时将产生二义性。），否则译码时将产生二义性。v约定在二叉树中用叶子结点表示字符，从根结点约定在二叉树中用叶子结点表示字符，从根结点到叶子结点的路径中，左分支表示到叶子结点的路径中，左分支表示“0”，右分支，右分支表示表示“1”。那么，从根结点到叶子结点的路径分。那么，从根结点到叶子结点的路径分支所组成的字符串做为该叶子结点字符的编码，支所组成的字符串做为该叶子结点字符的编码，二叉树即为编码树二叉树即为编码树。哈夫曼编码哈夫曼编码 n每个字符作为一棵树，放到森林中。每个字符作为一棵树，放到森林中。n每次从树的集合中每次从树的集合中权值最小权值最小的两棵树作为左、的两棵树作为左、右子树，构造一棵新树，新树根结点的权值右子树，构造一棵新树，新树根结点的权值为其左右孩子结点权之和，将新树插入到树为其左右孩子结点权之和，将新树插入到树的集合中。的集合中。哈夫曼编码哈夫曼编码 n步骤步骤1：确定合适的数据结构。：确定合适的数据结构。n步骤步骤2：初始化。构造：初始化。构造n棵结点为棵结点为n个字符的单结点树集合个字符的单结点树集合F=T1，T2,Tn，每棵树中只有一个带权的根结，每棵树中只有一个带权的根结点，权值为该字符的使用频率；点，权值为该字符的使用频率；n步骤步骤3：如果：如果F中只剩下一棵树，则哈夫曼树构造成功，中只剩下一棵树，则哈夫曼树构造成功，转步骤转步骤6；否则，从集合；否则，从集合F中取出双亲为中取出双亲为0且权值最小的两且权值最小的两棵树棵树Ti和和Tj，将它们合并成一棵新树，将它们合并成一棵新树Zk，新树以，新树以Ti为左为左儿子，儿子，Tj为右儿子（反之也可以）。新树为右儿子（反之也可以）。新树Zk的根结点的的根结点的权值为权值为Ti与与Tj的权值之和；的权值之和；n步骤步骤4：从集合：从集合F中删去中删去Ti、Tj，加入，加入Zk；n步骤步骤5：重复步骤：重复步骤3和和4；n步骤步骤6：从叶子结点到根结点逆向求出每个字符的哈夫曼：从叶子结点到根结点逆向求出每个字符的哈夫曼编码（约定左分支表示字符编码（约定左分支表示字符“0”，右分支表示字符，右分支表示字符“1”）。）。则从根结点到叶子结点路径上的分支字符组成的字符串即则从根结点到叶子结点路径上的分支字符组成的字符串即为叶子字符的哈夫曼编码。算法结束。为叶子字符的哈夫曼编码。算法结束。哈夫曼编码哈夫曼编码 哈夫曼编码哈夫曼编码n设权设权w=(5，29，7，8，14，23，3，11)，n=8，按哈夫曼算法的设计步骤构，按哈夫曼算法的设计步骤构造一棵哈夫曼编码树，具体过程如下：造一棵哈夫曼编码树，具体过程如下：（1）（2）（3）（4）哈夫曼编码哈夫曼编码（5）（6）（7）哈夫曼编码哈夫曼编码（8）哈夫曼编码哈夫曼编码 n哈夫曼树中结点的存储结构struct HtNode double weight;int parent,lchild,rchild;n哈夫曼树的存储结构Struct HtTree struct HtNode htMaxNode;int root;Typedef struct HtTree*PHtTree;哈夫曼编码哈夫曼编码 PHtTree Huffman(int n,double wn)PHtTree pht;int I,j,p1,p2;double min1,min2;if(nht=(struct HtNode*)malloc();for(i=0;ihti.parent=0;if(ihti.weight=wi;else pht-hti.weight=-1;哈夫曼编码哈夫曼编码.for(i=0;in-1;i+)/执行n-1次合并操作，构造哈夫曼树中的n-1个内部结点 p1=p2=0;min1=min2=max.value;for(j=0;jhtj.parent=0)if(pht-htj.weighthtj.weight;p2=p1;p1=j;else if(pht-htj.weighthtj.weight;p2=j;pht-htp1.parent=n+I;/将htp1和htp2合并，其双亲是n+i pht-htp2.parent=n+I;pht-htn+i.weight=min1+min2;pht-htn+i.lchild=p1;pht-htn|i.rchild=p2;Return pht;哈夫曼编码哈夫曼编码 n从叶结点逆向求出每个字符的哈夫曼编码Void HuffmanCode(char*HC,int n,PHtTree pht)char cn;/每个字符的编码长度不超过n HC=(char*)malloc(n*sizeof(char*);/分配n个字符指针空间 cn-1=0;/第n-1个单元存储编码串的结束符 for(i=1;ihti.parent;f!=0;k=f,f=pht-htk.parent)/f指向k的父亲 if(pht-htf.lchild=k)c-start=0;else c-start=1;HCi=(char*)malloc(n-start)*sizeof(char);/为每个字符编码分配空间 strcpy(HCi,&cstart);/将结果拷贝到HCi中 哈夫曼编码哈夫曼编码 n证明哈夫曼算法的正确性v贪心选择性质v最优子结构性质哈夫曼编码哈夫曼编码 n采用线性结构实现的算法，其复杂性为采用线性结构实现的算法，其复杂性为O(n2)。n算法的改进：采用极小堆实现，其复杂性为算法的改进：采用极小堆实现，其复杂性为O(nlogn)。哈夫曼编码哈夫曼编码 最小生成树n设设G=(V,E)G=(V,E)是无向连通带权图。是无向连通带权图。E E中每条边中每条边(v,w)(v,w)的权为的权为cvwcvw。n生成树：如果生成树：如果G G的子图的子图GG是一棵包含是一棵包含G G的所有的所有顶点的树，则称顶点的树，则称GG为为G G的生成树。的生成树。n耗费：生成树上各边权的总和耗费：生成树上各边权的总和n最小生成树在最小生成树在G G的所有生成树中，耗费最小的的所有生成树中，耗费最小的生成树生成树最小生成树n最小生成树应用最小生成树应用v在设计通信网络时，用图的顶点表在设计通信网络时，用图的顶点表示城市，用边示城市，用边(v,w)(v,w)的权的权cvwcvw表表示建立城市示建立城市v v和城市和城市w w之间的通信线之间的通信线路所需的费用路所需的费用最小生成树：Prim算法nPrim算法算法v设设G=(V，E)是无向连通带权图，是无向连通带权图，V=1,2,n；设最小生成树；设最小生成树T=(U，TE)。v令令U=u0，TE=。v选取满足条件选取满足条件iU，jV-U，且边，且边(i，j)是是连接连接U和和V-U的所有边中的最短边，即该边的所有边中的最短边，即该边的权值最小。然后，将顶点的权值最小。然后，将顶点j加入集合加入集合U，边，边(i，j)加入集合加入集合TE。v继续上面的贪心选择一直进行到继续上面的贪心选择一直进行到U=V为止为止最小生成树：Prim算法n实现实现Prim算法的关键算法的关键vclosestj表示表示V-U中的顶点中的顶点j在集合在集合U中的最近中的最近邻接顶点邻接顶点vlowcostj表示表示V-U中的顶点中的顶点j到到U中的所有顶中的所有顶点的最短边的权值，即边点的最短边的权值，即边(j，closestj)的权值。的权值。n步骤步骤1：确定合适的数据结构。设置带权邻接矩阵：确定合适的数据结构。设置带权邻接矩阵Cnn，bool数组数组s，如果，如果si=true，说明顶点，说明顶点i已加入集合已加入集合U；设置两个数组；设置两个数组closest和和lowcost；n步骤步骤2：初始化。令集合：初始化。令集合U=u0，TE=，并初始化数，并初始化数组组closest、lowcost和和s；n步骤步骤3：在集合：在集合V-U中寻找使得中寻找使得lowcost具有最小值的顶点具有最小值的顶点t，t就是集合就是集合V-U中连接集合中连接集合U中的所有顶点中最近的邻接顶中的所有顶点中最近的邻接顶点；点；n步骤步骤4：将顶点：将顶点t加入集合加入集合U，边，边(t，closestt)加入集合加入集合TE；n步骤步骤5：如果集合：如果集合V=U，算法结束，否则，转步骤，算法结束，否则，转步骤6；n步骤步骤6：对集合：对集合V-U中的所有顶点中的所有顶点k，更新其，更新其lowcost和和closest，用下面的公式更新：，用下面的公式更新：if(Ctklowcostk)lowcostk=Ctk;closestk=t;，转步骤，转步骤3。最小生成树：Prim算法最小生成树：Prim算法n求下图的最小生成树n假定初始顶点为顶点1，即U=1；t：集合V-U中距离集合U最近的顶点。最小生成树：Prim算法（1）（2）（3）（4）（5）（6）n构造过程最小生成树：Prim算法Void Prim(int n,int u0,int cnn)bool sn;int closestn,I,j;double lowcostn;su0=true;/初始化 for(i=0;in;i+)if(i!=u0)lowcosti=cu0i;closesti=u0;si=false;见下页。最小生成树：Prim算法最小生成树：Prim算法for(i=0;in;i+)double temp=float.MaxValue;int t=u0;for(j=0;jn;j+)/找最小的lowcostj if(!sj&(lowcostjtemp)t=j;temp=lowcostj;if(t=u0)break;st=true;/将顶点t加入集合U for(j=0;jn;j+)/更新当前的lowcostj和closestj if(!sj&(ctjlowcostj)lowcostj=ctj;closestj=t;最小生成树：Prim算法n时间复杂度：时间复杂度：O(n2)n复杂性与图中的边数无关复杂性与图中的边数无关nPrim算法适合于求边稠密的网的最小生算法适合于求边稠密的网的最小生成树。成树。最小生成树：Kruskal算法n将所有的边按权从小到大排序。将所有的边按权从小到大排序。n只要只要T中的连通分支数目不为中的连通分支数目不为1，就做如下的，就做如下的贪心选择贪心选择：在边集在边集E中选取权值最小的边中选取权值最小的边(i，j)，v如果将边如果将边(i，j)加入集合加入集合TE中不产生回路（或环）中不产生回路（或环），则将边，则将边(i，j)加入边集加入边集TE中，中，v否则继续选择下一条最短边。否则继续选择下一条最短边。n直到直到T中所有顶点都在同一个连通分支上为中所有顶点都在同一个连通分支上为止。止。最小生成树：Kruskal算法n回路回路判断：判断：v如果所选择加入的边的起点和终点都如果所选择加入的边的起点和终点都在在T的集合里，那么就可以断定一定会的集合里，那么就可以断定一定会形成回路。形成回路。算法设计求解步骤n步骤步骤1：初始化。将图：初始化。将图G的边集的边集E中的所有边按权从小到大排中的所有边按权从小到大排序，边集序，边集TE=，把每个顶点都初始化为一个孤立的分支，把每个顶点都初始化为一个孤立的分支，即一个顶点对应一个集合；即一个顶点对应一个集合；n步骤步骤2：在：在E中寻找权值最小的边中寻找权值最小的边(i，j)；n步骤步骤3：如果顶点：如果顶点i和和j位于两个不同连通分支，则将边位于两个不同连通分支，则将边(i，j)加入边集加入边集TE，并执合并操作将两个连通分支进行合并；，并执合并操作将两个连通分支进行合并；n步骤步骤4：将边：将边(i，j)从集合从集合E中删去，即中删去，即E=E-(i，j)；n步骤步骤5：如果连通分支数目不为：如果连通分支数目不为1，转步骤，转步骤2；否则，算法结；否则，算法结束，生成最小生成树束，生成最小生成树T。构造实例图2-12所示n首先，将图的边集E中的所有边按权从小到大排序为：1(1，3)、2(4，6)、3(2，5)、4(3，6)、5(1，4)和(2，3)和(3，4)、6(1，2)和(3，5)和(5，6)。（1）（2）（3）（4）（5）算法描述边的结点信息存储结构：Struct edge double weight;int u,v;bian;Void Kruskal(int n,struct edge bian,double cnn)int nodesetn,count=1;bool flagn+1;if(n=1)return;for(int i=1;i=n;i+)nodeseti=I;flagi=false;for(int j=1;j=n;j+)biancount.u=I;biancount.v=j;biancount.weight=cij;count+;sort(bian+1,bian+count);算法描述Count=1;int edgeset=0,w=0;While(edgeset(n-1)if(!flagbiancount.u)&(flagbiancount.v)w+=biancount.weight;edgeset+;flagbiancount.u=true;nodesetbiancount.u=nodesetbiancount.v;else if(flagbiancount.u)&(!flagbiancount.v)w+=biancount.weight;edgeset+;flagbiancount.v=true;nodesetbiancount.v=nodesetbiancount.u;else if(!flagbiancount.u)&(!flagbiancount.v)w+=biancount.weight;edgeset+;flagbiancount.u=true;flagbiancount.v=true;nodesetbiancount.u=nodesetbiancount.v;else if(nodesetbiancount.u!=nodesetbiancount.v)w+=biancount.weight;edgeset+;int tmp=nodesetbiancount.v;for(int i=1;i=n;i+)if(nodeseti=tmp)nodeseti=nodesetbiancount.u;count+;/end-while/end-Kruskal算法描述及分析n从算法的基本思想和设计步骤可以看出，要实现从算法的基本思想和设计步骤可以看出，要实现Kruskal算算法必须解决以下两个关键问题：（法必须解决以下两个关键问题：（1）选取权值最小的边的）选取权值最小的边的同时，要判断加入该条边后树中是否出现回路；（同时，要判断加入该条边后树中是否出现回路；（2）不同）不同的连通分支如何进行合并。的连通分支如何进行合并。n为了便于解决这两大问题，必须了解每条边的信息。那么，为了便于解决这两大问题，必须了解每条边的信息。那么，在在Kruskal算法中所设计的每条边的结点信息存储结构如下：算法中所设计的每条边的结点信息存储结构如下：nstruct edgendouble weight;/边的权值边的权值nint u，v;/u为边的起点，为边的起点，v为边的终点。为边的终点。nbian;nsort函数耗时最大，为此算法的时间复杂性为函数耗时最大，为此算法的时间复杂性为O(eloge)。Prim和Kruskal算法的比较n如果图如果图G中的边数较小时，可以采用中的边数较小时，可以采用KruskalnKruskal适用于稀疏图，而适用于稀疏图，而Prim适用于稠适用于稠密图。密图。nPrim算法的时间复杂度为算法的时间复杂度为O(n2)nKruskal算法的时间复杂度为算法的时间复杂度为O(eloge)n对于很大的图而言，对于很大的图而言，Kruskal算法需要占用算法需要占用比比Prim算法大得多的空间。算法大得多的空间。贪心总结算法n贪心算法是一个简单而高效的算法n可以用贪心算法求解的问题必须满足两个性质：贪心选择性质和最优子结构性质n贪心算法的时间复杂度大多数情况是排序的复杂度作业nP60 2-4、2-5END