《贪心算法.ppt.ppt》由会员分享，可在线阅读，更多相关《贪心算法.ppt.ppt（84页珍藏版）》请在三一办公上搜索。
1、贪心算法,顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。,贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。,活动安排问题,设有n个活动的集合s=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。si,fi分别为活动i的开始时间和结束时间，活动i和j相容当且仅当si=fj或者sj=fi,怎样对这n个活动进行安排才能令最多的活动
2、可以使用资源？,活动安排问题也就是要在所给的活动集合中选出最大的相容活动子集合,思路：按照结束时间递增序列将活动排序，使得f1=f2=fn满足相容关系后，按照标号从小到大选择活动注意：排序，贪心选择,活动安排问题的贪心策略：使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。,templatevoid 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;,各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列,活动安排问题的贪心
3、算法,算法GreedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。,贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法GreedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。,贪心算法的基本要素,最优子结构性质贪心选择性质,最优子结构性质,一个问题的最优解包含了它子问题的最优解。举例：你从北京经过广州到海南的最短距离，肯定包括北京到广州的最短距离，以及广州到海南的最短距离,贪心选择性质
4、,所求问题的最优解，可以通过一系列的局部最优解的选择，即贪心选择得到在当前状态下做出局部最优，然后解这个选择时候产生的子问题从全局看来，运用贪心策略解决的问题在程序的运行过程中无回溯过程,给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1in。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?,背包问题,用贪心算法解背包问题的基本步骤,首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未
5、超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。,void Knapsack(int n,float M,float v,float w,float x)Sort(n,v,w);int i;for(i=1;ic)break;xi=1;c-=wi;if(i=n)xi=c/wi;,算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为O（nlogn）。,0-1背包问题,给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最
6、大?,在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。,对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。,特殊的0-1背包问题,在0-1背包问题中，若各物品依重量递增序排列时，其价值恰好依递减序排列，对这个特殊的0-1背包问题，设计一个有效的算法找出最优解。,对于01背包问题本来是无法用贪心算法得到最优解的，但对于这类特殊的01背包问题，则可以用贪心算法去解。首先将各物品依重量递增序（即也是价值递减序）排列，然后依照价值递
7、减顺序选择物品装入背包，直到背包装不下下一件物品为止。这里贪心算法的贪心选择策略是：每次总是选择价值最大（同时重量也最小）的物品，然后检查是否可以装入背包。,最优装载,有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。,算法描述,最优装载问题可用贪心算法求解贪心选择策略:重量最轻者先装可产生最优装载问题的最优解,templatevoid Loading(int x,Type w,Type c,int n)int*t=new int n+1;Sort(w,t,n);for(int i=1;i=n;i+)x
8、i=0;for(int i=1;i=n,贪心选择性质,可以证明最优装载问题具有贪心选择性质。k=mini|xi=1 1=1,最优子结构性质,最优装载问题具有最优子结构性质。,算法Loading的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为 O(nlogn)。,贪心算法的基本步骤,从问题的某个初始解出发采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模将所有部分解综合起来，得到问题的最终解,旅行规划问题,G 先生想独自驾驶汽车从城市A 到城市B。从城市A 到城市B 的距离为d0 公里。汽车油箱的容量为c 公升。每公升汽油能行驶
9、e 公里。出发点每公升汽油的价格为p 元。从城市A到城市B 沿途有n 个加油站。第i 个加油站距出发点的距离为di，油价为每公升pi元。如何规划才能使旅行的费用最省。,编程任务：对于给定的d0,c,e,p,和n 以及n个加油站的距离和油价di 和pi，编程计算最小的旅行费用。如果无法到达目的地，输出“No Solution”。,Sample input275.6 11.9 27.4 2.8 2102.0 2.9220.0 2.2Sample output26.95ci0=220.0/27.4=8.029ci1=0 ci2=(275.6-220)/27.4=2.029Total=8.029*2.
10、8+2.029*2.2=26.95,第一步：判断旅行家能否到达目的地假设在任一个加油站都加满油，能否到达终点,第二步：预算最少费用采用贪心算法的思想求解,汽车在到达目的地之前的每一时刻，都必须保证油箱中的汽油足够行驶到下一油站。如果以p(i)表示第i油站的汽油价格，x(i)表示在第i油站所加汽油的量，总费用为P p(i)*x(i)i=0,1,.,n,两个城市之间的距离是固定不变的，汽车从出发点到达目的地所需要的汽油总量（即x(i)i=0,1,.,n）自然也是固定不变的。根据使费用最少的求解目标，要使费用函数取得最优值（在此为最小值），必须使p(i)尽可能小：也就是汽车要尽可能在价格便宜的油站加
11、油。,汽车每到达一个油站i（包括出发点第0站，但不包括目的地第n+1站），都要检查是否需要加油。,如果汽车在某个油站i需要加油，那么，就先将该油站的汽油价格p(i)与下一油站的汽油价格p(i+1)进行比较，若p(i)=p(i+1)，加油时，只需保证油箱中的汽油能够到达下一油站（第i+1站）即可；否则，继续将p(i)与第i+2站的汽油价格p(i+2)进行比较，,判断是否需要在第i站加油的条件可以确定为：在到达第i站时，汽车油箱中的剩余汽油（用变量rest表示剩余汽油的多少）是否足够行驶到下一更便宜的油站j，即rest*e是否大于或等于d(j)-d(i)。如果一直找不到比第i个油站更便宜的油站j，
12、则在第i个油站加满油（如果不用加满就已经到了终点，则加油量应该满足刚好到达终点）,哈夫曼编码,哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。,前缀码,对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。,编码的前缀性质可以使译码方法非常简单平均码长定义为：使平均码长达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码。表示最优前缀
13、码的二叉树树中任一结点都有2个儿子结点,构造哈夫曼编码,哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以|C|个叶结点开始，执行|C|1次的“合并”运算后产生最终所要求的树T。,算法huffmanTree中，编码字符集中每一字符c的频率是f(c)。以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。经过n1次的合并后，优先队列中只剩下一棵树，即所要求的树T。,算法huffman
14、Tree用最小堆实现优先队列Q。初始化优先队列需要O(n)计算时间，由于最小堆的removeMin和put运算均需O(logn)时间，n1次的合并总共需要O(nlogn)计算时间。因此，关于n个字符的哈夫曼算法的计算时间为O(nlogn)。,选址问题,给定n个小区之间的交通图。若小区i与小区j之间有路可通，则将顶点i与顶点j之间用边连接，边上的权值 表示这条道路的长度。现在打算在这n个小区中选定一个小区建一所医院。试问这家医院应建在哪个小区，才能使距离医院最远的小区到医院的路程最短？请设计一 个算法求解上述问题。,单源最短路径,给定带权有向图G=(V,E)，其中每条边的权是非负实数。另外，还给
15、定V中的一个顶点v，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。,单源最短路径,Dijkstra算法是解决单源最短路径问题的贪心算法。其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。,通过分步方法求出最短路径,每一步产生一个到达新的目的顶点的最短路径下一步所能达到的目的顶点通过如下贪婪准则选取：在还未产生最短路径的顶点中，选择路径长度最短的目的顶点,单源最短路径,初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到
16、u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。,Dijkstra算法的迭代过程,选址问题,给定n个小区之间的交通图。若小区i与小区j之间有路可通，则将顶点i与顶点j之间用边连接，边上的权值 表示这条道路的长度。现在打算在这n个小区中选定一个小区建一所医院。试问这家医院应建在哪个小区，才能使距离医院最远的小区到医院的路程最短？请设计一 个算法求解上述问题。,将n个小区的交通图视为一
17、张带权无向图，并利用邻接矩阵来存放带权无向图。算法的思想是：应用Dijkstra算法计算每对顶点之间的最短路径；找出从每一个顶点到其它各顶点的最短路径中最长路径；在这n条最长路径中找出最短的一条，则它的出发点即为所求。,如何架设通信网络,如下图G，图中的6个顶点为某乡的6个村，图G的边代表公路，现在要沿公路架设电线，使各村之间都通电话，问应该怎样架线，才能使所用的电线最少？,最小生成树,设G=(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)的权为cvw。如果G的子图G是一棵包含G的所有顶点的树，则称G为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小
18、的生成树称为G的最小生成树。,最小生成树性质（MST性质）,设G=(V,E)是连通带权图，U是V的真子集。如果(u,v)E，且u U，v V-U，且在所有这样的边中，边（u，v）的权最小，那么一定存在G的一棵最小生成树，以（u，v）为其中一条边。,Prim算法,设G=(V,E)是连通带权图，V=1,2,n。构造G的最小生成树的Prim算法的基本思想是：首先置S=1，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件iS，jV-S，且cij最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。,例如，对于右图中的带权图，按Pr
19、im算法选取边的过程如下页图所示。,在上述Prim算法中，还应当考虑如何有效地找出满足条件iS,jV-S，且权cij最小的边(i,j)。实现这个目的的较简单的办法是设置2个数组closest和lowcost。在Prim算法执行过程中，先找出V-S中使lowcost值最小的顶点j，然后根据数组closest选取边(j,closestj)，最后将j添加到S中，并对closest和lowcost作必要的修改。用这个办法实现的Prim算法所需的计算时间为,Kruskal算法,Kruskal算法构造G的最小生成树的基本思想是，首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。,Kru
20、skal算法,从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：1、当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；2、如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。,当图的边数为e时，Kruskal算法所需的计算时间是。当 时，Kruskal算法比Prim算法差，但当 时，Kruskal算法却比Prim算法好得多。,Google Book,You,the best hacker
21、in the world,want to download the books published on Google Book.After some investigation,you found that the address of each page consists of two parts.The first part is the page number,the second part is the signature which is unique for each page.,Google Book,To get the signature,you can send the
22、query to the server.The query has one parameter,which indicates the page number.The server will return the signature of the required page,and it may also return the signature of some adjacent pages.minimize the number of queries,Google Book,Sample Input2 3 1 1 2 2 3 3 3 1 1 1 3 3 3,Sample Output3 1,
23、区间覆盖问题贪心策略:选取的区间能覆盖尽可能长的区域,并且保证所有的1-n的范围都给覆盖到第1步:1开始的区间,取覆盖范围最长的,设为1,max接下来,每次取能覆盖到max+1的最长覆盖区间s,e,s=max+1,对每个区间，以其起始坐标为关键字，从小到大排序；如果起始坐标相等，则按结束坐标从大到小排序,另一区间覆盖问题,用i来表示x轴上坐标为i-1,i的区间（长度为1），并给出M(1=M=200)个不同的整数，表示M个这样的区间。现在让你画几条线段覆盖住所有的区间，条件是：每条线段可以任意长，但是要求所画线段之和最小，并且线段的数目不超过N(1=N=50)。例如：M=5个整数1、3、4、8和
24、11表示区间，要求所用线段不超过N=3条0 1 2 3 4 5 6 7 8 9 10 11,算法分析,如果N=M，那么显然用M条长度为1的线段可以覆盖住所有的区间，所求的线段总长为M。如果N=1，那么显然所需线段总长为：如果N=2，相当于N=1的情况下从某处断开（从哪儿断开呢？）如果N=k呢？,多机调度问题,多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。这个问题是NP完全问题，到目前为止还没有有效的解法。对于这一类问题,用贪心选择策略有时可以设计出较好的近似算法。,约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆
25、分成更小的子作业。,多机调度问题,当 n=m 时，设置合理的贪心策略求解,例：假设有9个独立的作业1，2，3，4，5，6，7，8，9，由3台机器M1，M2，M3来加工处理。各作业所处理的时间Tt1，t2，t9=81，40，26，4，65，98，53，71，15。,贪心策略的设置,1、将每个作业平均分给每台机器，即每个机器处理一样数量的作业,此方法的优点是容易想到，相当简单，但没有充分利用机器的处理能力，只是按照任务的次序进行分配，当有比较大的任务集中分配给一台机器而其它任务较小时会造成其他机器等待，效率较低。,2、把作业处理所需时间按照从小到大的顺序依次分给每台机器,此方法也容易想到，实现起来也较简单，同时也考虑到了时间的安排，但处理时间最长的作业放在最后处理，如果M1，M2跟M3处理完前两个任务时间基本相同的话，会造成M1和M2的闲置，这样机器的利用效率也比较低。,3、把作业处理所需时间按照从大到小的顺序依次分给每台机器,将作业处理所需时间按照从大到小排序，分给每台机器后把剩下的作业分给空闲的机器，即把耗时最多的作业分配给先空闲的机器，这样就充分利用了每台机器的处 理能力，显然有利于均衡。这就是我们所要提出的采用最长处理时间作业优先的贪心选择策略，用这种策略可以设计出解多机调度问题的较好的近似算法。,
