资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第7章 贪心法,7.1 概 述,7.2 图问题中的贪心法,7.3 组合问题中的贪心法,8/28/2024,1,7.1 概 述,7.1.1 贪心法的设计思想,7.1.2 贪心法的求解过程,8/28/2024,2,贪心法只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。,7.1.1 贪心法的设计思想,换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。,这种局部最优选择并不总能获得整体最优解Optimal Solution，但通常能获得近似最优解Near-Optimal Solution。,8/28/2024,3,例：用贪心法求解付款问题。,假设有面值为5元、2元、1元、5角、2角、1角的货币，需要找给顾客4元6角现金，为使付出,的货币的数量最少，首先选出1张面值不超过4元6角的最大面值的货币，即2元，再选出1张面值不超过2元6角的最大面值的货币，即2元，再选出1张面值不超过6角的最大面值的货币，即5角，再选出1张面值不超过1角的最大面值的货币，即1角，总共付出4张货币。,面值改为3元、1元、8角、5角、1角的货币如何?,8/28/2024,4,在付款问题每一步的贪心选择中，在不超过应付款金额的条件下，只选择面值最大的货币，而不去考虑在后面看来这种选择是否合理，而且它还不会改变决定：一旦选出了一张货币，就永远选定。,付款问题的贪心选择策略是尽可能使付出的货币最快地满足支付要求，其目的是使付出的货币张数最慢地增加，这正表达了贪心法的设计思想。,8/28/2024,5,贪心法求解的问题的特征：,动态规划法通常以自底向上的方式求解各个子问题，而贪心法那么通常以自顶向下的方式做出一系列的贪心选择。,1最优子结构性质,当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理。,2贪心选择性质,所谓贪心选择性质是指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。,8/28/2024,6,7.1.2 贪心法的求解过程,用贪心法求解问题应该考虑如下几个方面：,1候选集合C：为了构造问题的解决方案，有一个候选集合C作为问题的可能解，即问题的最终解均取自于候选集合C。例如，在付款问题中，各种面值的货币构成候选集合。,2解集合S：随着贪心选择的进行，解集合S不断扩展，直到构成一个满足问题的完整解。例如，在付款问题中，已付出的货币构成解集合。,8/28/2024,7,3解决函数solution：检查解集合S是否构成问题的完整解。例如，在付款问题中，解决函数是已付出的货币金额恰好等于应付款。,4选择函数select：即贪心策略，这是贪心法的关键，它指出哪个候选对象最有希望构成问题的解，选择函数通常和目标函数有关。例如，在付款问题中，贪心策略就是在候选集合中选择面值最大的货币。,5可行函数feasible：检查解集合中参加一个候选对象是否可行，即解集合扩展后是否满足约束条件。例如，在付款问题中，可行函数是每一步选择的货币和已付出的货币相加不超过应付款。,8/28/2024,8,贪心法的一般过程,Greedy(C) /C是问题的输入集合即候选集合,S= ; /初始解集合为空集,while (not solution(S) /集合S没有构成问题的一个解,x=select(C); /在候选集合C中做贪心选择,if feasible(S, x) /判断集合S中参加x后的解是否可行,S=S+x;,C=C-x;,return S;,8/28/2024,9,7.2 图问题中的贪心法,7.2.1 TSP问题,7.2.2 图着色问题,7.2.3 最小生成树问题,8/28/2024,10,7.2.1 TSP,问题,求解TSP问题至少有两种贪心策略是合理的：,1最近邻点策略：从任意城市出发，每次在没有到过的城市中选择最近的一个，直到经过了所有的城市，最后回到出发城市。,8/28/2024,11,(d) 城市3城市5 (e) 城市5城市2 (f) 城市2城市1,最近邻点贪心策略求解TSP问题的过程,2,5,2,2,1,5,4,3,2,2,5,2,2,1,5,4,3,2,3,2,5,2,2,1,5,4,3,2,7,3,6,3,2,1,5,4,3,2,2,3,3,2,1,5,4,3,2,C=, 3 3 2 6,3 7 3 2,3 7 2 5,2 3 2 3,6 2 5 3 ,(a) 5城市的代价矩阵 (b) 城市1城市4 (c) 城市4城市3,8/28/2024,12,算法7.1最近邻点策略求解TSP问题,1 P= ;,2 V=V,-,u,0,; u=u,0,; /从顶点u,0,出发,3 循环直到集合P中包含n,-,1条边,3.1 查找与顶点u邻接的最小代价边(u, v)并且v属于集合V；,3.2 P=P+(u, v);,3.3 V=V,-,v;,3.4 u=v; /从顶点v出发继续求解,伪代码,设图,G,有,n,个顶点，边上的代价存储在二维数组,wnn,中，集合,V,存储图的顶点，集合,P,存储经过的边，最近邻点策略求解,TSP,问题的算法如下：,8/28/2024,13,算法7.1的时间性能为,O,(,n,2,)，因为共进行n-1次贪心选择，每一次选择都需要查找满足贪心条件的最短边。,用最近邻点贪心策略求解,TSP,问题所得的结果不一定是最优解，图,7.1(a),中从城市,1,出发的最优解是,1,2,5,4,3,1,，总代价只有,13,。,当图中顶点个数较多并且各边的代价值分布比较均匀时，最近邻点策略可以给出较好的近似解，不过，这个近似解以何种程度近似于最优解，却难以保证。例如，在图7.1中，如果增大边(2, 1)的代价，那么总代价只好随之增加，没有选择的余地。,8/28/2024,14,2最短链接策略：每次在整个图的范围内选择最短边参加到解集合中，但是，要保证参加解集合中的边最终形成一个哈密顿回路。,因此，当从剩余边集E中选择一条边(u, v)参加解集合S中，应满足以下条件：, 边(u, v)是边集E中代价最小的边；, 边(u, v)参加解集合S后，S中不产生回路；, 边(u, v) 参加解集合S后，S中不产生分枝；,8/28/2024,15,2,1,5,4,3,2,2,1,5,4,3,2,C=, 3 3 2 6,3 7 3 2,3 7 2 5,2 3 2 3,6 2 5 3 ,(a) 5城市的代价矩阵 (b) 城市1城市4 (c) 城市5城市2,2,(d) 城市4城市3 (e) 城市3城市5 (f) 城市2回到出发城市1,最短链接贪心策略求解TSP问题的过程,2,2,2,1,5,4,3,2,2,2,2,1,5,4,3,2,2,2,2,1,5,4,3,2,5,3,5,8/28/2024,16,算法7.2最短链接策略求解TSP问题,1P= ;,2E,=E; /候选集合，初始时为图中所有边,3循环直到集合P中包含n,-,1条边,3.1 在E,中选取最短边(u, v);,3.2 E,=E,-,(u, v);,3.3 如果 (顶点u和v在P中不连通 and 不产生分枝),则P=P+(u, v);,伪代码,设图,G,有,n,个顶点，边上的代价存储在二维数组,wnn,中，集合,E,是候选集合即存储所有未选取的边，集合,P,存储经过的边，最短链接策略求解,TSP,问题的算法如下：,8/28/2024,17,在算法7.2中，如果操作“在E中选取最短边(u, v)用顺序查找，那么算法7.2的时间性能是O(n2)。,如果采用堆排序的方法将集合E中的边建立堆，那么选取最短边的操作可以是O(log2n)，对于两个顶点是否连通以及是否会产生分枝，可以用并查集的操作将其时间性能提高到O(n)，此时算法7.2的时间性能为O(nlog2n)。,8/28/2024,18,7.2.2,图着色问题,给定无向连通图,G,=(,V,E,)，求图,G,的最小色数,k,，使得用,k,种颜色对,G,中的顶点着色，可使任意两个相邻顶点着色不同。,8/28/2024,19,1,2,3,4,5,以下图可以只用两种颜色着色，将顶点1、3和4着成一种颜色，将顶点2和顶点5着成另外一种颜色。,8/28/2024,20,贪心策略：选择一种颜色，以任意顶点作为开始顶点，依次考察图中的未被着色的每个顶点，如果一个顶点可以用颜色1着色，换言之，该顶点的邻接点都还未被着色，那么用颜色1为该顶点着色。,3,4,5,1,2,1,2,3,4,5,当没有顶点能以这种颜色着色时，选择颜色2和一个未被着色的顶点作为开始顶点，用第二种颜色为尽可能多的顶点着色，如果还有未着色的顶点，那么选取颜色3并为尽可能多的顶点着色，依此类推。,顶点顺序1,2,3,4,5,顶点顺序1,5, 2,3,4,8/28/2024,21,算法7.3图着色问题,1color1=1; /顶点1着颜色1,2for (i=2; i=n; i+) /其他所有顶点置未着色状态,colori=0;,3k=0;,4循环直到所有顶点均着色,4.1 k+; /取下一个颜色,4.2 for (i=2; iC),4.1 xi=1; /将第i个物品放入背包,4.2 C=C-wi;,4.3 i+;,5. xi=C/wi;,伪代码,算法7.6的时间主要消耗在将各种物品依其单位重量的价值从大到小排序。因此，其时间复杂性为,O,(,n,log2,n,)。,8/28/2024,37,7.3.2 活动安排问题,设有n个活动的集合E=1, 2, , n，其中每个活动都要求使用同一资源如演讲会场，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi，且si =fj) 则,4.1.1 B=B+j;,4.1.2 j=i;,4.2 i+;,伪代码,算法,7.7,的时间主要消耗在将各个活动按结束时间从小到大排序。因此，算法的时间复杂性为,O,(,n,log,2,n,),。,8/28/2024,42,算法7.8活动安排问题,int ActiveManage(int s , int f , bool a , int n), /各活动的起始时间和结束时间存储于数组s和f中且,/按结束时间的非减序排列,a1=1;,j=1; count=1;,for (i=2; i=fj) ,ai=1;,j=i;,count+;,else ai=0;,return count;,C+描述,8/28/2024,43,7.3.3,多机调度问题,设有n个独立的作业1, 2, , n，由m台相同的机器M1, M2, , Mm进行加工处理，作业i所需的处理时间为ti1in，每个作业均可在任何一台机器上加工处理，但不可间断、拆分。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。,8/28/2024,44,贪心法求解多机调度问题的贪心策略是,最长处理时间,作业优先，即把处理时间最长的作业分配给最先空闲的机器，这样可以保证处理时间长的作业优先处理，从而在整体上获得尽可能短的处理时间。,按照最长处理时间作业优先的贪心策略，当,m,n,时，只要将机器,i,的0,ti,)时间区间分配给作业,i,即可；当,m,n,时，首先将,n,个作业依其所需的处理时间从大到小排序，然后依此顺序将作业分配给空闲的处理机。,8/28/2024,45,例：设7个独立作业1, 2, 3, 4, 5, 6, 7由3台机器,M,1,M,2,M,3,加工处理，各作业所需的处理时间分别为2, 14, 4, 16, 6, 5, 3。贪心法产生的作业调度如下：,M,1,M,2,M,3,时间,分配,作业5,作业6,作业3,作业1,作业2,作业7,作业4,17,16,图7.10 三台机器的调度问题示例,6,5,4,8/28/2024,46,算法7.9多机调度问题,1将数组tn由大到小排序，对应的作业序号存储在数组pn中；,2将数组dm初始化为0；,3for (i=1; i=m; i+),3.1 Si=pi; /将m个作业分配给m个机器,3.2 di=ti;,4. for (i=m+1; i=n; i+),4.1 j=数组dm中最小值对应的下标； /j为最先空闲的机器序号,4.2 Sj=Sj+pi; /将作业i分配给最先空闲的机器j,4.3 dj=dj+ti; /机器j将在dj后空闲,伪代码,在算法7.9中，操作“数组dm中最小值对应的下标如果采用蛮力法查找，那么算法的时间性能为：,通常情况下mn，那么算法7.9的时间复杂性为O(nm)。,8/28/2024,47,
展开阅读全文