贪心算法

贪心算法顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。活动安排问题设有n个活动的集合s={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。si,fi分别为活动i的开始时间和结束时间，活动i和j相容当且仅当si=fj或者sj=fi怎样对这n个活动进行安排才能令最多的活动可以使用资源？活动安排问题也就是要在所给的活动集合中选出最大的相容活动子集合思路：按照结束时间递增序列将活动排序，使得f1=f2=…=fn满足相容关系后，按照标号从小到大选择活动注意：排序，贪心选择活动安排问题的贪心策略：使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。templateclassTypevoidGreedySelector(intn,Types[],Typef[],boolA[]){A[1]=true;intj=1;for(inti=2;i=n;i++){if(s[i]=f[j]){A[i]=true;j=i;}elseA[i]=false;}}各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列活动安排问题的贪心算法算法GreedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法GreedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。贪心算法的基本要素最优子结构性质贪心选择性质最优子结构性质一个问题的最优解包含了它子问题的最优解。举例：你从北京经过广州到海南的最短距离，肯定包括北京到广州的最短距离，以及广州到海南的最短距离贪心选择性质所求问题的最优解，可以通过一系列的局部最优解的选择，即贪心选择得到在当前状态下做出局部最优，然后解这个选择时候产生的子问题从全局看来，运用贪心策略解决的问题在程序的运行过程中无回溯过程0-1背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。背包问题：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。这2类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。用贪心算法解背包问题的基本步骤首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);inti;for(i=1;i=n;i++)x[i]=0;floatc=M;for(i=1;i=n;i++){if(w[i]c)break;x[i]=1;c-=w[i];}if(i=n)x[i]=c/w[i];}算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为O（nlogn）。为了证明算法的正确性，还必须证明背包问题具有贪心选择性质。对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。特殊的0-1背包问题在0-1背包问题中，若各物品依重量递增序排列时，其价值恰好依递减序排列，对这个特殊的0-1背包问题，设计一个有效的算法找出最优解。对于0－1背包问题本来是无法用贪心算法得到最优解的，但对于这类特殊的0－1背包问题，则可以用贪心算法去解。首先将各物品依重量递增序（即也是价值递减序）排列，然后依照价值递减顺序选择物品装入背包，直到背包装不下下一件物品为止。这里贪心算法的贪心选择策略是：每次总是选择价值最大（同时重量也最小）的物品，然后检查是否可以装入背包。最优装载有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。算法描述最优装载问题可用贪心算法求解贪心选择策略:重量最轻者先装可产生最优装载问题的最优解templateclassTypevoidLoading(intx[],Typew[],Typec,intn){int*t=newint[n+1];Sort(w,t,n);for(inti=1;i=n;i++)x[i]=0;for(inti=1;i=n&&w[t[i]]=c;i++){x[t[i]]=1;c-=w[t[i]];}}由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法loading的正确性。算法Loading的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为O(nlogn)。哈夫曼编码哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。abcdef频率(千次)4513121695定长码000001010011100101变长码010110011111011100前缀码对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。构造哈夫曼编码哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以|C|个叶结点开始，执行|C|－1次的“合并”运算后产生最终所要求的树T。选址问题给定n个小区之间的交通图。若小区i与小区j之间有路可通，则将顶点i与顶点j之间用边连接，边上的权值表示这条道路的长度。现在打算在这n个小区中选定一个小区建一所医院。试问这家医院应建在哪个小区，才能使距离医院最远的小区到医院的路程最短？请设计一个算法求解上述问题。单源最短路径给定带权有向图G=(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点v，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。单源最短路径1、算法基本思想Dijkstra算法是解决单源最短路径问题的贪心算法通过分步方法求出最短路径,每一步产生一个到达新的目的顶点的最短路径下一步所能达到的目的顶点通过如下贪婪准则选取：在还未产生最短路径的顶点中，选择路径长度最短的目的顶点单源最短路径初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10maxint301001{1,2}21060301002{1,2,4}4105030903{1,2,4,3}3105030604{1,2,4,3,5}510503060选址问题给定n个小区之间的交通图。若小区i与小区j之间有路可通，则将顶点i与顶点j之间用边连接，边上的权值表示这条道路的长度。现在打算在这n个小区中选定一个小区建一所医院。试问这家医院应建在哪个小区，才能使距离医院最远的小区到医院的路程最短？请设计一个算法求解上述问题。将n个小区的交通图视为一张带权无向图，并利用邻接矩阵来存放带权无向图。算法的思想是：①应用Dijkstra算法计算每对顶点之间的最短路径；②找出从每一个顶点到其它各顶点的最短路径中最长路径；③在这n条最长路径中找出最短的一条，则它的出发点即为所求。如何架设通信网络如下图G，图中的6个顶点为某乡的6个村，图G的边代表公路，现在要沿公路架设电线，使各村之间都通电话，问应该怎样架线，才能使所用的电线最少？最小生成树设G=(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)的权为c[v][w]。如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。Prim算法设G=(V,E)是连通带权图，V={1,2,…,n}。构造G的最小生成树的Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件iS，jV-S，且c[i][j]最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。例如，对于右图中的带权图，按Prim算法选取边的过程如下页图所示。Kruskal算法Kruskal算法构造G的最小生成树的基本思想是，首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。Kruskal算法从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：1、当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；2、如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。多机调度问题多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。这个问题是NP完全问题，到目前为止还没有有效的解法。对于这一类问题,用贪心选择策略有时可以设计出较好的近似算法。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。多机调度问题当n=m时，只要将机器i的[0,ti]时间区间分配给作业i即可，算法只需要O(1)时间。当nm时，设置合理的贪心策略求解例：假设有9个独立的作业{1，2，3，4，5，6，7，8，9}，由3台机器M1，M2，M3来加工处理。各作业所处理的时间T{t1，t2…，t9}={81，40，26，4，65，98，53，71，15}。贪心策略的设置1、将每个作业平均分给每台机器，即每个机器处理一样数量的作业此方法的优点是容易想到，相当简单，但没有充分利用机器的处理能力，只是按照任务的次序进行分配，当有比较大的任务集中分配给一台机器而其它任务较小时会造成其他机器等待，效率较低。2、把作业处理所需时间按照从小到大的顺序依次分给每台机器此方法也容易想到，实现起来也较简单，同时也考虑到了时间的安排，但处理时间最长的作业放在最后处理，