2022年贪心算法 .pdf

贪心算法学习收藏一、贪心策略的定义【定义 1】贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。其实，从贪心策略 一词我们便可以看出，贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心策略可以得到最优解或较优解。二、贪心算法的特点通过上文的介绍，可能有人会问：贪心算法有什么样的特点呢？我认为，适用于贪心算法解决的问题应具有以下2 个特点：1、贪心选择性质：所谓贪心选择性质是指应用同一规则f，将原问题变为一个相似的、但规模更小的子问题、而后的每一步都是当前看似最佳的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。从全局来看，运用贪心策略解决的问题在程序的运行过程中无回溯过程。关于贪心选择性质，读者可在后文给出的贪心策略状态空间图中得到深刻地体会。2、局部最优解：我们通过特点2 向大家介绍了贪心策略的数学描述。由于运用贪心策略解题在每一次都取得了最优解，但能够保证局部最优解得不一定是贪心算法。如大家所熟悉得动态规划算法就可以满足局部最优解，在广度优先搜索（BFS）中的解题过程亦可以满足局部最优解。在遇到具体问题时，往往分不清哪些题该用贪心策略求解，哪些题该用动态规划法求解。在此，我们对两种解题策略进行比较。名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 14 页 -三、贪心策略的理论基础-矩阵胚名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 14 页 -正如前文所说的那样，贪心策略是最接近人类认知思维的一种解题策略。但是，越是显而易见的方法往往越难以证明。下面我们就来介绍贪心策略的理论-矩阵胚。矩阵胚 理论是一种能够确定贪心策略何时能够产生最优解的理论，虽然这套理论还很不完善，但在求解最优化问题时发挥着越来越重要的作用。【定义 3】矩阵胚是一个序对M=S，I，其中 S 是一个有序非空集合，I 是 S的一个非空子集，成为S的一个独立子集。如果 M 是一个 N M 的矩阵的话，即:若 M是无向图G的矩阵胚的话，则S为图的边集，I 是所有构成森林的一组边的子集。如果对 S的每一个元素X（XS）赋予一个正的权值W（X），则称矩阵胚M=（S，I）为一个加权矩阵胚。适宜于用贪心策略来求解的许多问题都可以归结为在加权矩阵胚中找一个具有最大权值的独立子集的问题，即给定一个加权矩阵胚，M=（S，I），若能找出一个独立且具有最大可能权值的子集A，且 A 不被 M中比它更大的独立子集所包含，那么A为最优子集，也是一个最大的独立子集。矩阵胚理论对于我们判断贪心策略是否适用于某一复杂问题是十分有效的。四、几种典型的贪心算法贪心策略在图论中有着极其重要的应用。诸如 Kruskal、Prim、Dijkstra 等体现“贪心”思想的图形算法更是广泛地应用于树与图的处理。下面就分别来介绍Kruskal 算法、Prim 算法和Dijkstra 算法。.、库鲁斯卡尔（Kruskal）算法【定义 4】设图 G=（V，E）是一简单连通图，V=n,E=m,每条边 ei 都给以权 W，W 假定是边 e 的长度（其他的也可以），i=1，2，3，.，m。求图 G的总长度最短的树，这就是最短树问题。kruskal 算法的基本思想是：首先将赋权图G 的边按权的升序排列，不失一般性为：e,e,.,e。其中 W W，然后在不构成回路的条件下择优取进权最小的边。其流程如下：名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 14 页 -（1）对属于 E 的边进行排序得e e.e。（2）初始化操作w0，T，k0，t0；（3）若 t=n-1，则转（6），否则转（4）（4）若 Te 构成一回路，则作【kk+1，转（4）】（5）TT e，w w+w，tt+1，k k+1，转（3）（6）输出 T，w，停止。下面我们对这个算法的合理性进行证明。设在最短树中，有边v，v，连接两顶点v，v，边 v，v 的权为wp，若 v，v 加入到树中不能保证树的总长度最短，那么一定有另一条边v，v 或另两条边 v，v、v，v，且 wwp 或 w+wvk，vjwp，因为 v，v、v，v 不在最短树中，可知当 v，v、v，v 加入到树中时已构成回路，此时程序终止。因为 v，v T，v，v T 且 wvI，vk+wvk，vjw p，与程序流程矛盾。下面给出C语言描述的kruskal算法:#define MAXE typedef struct int u;/边的起始顶点 int v;/边的终止顶点 int w;/边的权值 Edge;void kruskal(Edge E,int n,int e)/边的权值从小到大排列 int i,j,m1,m2,sn1,sn2,k;int vsetMAXV;for(i=0;in;i+)vseti=i;k=1;j=0;while(kn)名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 14 页 -m1=Ej.u;m2=Ej.v;sn1=vsetm1;sn2=vsetm2;if(sn1!=sn2)/两顶点属于不同的集合,是最小生成树的一条边 输出这条边;k+;for(i=0;in;i+)if(vseti=sn2)vseti=sn1;j+;kruskal算法对边的稀疏图比较合适,时间复杂度为o(elog2e),e是边数,与顶点无关.、普林（Prim）算法：Kruskal 算法采取在不构成回路的条件下，优先选择长度最短的边作为最短树的边，而Prim 则是采取了另一种贪心策略。已知图 G=（V，E），V=v，v，v，.，v，D=（d）是图 G的矩阵，若v，v E，则令 dij=，并假定dij=Prim 算法的基本思想是：从某一顶点（设为v）开始，令 Sv，求 VS 中点与 S 中点 v 距离最短的点，即从矩阵D 的第一行元素中找到最小的元素，设为d，则令 SS v ，继续求VS 中点与 S 的距离最短的点，设为v,则令 SS v ，继续以上的步骤，直到 n 个顶点用n-1 条边连接起来为止。流程如下：(1)初始化操作：，（1）-1，从到作【（）1，（）】，1(2)若 n,则作【输出T,结束】否则作【min，从到作名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 14 页 -【若 q(i)min 则作【minq(i)hj】(3)，p(h),q(h)-1(4)从到作【若 d q(j)则作【q(j)d,p(j)h】(5)，转(2)算法中数组p（i）是用以记录和v 点最接近的属于S 的点，q（i）则是记录了v 点和 S中点的最短距离，q（i）=-1 用以表示v 点已进入集合S。算法中第四步：v 点进入 S 后，对不属于 S 中的点 vj 的 p（j）和 q（j）进行适当调整，使之分别记录了所有属于S 且和 S 距离最短的点和最短的距离，点v,v，v 分别用 1，2，,n 表示。下面给出C 语言描述的prim 算法:void prim(int costMAXV,int n,int v)/v是起始顶点 int lowcostMAXV,min;int closestMAXV,i,j,k;/*closesti表示 U 中的一个顶点,该顶点和V-U 中的一个顶点构成的边(i,closesei)具有最小的权 */lowcosti表示边(i,closeti)的权值 for(i=0;in;i+)lowcosti=costvi;closesti=v;for(i=1;in;i+)min=INF;for(j=0;jn;j+)/在(V-U)中找出离U最近的顶点K.if(lowcostj!=0&lowcostjk;lowcostk=0;/标记 k 已经加入U;for(j=0;jn;j+)/修改数组lowcost和 closest if(costkj!=0&costkjdistu+aux,则distx=distu+aux，prevx=u,转 S2对于具有n 个顶点和e 条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要O(n)时间。这个循环需要执行n-1 次，所以完成循环需要O(n2)时间。算法的其余部分所需要时间不超过O(n2)。五、贪心策略在P类问题求解中的应用在现实世界中，我们可以将问题分为两大类。其中一类被称为P 类问题，它存在有效算法，可求得最优解；另一类问题被称为NPC 类问题，这类问题到目前为止人们尚未找到名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 14 页 -求得最优解的有效算法，这就需要每一位程序设计人员根据自己对题目的理解设计出求较优解的方法。下面我们着重分析贪心策略在求解P 类问题中的应用。在现实生活中，P 类问题是十分有限的，而NPC 类问题则是普遍的、广泛的。例 1删数问题试题描述键盘输入一个高精度的正整数N(不超过 240 位)，去掉其中任意S 个数字后剩下的数字按左右次序组成一个新的正整数。对给定的N 和 S，寻找一种删数规则使得剩下得数字组成的新数最小。试题背景此题出自 NOI94试题分析这是一道运用贪心策略求解的典型问题。此题所需处理的数据从表面上看是一个整数。其实，大家通过对此题得深入分析便知：本题所给出的高精度正整数在具体做题时将它看作由若干个数字所组成的一串数，这是求解本题的一个重要突破。这样便建立起了贪心策略的数学描述。每次删除一个数字,选择一个使剩下的数最小的数字作为删除对象,之所以选择这样”贪心”的操作,是因为删S个数字的全局最优解包含了删一个数字的子问题的最优解.当 S=1时,在 N 中删除哪一个数字能达到最小的目的?从左到右每相邻的两个数字比较:若出现左边大于右边,则删除左边的大数字.若不出现降序排列,即所有数字全部升序,则删除最右边的大数字.当 S1,按上述操作一个一个删除,删除一个达到最小后,再从头即从串首开始,删除第 2个,依次分解为S 次完成.若删除不到S 个后已无左边大于右边的减序,则停止删除操作,打印剩下串的左边L-S 个数字即可(相当于删除了若干个最右边的大数字,这里 L 为原数字 N 的位数).附源程序:#include#include using namespace std;int main()string n;int s,i,x,l,m;while(cinns)i=-1,m=0,x=0;l=n.length();名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 14 页 -while(xni+1)/出现递减,删除递减的首数字 n=n.erase(i,1);x+;/x统计删除数字的个数 i=-1;/从头开始查递减区间 if(i=l-x-2&xs)m=1;/已经无递减区间,m=1 脱离循环 coutn.substr(0,l-s+x);/只打印剩下的左边l-(s-x)个数字 例 2数列极差问题试题描述在黑板上写了N 个正整数作成的一个数列，进行如下操作：每一次擦去其中的两个数 a 和 b，然后在数列中加入一个数ab+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的max，最小的为min，则该数列的极差定义为M=max-min。编程任务：对于给定的数列，编程计算出极差M。试题分析当看到此题时，我们会发现求max 与求 min 是两个相似的过程。若我们把求解max 与 min 的过程分开，着重探讨求max 的问题。下面我们以求max 为例来讨论此题用贪心策略求解的合理性。讨论：假设经（3）次变换后得到个数：a,b,max（max），其中 max是（）个数经（）次变换后所得的最大值，此时有两种求值方式，设其所求值分别为，则有：（）max，（max）+所以 max若经（）次变换后所得的个数为：，（）且不为（）次变换后的最大值，名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 14 页 -即 max则此时所求得的最大值为：（+）+此时 （+）（max）所以此时不为最优解。所以若使第（）次变换后所得值最大，必使（）次变换后所得值最大（符合贪心策略的特点2），在进行第次变换时，只需取在进行（）次变换后所得数列中的两最小数，施加操作：+1，即可（符合贪心策略特点 1），因此此题可用贪心策略求解。讨论完毕。在求时，我们只需在每次变换的数列中找到两个最大数，施加作用：+，-即可原理同上例最优乘车问题试题描述城是一个旅游胜地，每年都有成千上万的人前来观光为方便游客，巴士公司在各个旅游景点及宾馆、饭店等地都设置了巴士站，并开通了一些单向巴士线路。每条单向巴士线路从某个巴士站出发，依次途径若干个巴士站，最终到达终点巴士站。阿昌最近到城旅游，住在饭店。他很想去公园游玩。听人说，从饭店到公园可能有也可能没有直通巴士。如果没有，就要换乘不同线路的单向巴士，还有可能无法乘巴士到达。现在用整数，.，给城的所有巴士站编号，约定饭店的巴士站编号为，公园巴士站的编号为。写一个程序，帮助阿昌寻找一个最优乘车方案，使他在从饭店到公园的过程中换车的次数最少。试题背景出自试题分析此题看上去很像一道搜索问题。在搜索问题中，我们所求的使经过车站数最少的方案，而本题所求解的使换车次数最少的方案。这两种情况的解是否完全相同呢？我们来看一个实例：如图 5 所示：共有个车站（分别为、），共有条巴士线（线路：；线路：；线路：）。此时要使换车次数最少，应乘坐线路的巴士，路线为：，换车次数为；要使途经车站数最少，乘坐线路应为，换车次数为。所以说使换车次数最少的路线和使途经车站数最少的方案不一定相同。这使不能用搜索发求解此问题的原因之一。名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 14 页 -原因之二，来自对数学模型的分析。我们根据题中所给数据来建立一个图后会发现该图中存在大量的环，因而不适合用搜索法求解。其实，此题完全可以套用上文所提到的Dijkstra 算法来求解。输入数据：输入文件 INPUT.TXT。文件的第 1 行是一个数字 M（1M100）表示开通了 M 条单向巴士线路，第2 行是一个数字 N（1N500），表示共有N 个车站。从第 3 行到第 M+2 行依次给出了第一条到第M 条巴士线路的信息。其中第 i+2 行给出的是第 i 条巴士线路的信息，从左至右依次按行行驶顺序给出了该线路上的所有站点，相邻两个站号之间用一个空格隔开。输出数据：输出文件是 OUTPUT.TXT。文件只有一行，为最少换车次数（在0，1，M-1 中取值），0 表示不需换车即可达到。如果无法乘车达到S 公园，则输出 NO。源程序:#include#include#includeusing namespace std;int m,n;/m为开通的单向巴士线路数,n 为车站总数int result502;/到某车站的最少换车数int num50252;/从某车站可达的所有车站序列int sum502;/从某车站可达的车站总数bool check502;/某车站是否已扩展完const int INF=600;int main()int i,j,c,a,b,d,min;int data52;char ch;while(cinmn)memset(sum,0,sizeof(sum);memset(num,0,sizeof(num);for(i=0;idataj;ch=getchar();if(ch!=)break;for(c=1;c=j-1;c+)for(d=c+1;d=j;d+)sumdatac+;numdatacsumdatac=datad;memset(result,-1,sizeof(result);memset(check,0,sizeof(check);result1=0;for(c=1;c=sum1;c+)resultnum1c=0;b=num11;do checkb=1;/某车站已扩展完 for(c=1;c=sumb;c+)if(resultnumbc=-1)resultnumbc=resultb+1;min=501;resultmin=INF;/*贪心选择目前经过最小换乘数就可以到达的某车站*/for(c=1;c=n;c+)if(resultc!=-1&resultcresultmin&checkc=0)min=c;b=min;while(resultn=-1)&(min!=501);/min=501表示目前所有车站已扩展完 if(resultn=-1)/站点 n无法到达 coutNOendl;else coutresultnendl;return 0;例最佳浏览路线问题名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 14 页 -试题描述 某旅游区的街道成网格状（见图），其中东西向的街道都是旅游街，南北向的街道都是林荫道。由于游客众多，旅游街被规定为单行道。游客在旅游街上只能从西向东走，在林荫道上既可以由南向北走，也可以从北向南走。阿隆想到这个旅游区游玩。他的好友阿福给了他一些建议，用分值表示所有旅游街相邻两个路口之间的道路值得浏览得程度，分值从-到的整数，所有林荫道不打分。所有分值不可能全是负值。例如下图是被打过分的某旅游区的街道图：阿隆可以从任一路口开始浏览，在任一路口结束浏览。请你写一个程序，帮助阿隆寻找一条最佳的浏览路线，使得这条路线的所有分值总和最大。试题背景这道题同样出自，国际大学生程序设计竞赛的第二题（吉尔的又一个骑车问题）与本题是属于本质相同的题目。试题分析由于林荫道不打分，也就是说，无论游客在林荫道中怎么走，都不会影响得分。因题可知，若游客需经过某一列的旅游街，则他一定要经过这一列的条旅游街中分值最大的一条，才会使他所经路线的总分值最大。这是一种贪心策略。贪心策略的目的是降维，使题目所给出的一个矩阵便为一个数列。下一步便是如何对这个数列进行处理。在这一步，很多人用动态规划法求解，这种算法的时间复杂度为（），当林荫道较多时，效率明显下降。其实在这一步我们同样可以采用贪心法求解。这时的时间复杂度为（）。输入数据：输入文件是 INPUT.TXT。文件的第一行是两个整数M 和 N，之间用一个空格符隔开，M 表示有多少条旅游街（1M100），N 表示有多少条林荫道（1N20000）。接下里的 M 行依次给出了由北向南每条旅游街的分值信息。每行有 N-1 个整数，依次表示了自西向东旅游街每一小段的分值。同一行相邻两个数之间用一个空格隔开。输出文件：输出文件是 OUTPUT.TXT。文件只有一行，是一个整数，表示你的程序找到的最佳浏览路线的总分值。源程序:#include名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 14 页 -#includeusing namespace std;int m,n;/m 为旅游街数，n为林荫道数int data20000;/data是由相邻两条林荫道所分隔的旅游街的最大分值int MaxSum(int n,int*a)/求最大子段和函数 int sum=0;int b=0;for(int i=1;isum)sum=b;if(bmn)/*读取每一段旅游街的分值，并选择读取每一段旅游街的分值，并选择到目前位置所在列的最大分值记入数组data*/for(i=1;idatai;for(i=2;i=m;i+)for(j=1;jc;if(cdataj)dataj=c;coutMaxSum(n-1,data)endl;return 0;名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 14 页 -