1贪婪算法

贪婪算法解题的一般思路 作者：未知 最优化问题是程序设计中一类非常重要的问题。每一个最优化问题都包含一组约束条件和一个优化函数，满足约束条件的问题求解称为问题的可行解，使优化函数取得最优值的可行解称为问题的最优解。贪婪算法是解决最优化问题的一种基本方法。它采用逐步构造最优解的思想，在问题求解的每一个阶段，都作出一个在一定下看上去最优的决策；决策一旦作出，就不可再更改。制定决策的依据称为贪婪准则。使用贪婪算法解决问题，通常需要做好以下几个方面的工作： 1、明确问题的求解目标。 2、分析问题所包含的约束条件。 3、建立优化函数。优化函数通常可以通过综合分析问题的求解目标及约束条件归纳出来。 4、制定贪婪准则。清楚问题的求解目标、所包含的约束条件及优化函数之后，就可以着手制定一个可行的贪婪准则。贪婪准则的制定是用贪婪算法解决最优化问题的关键，它关系到问题能否得到成功解决及解决质量的高低。 把以上几个方面的工作都完成了，问题自然会不攻自破。 例1：计算发放工资时所需的最少人民币张数。输入数据为职工的工资数。要求统计并输出应发给该职工面值100元、50元、20元、10元、5元、2元、1元的人民币各多少张，使总张数最少。 分析：举个具体例子，假设某职工的工资为638元，我们该发给他多少张人民币呢？答案可以是638张面值1元的人民币，可以是638/2=319张面值2元的人民币，……无论发给该职工人民币多少张，他拿到的人民币总和都应等于他自己的工资数。 要发给该职工638元的工资，并使总张数最少，直觉告诉我们，应先给他6张面值100元的人民币；第7张不能再给100元的，也不能给50元的，否则该职工实际拿到的工资将会超过他应得的工资；显然，第7张应为面值20元的人民币。同理，第8张为面值10元的人民币，第9张为面值5元的人民币，第10张为面值2元的人民币，第11张为面值1元的人民币。该职工共拿到人民币11张，分别为面值100元的6张，面值50元的没有，面值20元、10元、5元、2元和1元的各1张。这样，不但满足了约束条件 =zggz，即100×6+（20+10+5+2+1）×1＝638，而且使该职工拿到的人民币张数最少。把以上操作方法归纳出来就是一种可行的贪婪准则：按面值从大到小的顺序分发人民币，并始终保证职工实际拿到的工资不超过他应得的工资。参考程序如下： dim mz(1 to 7) as integer dim zs(1 to 7) as integer cls : input zggz mz(1) = 100: mz(2) = 50: mz(3) = 20 mz(4) = 10: mz(5) = 5: mz(6) = 2: mz(7) = 1 for i = 1 to 7     zs(i) = 0 next i i = 1: sy = zggz rem 变量sy用来记录在给某职工发工资的过程中，某一时刻还需要付给该职工的人民币总数 do while i <= 7 and sy > 0   do while mz(i) * (zs(i) + 1) <= sy     zs(i) = zs(i) + 1  loop   sy = sy - zs(i) * mz(i)   i = i + 1 loop for i = 1 to 7     print mz(i); ":"; zs(i) next i end 例2：旅行家的预算（1999年全国青少年信息学（计算机）奥林匹克分区联赛高中组复赛试题第三题） 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离d1、汽车油箱的容量c（以升为单位），每升汽油能行驶的距离d2、出发点每升汽油的价格p和沿途油站数n（n可以为零），油站i离出发点的距离di、每升汽油的价格pi（i=1,2, ……n）。 计算结果四舍五入至小数点后两位。 如果无法到达目的地，则输出“No solution”。 分析：对于任意给定的输入数据，并不一定能保证旅行家能够到达目标城市。如果旅行家不能到达目的地，那么对最少费用的预算将毫无意义。所以，在预算最少费用之前，有必要对输入数据进行分析，看是否能使旅行家到达目的地。当已经确认旅行家能够到达目的地之后，再预算最少费用；如果通过对输入数据进行分析，确定旅行家不能到达目的地，那么，按照题目要求直接输出提示信息“No solution”即可。算法程序如下： （1）输入数据 （2）判断旅行家能否到达目的地 if 能到达目的地 then （3）预算最少费用 （4）输出最少费用 else     输出提示信息“No solution” endif end 为了便于判断旅行家是否能够到达目的地，我们设置数组d(0 to n+1)，用来保存每一个油站离出发点的距离，其中，d(0)=0表示出发点，d(n+1)=d1（两个城市之间的距离）表示终点；设置变量Dmax，用来表示油箱装满汽油时汽车能够行驶的最大距离；设置标志flag，用来能否到达目的地，若旅行家能到达目的地，则flag=1,否则flag=0。第（2）步判断旅行家是否能够到达目的地，可用下面代码实现： Dmax=c*d2 rem d2为每升汽油能行驶的距离 flat=1:i=1 while i<=n+1 and flag=1    if d(i)-d(i-1)>Dmax then       flag=0   else       i=i+1   endif wend 第（3）步预算最少费用是整个问题的核心，也是解决问题的难点。我们可以使用贪婪算法的解题思想来进行分析。首先仔细阅读题目，明确问题的求解目标是“最少的费用”；再联系实际进行思考，不难发现问题中隐含着一个约束条件：汽车在到达目的地之前的每一时刻，都必须保证油箱中的汽油足够行驶到下一油站。如果以p(i)表示第i油站的汽油价格，x(i)表示在第i油站所加汽油的量，那么，优化函数就是 。两个城市之间的距离是固定不变的，汽车从出发点到达目的地所需要的汽油总量（即 ）自然也是固定不变的。根据使费用最少的求解目标，要使优化函数 取得最优值（在此为最小值），必须使p(i)尽可能小：也就是汽车要尽可能在价格便宜的油站加油。这是解决问题的贪婪准则。汽车每到达一个油站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站时，汽车油箱中的剩余汽油（用变量sy表示剩余汽油的多少）是否足够行驶到下一油站，即sy*d2是否大于或等于d(i+1)-d(i)。预算最少费用的算法程序如下： for i=0 to n   ①计算到达第i站时汽车油箱中还剩下的汽油量sy   if 汽车需要加油 then       ②给汽车加油   endif next i 汽车在第0站（出发点）的时候，油箱中的汽油量肯定是0，不用计算；从第1站开始，以后每经过一个油站，我们都计算一下油箱中还剩下多少汽油，以便判断汽车是否需要加油。计算的方法是：用上一次产生的剩余汽油量减掉汽车从前面一站（第i-1站）行驶到现在的位置（第i站）所消耗的汽油量。对以上算法中的第①步进行求精，得到下面的代码： if i >= 1 then     sy = sy - (d(i) - d(i - 1)) / d2   endif 汽车到达油站i时，如果需要加油，那需要加多少油呢？根据以上分析出来的贪婪策略：先将油站i的汽油价格p(i)与下一油站的汽油价格p(i+1)进行比较，若p(i)>=p(i+1)，只需保证油箱中的汽油能够到达下一油站即可；若p(i)< font> sub jy(i as integer,j as integer)   if p(i)>=p(j) then    if (d(j)-d(i))/d2>c then   rem 即便把油箱加满，还是不能到达j站（注意：不是i的下一站i+1）    fy=fy+(c-sy)*p(i)   rem fy用来累计费用  sy = c   else   fy=fy+((d(j)-d(i))/d2-sy)*p(i)   sy = (d(j) - d(i)) / d2  endif   else  call jy(i,j+1) endif end sub 第 1 章 贪婪算法   虽然设计一个好的求解算法更像是一门艺术，而不像是技术，但仍然存在一些行之有效的能够用于解决许多问题的算法设计方法，你可以使用这些方法来设计算法，并观察这些算法是如何工作的。一般情况下，为了获得较好的性能，必须对算法进行细致的调整。但是在某些情况下，算法经过调整之后性能仍无法达到要求，这时就必须寻求另外的方法来求解该问题。 本章首先引入最优化的概念，然后介绍一种直观的问题求解方法：贪婪算法。最后，应用该算法给出货箱装船问题、背包问题、拓扑排序问题、二分覆盖问题、最短路径问题、最小代价生成树等问题的求解方案。   1.1 最优化问题   本章及后续章节中的许多例子都是最优化问题（ optimization problem），每个最优化问题都包含一组限制条件（ c o n s t r a i n t）和一个优化函数（ optimization function），符合限制条件的问题求解方案称为可行解（ feasible solution），使优化函数取得最佳值的可行解称为最优解（optimal solution）。 例1-1 [ 渴婴问题] 有一个非常渴的、聪明的小婴儿，她可能得到的东西包括一杯水、一桶牛奶、多罐不同种类的果汁、许多不同的装在瓶子或罐子中的苏打水，即婴儿可得到n 种不同的饮料。根据以前关于这n 种饮料的不同体验，此婴儿知道这其中某些饮料更合自己的胃口，因此，婴儿采取如下方法为每一种饮料赋予一个满意度值：饮用1盎司第i 种饮料，对它作出相对，将一个数值si 作为满意度赋予第i 种饮料。 通常，这个婴儿都会尽量饮用具有最大满意度值的饮料来最大限度地满足她解渴的需要，但是不幸的是：具有最大满意度值的饮料有时并没有足够的量来满足此婴儿解渴的需要。设ai是第i 种饮料的总量（以盎司为单位），而此婴儿需要t 盎司的饮料来解渴，那么，需要饮用n种不同的饮料各多少量才能满足婴儿解渴的需求呢？ 设各种饮料的满意度已知。令xi 为婴儿将要饮用的第i 种饮料的量，则需要解决的问题是： 找到一组实数xi（1≤i≤n），使n i = 1si xi 最大，并满足：n i=1xi =t 及0≤xi≤ai 。 需要指出的是：如果n i = 1ai < t，则不可能找到问题的求解方案，因为即使喝光所有的饮料也不能使婴儿解渴。 对上述问题精确的数学描述明确地指出了程序必须完成的工作，根据这些数学公式，可以对输入/ 输出作如下形式的描述： 输入：n，t，si ，ai（其中1≤i≤n，n 为整数，t、si 、ai 为正实数）。 输出：实数xi（1≤i≤n），使n i= 1si xi 最大且n i=1xi =t（0≤xi≤ai）。如果n i = 1ai k。寻找[ 1 ,n]范围内最小的整数j，使得xj≠yj 。若没有这样的j 存在，则n i= 1xi =n i = 1yi 。如果有这样的j 存在，则j≤k，否则y 就不是一个可行解，因为xj≠yj ，xj = 1且yj = 0。令yj = 1，若结果得到的y 不是可行解，则在[ j+ 1 ,n]范围内必有一个l 使得yl = 1。令yl = 0，由于wj≤wl ，则得到的y 是可行的。而且，得到的新y 至少与原来的y 具有相同数目的1。 经过数次这种转化，可将y 转化为x。由于每次转化产生的新y 至少与前一个y 具有相同数目的1，因此x 至少与初始的y 具有相同的数目1。货箱装载算法的C + +代码实现见程序1 3 - 1。由于贪婪算法按货箱重量递增的顺序装载，程序1 3 - 1首先利用间接寻址排序函数I n d i r e c t S o r t对货箱重量进行排序（见3 . 5节间接寻址的定义），随后货箱便可按重量递增的顺序装载。由于间接寻址排序所需的时间为O (nl o gn)（也可利用9 . 5 . 1节的堆排序及第2章的归并排序），算法其余部分所需时间为O (n)，因此程序1 3 - 1的总的复杂性为O (nl o gn)。 程序13-1 货箱装船 template void ContainerLoading(int x[], T w[], T c, int n) {// 货箱装船问题的贪婪算法 // x[i] = 1 当且仅当货箱i被装载， 1<=i<=n // c是船的容量, w 是货箱的重量 // 对重量按间接寻址方式排序 // t 是间接寻址表 int *t = new int [n+1]; I n d i r e c t S o r t ( w, t, n); // 此时, w[t[i]] <= w[t[i+1]], 1<=i0时总的时间开销为O (nk+1 )。实际观察到的性能要好得多。   1.3.3 拓扑排序 一个复杂的工程通常可以分解成一组小任务的集合，完成这些小任务意味着整个工程的完成。例如，汽车装配工程可分解为以下任务：将底盘放上装配线，装轴，将座位装在底盘上，上漆，装刹车，装门等等。任务之间具有先后关系，例如在装轴之前必须先将底板放上装配线。任务的先后顺序可用有向图表示——称为顶点活动（ Activity On Vertex, AOV）网络。有向图的顶点代表任务，有向边(i, j) 表示先后关系：任务j 开始前任务i 必须完成。图1 - 4显示了六个任务的工程，边（ 1 , 4）表示任务1在任务4开始前完成，同样边（ 4 , 6）表示任务4在任务6开始前完成，边（1 , 4）与（4 , 6）合起来可知任务1在任务6开始前完成，即前后关系是传递的。由此可知，边（1 , 4）是多余的，因为边（1 , 3）和（3 , 4）已暗示了这种关系。 在很多条件下，任务的执行是连续进行的，例如汽车装配问题或平时购买的标有“需要装配”的消费品（自行车、小孩的秋千装置，割草机等等）。我们可根据所建议的顺序来装配。在由任务建立的有向图中，边（ i, j）表示在装配序列中任务i 在任务j 的前面，具有这种性质的序列称为拓扑序列（topological orders或topological sequences)。根据任务的有向图建立拓扑序列的过程称为拓扑排序（topological sorting）。图1 - 4的任务有向图有多种拓扑序列，其中的三种为1 2 3 4 5 6，1 3 2 4 5 6和2 1 5 3 4 6，序列1 4 2 3 5 6就不是拓扑序列，因为在这个序列中任务4在3的前面，而任务有向图中的边为（ 3 , 4），这种序列与边（ 3 , 4）及其他边所指示的序列相矛盾。可用贪婪算法来建立拓扑序列。算法按从左到右的步骤构造拓扑序列，每一步在排好的序列中加入一个顶点。利用如下贪婪准则来选择顶点：从剩下的顶点中，选择顶点w，使得w 不存在这样的入边（ v,w），其中顶点v 不在已排好的序列结构中出现。注意到如果加入的顶点w违背了这个准则（即有向图中存在边（ v,w）且v 不在已构造的序列中），则无法完成拓扑排序，因为顶点v 必须跟随在顶点w 之后。贪婪算法的伪代码如图1 3 - 5所示。while 循环的每次迭代代表贪婪算法的一个步骤。 现在用贪婪算法来求解图1 - 4的有向图。首先从一个空序列V开始，第一步选择V的第一个顶点。此时，在有向图中有两个候选顶点1和2，若选择顶点2，则序列V = 2，第一步完成。第二步选择V的第二个顶点，根据贪婪准则可知候选顶点为1和5，若选择5，则V = 2 5。下一步，顶点1是唯一的候选，因此V = 2 5 1。第四步，顶点3是唯一的候选，因此把顶点3加入V 得到V = 2 5 1 3。在最后两步分别加入顶点4和6 ，得V = 2 5 1 3 4 6。 1. 贪婪算法的正确性 为保证贪婪算法算的正确性，需要证明： 1) 当算法失败时，有向图没有拓扑序列； 2) 若 算法没有失败，V即是拓扑序列。2) 即是用贪婪准则来选取下一个顶点的直接结果， 1) 的证明见定理1 3 - 2，它证明了若算法失败，则有向图中有环路。若有向图中包含环qj qj + 1.qk qj , 则它没有拓扑序列，因为该序列暗示了qj 一定要在qj 开始前完成。 定理1-2 如果图1 3 - 5算法失败，则有向图含有环路。 证明注意到当失败时| V | S; for (i = 1; i <= n; i++) if (!InDegree[i]) S.Add(i); // 产生拓扑次序 i = 0; // 数组v 的游标 while (!S.IsEmpty()) {// 从堆栈中选择 int w; // 下一个顶点 S . D e l e t e ( w ) ; v[i++] = w; int u = Begin(w); while (u) {// 修改入度 I n D e g r e e [ u ] - - ; if (!InDegree[u]) S.Add(u); u = NextVe r t e x ( w ) ; } } D e a c t i v a t e P o s ( ) ; delete [] InDegree; return (i == n); }   1.3.4 二分覆盖 二分图是一个无向图，它的n 个顶点可二分为集合A和集合B，且同一集合中的任意两个顶点在图中无边相连（即任何一条边都是一个顶点在集合A中，另一个在集合B中）。当且仅当B中的每个顶点至少与A中一个顶点相连时，A的一个子集A' 覆盖集合B（或简单地说，A' 是一个覆盖）。覆盖A' 的大小即为A' 中的顶点数目。当且仅当A' 是覆盖B的子集中最小的时，A' 为最小覆盖。 例1-10 考察如图1 - 6所示的具有1 7个顶点的二分图，A={1, 2, 3, 16, 17}和B={4, 5, 6, 7, 8, 9,10, 11, 12, 13, 14, 15}，子集A' = { 1 , 1 6 , 1 7 }是B的最小覆盖。在二分图中寻找最小覆盖的问题为二分覆盖（ b i p a r t i t e - c o v e r）问题。在例1 2 - 3中说明了最小覆盖是很有用的，因为它能解决“在会议中使用最少的

翻译

阿房宫赋翻译下载德汉翻译pdf阿房宫赋翻译下载阿房宫赋翻译下载翻译理论.doc

人员进行翻译”这一类的问题。 二分覆盖问题类似于集合覆盖（ s e t - c o v e r）问题。在集合覆盖问题中给出了k 个集合S= {S1 , S2 ,., Sk }，每个集合Si 中的元素均是全集U中的成员。当且仅当i S'Si =U时，S的子集S' 覆盖U，S '中的集合数目即为覆盖的大小。当且仅当没有能覆盖U的更小的集合时，称S' 为最小覆盖。可以将集合覆盖问题转化为二分覆盖问题（反之亦然），即用A的顶点来表示S1 , ., Sk ，B中的顶点代表U中的元素。当且仅当S的相应集合中包含U中的对应元素时，在A与B的顶点之间存在一条边。 例1 - 11 令S= {S1，. . .，S5 }, U= { 4，5，. . .，15}, S1 = { 4，6，7，8，9，1 3 }，S2 = { 4，5，6，8 }，S3 = { 8，1 0，1 2，1 4，1 5 }，S4 = { 5，6，8，1 2，1 4，1 5 }，S5 = { 4，9，1 0，11 }。S ' = {S1，S4，S5 }是一个大小为3的覆盖，没有更小的覆盖， S' 即为最小覆盖。这个集合覆盖问题可映射为图1-6的二分图，即用顶点1，2，3，1 6和1 7分别表示集合S1，S2，S3，S4 和S5，顶点j 表示集合中的元素j，4≤j≤1 5。 集合覆盖问题为N P-复杂问题。由于集合覆盖与二分覆盖是同一类问题，二分覆盖问题也是N P-复杂问题。因此可能无法找到一个快速的算法来解决它，但是可以利用贪婪算法寻找一种快速启发式方法。一种可能是分步建立覆盖A' ，每一步选择A中的一个顶点加入覆盖。顶点的选择利用贪婪准则：从A中选取能覆盖B中还未被覆盖的元素数目最多的顶点。 例1-12 考察图1 - 6所示的二分图，初始化A' = 且B中没有顶点被覆盖，顶点1和1 6均能覆盖B中的六个顶点，顶点3覆盖五个，顶点2和1 7分别覆盖四个。因此，在第一步往A' 中加入顶点1或1 6，若加入顶点1 6，则它覆盖的顶点为{ 5 , 6 , 8 , 1 2 , 1 4 , 1 5 }，未覆盖的顶点为{ 4 , 7 , 9 , 1 0 , 11 , 1 3 }。顶点1能覆盖其中四个顶点（ { 4 , 7 , 9 , 1 3 }），顶点2 覆盖一个( { 4 } )，顶点3覆盖一个（{ 1 0 }），顶点1 6覆盖零个，顶点1 7覆盖四个{ 4 , 9 , 1 0 , 11 }。下一步可选择1或1 7加入A' 。若选择顶点1，则顶点{ 1 0 , 11} 仍然未被覆盖，此时顶点1，2，1 6不覆盖其中任意一个，顶点3覆盖一个，顶点1 7覆盖两个，因此选择顶点1 7，至此所有顶点已被覆盖，得A' = { 1 6 , 1 , 1 7 }。 图1 - 7给出了贪婪覆盖启发式方法的伪代码，可以证明： 1) 当且仅当初始的二分图没有覆盖时，算法找不到覆盖；2) 启发式方法可能找不到二分图的最小覆盖。 1. 数据结构的选取及复杂性分析 为实现图13 - 7的算法，需要选择A' 的描述方法及考虑如何记录A中节点所能覆盖的B中未覆盖节点的数目。由于对集合A' 仅使用加法运算，则可用一维整型数组C来描述A '，用m 来记录A' 中元素个数。将A' 中的成员记录在C[ 0 :m-1] 中。对于A中顶点i，令N e wi 为i 所能覆盖的B中未覆盖的顶点数目。逐步选择N e wi 值最大的顶点。由于一些原来未被覆盖的顶点现在被覆盖了，因此还要修改各N e wi 值。在这种更新中，检查B中最近一次被V覆盖的顶点，令j 为这样的一个顶点，则A中所有覆盖j 的顶点的N e wi 值均减1。 例1-13 考察图1 - 6，初始时(N e w1 , N e w2 , N e w3 , N e w16 , N e w17 ) = ( 6 , 4 , 5 , 6 , 4 )。假设在例1 - 1 2中，第一步选择顶点1 6，为更新N e wi 的值检查B中所有最近被覆盖的顶点，这些顶点为5 , 6 , 8 , 1 2 , 1 4和1 5。当检查顶点5时，将顶点2和1 6的N e wi 值分别减1，因为顶点5不再是被顶点2和1 6覆盖的未覆盖节点；当检查顶点6时，顶点1 , 2 ,和1 6的相应值分别减1；同样，检查顶点8时，1，2，3和1 6的值分别减1；当检查完所有最近被覆盖的顶点，得到的N e wi 值为（4，1，0，4）。下一步选择顶点1，最新被覆盖的顶点为4，7，9和1 3；检查顶点4时，N e w1 , N e w2, 和N e w1 7 的值减1；检查顶点7时，N e w1 的值减1，因为顶点1是覆盖7的唯一顶点。 为了实现顶点选取的过程，需要知道N e wi 的值及已被覆盖的顶点。可利用一个二维数组来达到这个目的，N e w是一个整型数组，New[i] 即等于N e wi，且c o v为一个布尔数组。若顶点i未被覆盖则c o v [ i ]等于f a l s e，否则c o v [ i ]为t r u e。现将图1 - 7的伪代码进行细化得到图1 - 8。 m=0; //当前覆盖的大小 对于A中的所有i，New[i]=Degree[i] 对于B中的所有i，C o v [ i ] = f a l s e while (对于A中的某些i,New[i]>0) { 设v是具有最大的N e w [ i ]的顶点； C [ m + + ] = v ; for ( 所有邻接于v的顶点j) { if (!Cov[j]) { Cov[j]= true; 对于所有邻接于j的顶点，使其N e w [ k ]减1 } } } if (有些顶点未被覆盖) 失败 else 找到一个覆盖 图1-8 图1-7的细化 更新N e w的时间为O (e)，其中e 为二分图中边的数目。若使用邻接矩阵，则需花(n2 ) 的时间来寻找图中的边，若用邻接链表，则需(n+e) 的时间。实际更新时间根据描述方法的不同为O