技术参考贪心策略

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,贪心策略 特点 理论基础 应用,1,本讲着重探讨的是贪心策略的数学模型、理论基础（矩形胚结构）和贪心策略的特点。（贪心选择性质和局部最优解）介绍了3种体现贪心思想的图形算法：Dijkstra算法、Prim算法和Kruskal算法，并着重给出了近几年来在各级各类程序设计竞赛中出现的一些题目。,2,一、贪心策略的定义,【定义1】,贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。,3,二、贪心算法的特点,1,、贪心选择性质：,所谓贪心选择性质是指应用同一规则f，将原问题变为一个相似的、但规模更小的子问题、而后的每一步都是当前看似最佳的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。从全局来看，运用贪心策略解决的问题在程序的运行过程中无回溯过程。,4,2,、局部最优解：,我们通过特点2向大家介绍了贪心策略的数学描述。由于运用贪心策略解题在每一次都取得了最优解，但能够保证局部最优解得不一定是贪心算法。如大家所熟悉得动态规划算法就可以满足局部最优解，在广度优先搜索（BFS）中的解题过程亦可以满足局部最优解。,在遇到具体问题时，许多选手往往分不清哪些题该用贪心策略求解，哪些题该用动态规划法求解。在此，我们对两种解题策略进行比较。,5,6,7,8,三、,贪心策略的理论基础-矩阵胚,正如前文所说的那样，贪心策略是最接近人类认知思维的一种解题策略。但是，越是显而易见的方法往往越难以证明。下面我们就来介绍贪心策略的理论-矩阵胚。矩阵胚理论是一种能够确定贪心策略何时能够产生最优解的理论，虽然这套理论还很不完善，但在求解最优化问题时发挥着越来越重要的作用。,9,【定义,3,】,矩阵胚是一个序对,M=S,，,I,，其中,S,是一个有序非空集合，,I,是,S,的一个非空子集，成为,S,的一个独立子集。,如果,M,是一个,NM,的矩阵的话，即,10,若M是无向图G的矩阵胚的话，则S为图的边集，I是所有构成森林的一组边的子集。如果对S的每一个元素X（XS）赋予一个正的权值W（X），则称矩阵胚M=（S，I）为一个加权矩阵胚。,适宜于用贪心策略来求解的许多问题都可以归结为在加权矩阵胚中找一个具有最大权值的独立子集的问题，即给定一个加权矩阵胚，M=（S，I），若能找出一个独立且具有最大可能权值的子集A，且A不被M中比它更大的独立子集所包含，那么A为最优子集，也是一个最大的独立子集。,针对绝大多数的信息学问题，只要它具备了,矩阵胚,的结构，便可用贪心策略求解。矩阵胚理论对于我们判断贪心策略是否适用于某一复杂问题是十分有效的。,11,四,、,几种典型的贪心算法,贪心策略在图论中有着极其重要的应用。诸如Kruskal、 Prim、 Dijkstra等体现贪心思想的图形算法更是广泛地应用于树与图的处理。下面就分别来介绍Kruskal算法、Prim算法和Dijkstra算法。,12,、库鲁斯卡尔（,Kruskal,）算法,13,14,15,五、 贪心策略的应用,在现实世界中，我们可以将问题分为两大类。其中一类被称为P类问题，它存在有效算法，可求得最优解；另一类问题被称为NPC类问题，这类问题到目前为止人们尚未找到求得最优解的有效算法，这就需要每一位程序设计人员根据自己对题目的理解设计出求较优解的方法。下面我们着重分析贪心策略在求解P类问题中的应用。,16,贪心策略在求P类最优解问题中的应用,在现实生活中，P类问题是十分有限的，而NPC类问题则是普遍的、广泛的。在国际信息学奥林匹克竞赛的发展过程中，由于受到评测手段的限制，在1989年至1996年的8年赛事中，始终是以P类问题为主的，且只允许求最优解。在这些问题中，有的题目可以用贪心策略来直接求解，有的题目运用贪心策略后可以使问题得到极大的简化，使得程序对大信息量的处理提供了可能。,17,例1删数问题,试题描述,键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按左右次序组成一个新的正整数。对给定的N和S，寻找一种删数规则使得剩下得数字组成的新数最小。,试题背景,此题出自NOI94,试题分析,这是一道运用贪心策略求解的典型问题。此题所需处理的数据从表面上看是一个整数。其实，大家通过对此题得深入分析便知：本题所给出的高精度正整数在具体做题时将它看作由若干个数字所组成的一串数，这是求解本题的一个重要突破。这样便建立起了贪心策略的数学描述。,18,例,2,数列极差问题,试题描述,在黑板上写了,N,个正整数作成的一个数列，进行如下操作：每一次擦去其中的两个数,a,和,b,，然后在数列中加入一个数,ab+1,，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的,max,，最小的为,min,，则该数列的极差定义为,M=max-min,。,编程任务,：对于给定的数列，编程计算出极差,M,。,试题背景,这是,1997,年福建队选拔赛的一道题目。,19,试题分析,当看到此题时，我们会发现求,max,与求,min,是两个相似的过程。若我们把求解,max,与,min,的过程分开，着重探讨求,max,的问题。,下面我们以求,max,为例来讨论此题用贪心策略求解的合理性。,讨论：假设经（,3,）次变换后得到个数：,a,b,max,（,max,），其中,max,是（）个数经（）次变换后所得的最大值，此时有两种求值方式，设其所求值分别为，,，则有：,（）,max,，,（,max,）,+,所以,max,若经（）次变换后所得的个数为：，（,）且不为（）次变换后的最大值，即,max,则此时所求得的最大值为：,（,+,）,+,此时,（,+,）（,max,）所以此时不为最优解。,20,所以若使第（）次变换后所得值最大，必使（）次变换后所得值最大（符合贪心策略的特点,2,），在进行第次变换时，只需取在进行（）次变换后所得数列中的两最小数，施加操作：,+1,，,即可（符合贪心策略特点,1,），因此此题可用贪心策略求解。讨论完毕,在求时，我们只需在每次变换的数列中找到两个最大数，施加作用：,+,，,-,即可原理同上。,这是一道两次运用贪心策略解决的一道问题，它要求选手有较高的数学推理能力。,21,例最优乘车问题,试题描述,城是一个旅游胜地，每年都有成千上万的人前来观光为方便游客，巴士公司在各个旅游景点及宾馆、饭店等地都设置了巴士站，并开通了一些单向巴士线路。每条单向巴士线路从某个巴士站出发，依次途径若干个巴士站，最终到达终点巴士站。,阿昌最近到城旅游，住在饭店。他很想去公园游玩。听人说，从饭店到公园可能有也可能没有直通巴士。如果没有，就要换乘不同线路的单向巴士，还有可能无法乘巴士到达。,现在用整数，,.,，给城的所有巴士站编号，约定饭店的巴士站编号为，公园巴士站的编号为。,写一个程序，帮助阿昌寻找一个最优乘车方案，使他在从饭店到公园的过程中换车的次数最少。,22,试题背景,出自,试题分析,此题看上去很像一道搜索问题。在搜索问题中，我们所求的使经过车站数最少的方案，而本题所求解的使换车次数最少的方案。这两种情况的解是否完全相同呢？我们来看一个实例：,图 5,23,如图5所示：共有个车站（分别为、），共有条巴士线（线路：；线路：；线路：）。此时要使换车次数最少，应乘坐线路的巴士，路线为：，换车次数为；要使途经车站数最少，乘坐线路应为，换车次数为。所以说使换车次数最少的路线和使途经车站数最少的方案不一定相同。这使不能用搜索发求解此问题的原因之一。原因之二，来自对数学模型的分析。我们根据题中所给数据来建立一个图后会发现该图中存在大量的环，因而不适合用搜索法求解。题目分析到这里，我们可以发现此题与NOI93的求最长路径问题有相似之处。其实，此题完全可以套用上文所提到的Dijkstra算法来求解。,24,以上三道题只是使用了单一的贪心策略来求解的。而从近几年的信息学奥林匹克竞赛的命题方向上看，题目更加灵活，同时测试数据较大，规定的出解时间较短。在一些问题中，我们采用贪心策略对问题化简，从而使程序具有更高的效率。,25,试题描述,某旅游区的街道成网格状（见图），其中东西向的街道都是旅游街，南北向的街道都是林荫道。由于游客众多，旅游街被规定为单行道。游客在旅游街上只能从西向东走，在林荫道上既可以由南向北走，也可以从北向南走。,阿隆想到这个旅游区游玩。他的好友阿福给了他一些建议，用分值表示所有旅游街相邻两个路口之间的道路值得浏览得程度，分值从,-,到的整数，所有林荫道不打分。所有分值不可能全是负值,26,例如下图是被打过分的某旅游区的街道图：,阿隆可以从任一路口开始浏览，在任一路口结束浏览。请你写一个程序，帮助阿隆寻找一条最佳的浏览路线，使得这条路线的所有分值总和最大。,27,试题背景,这道题同样出自，国际大学生程序设计竞赛的第二题（吉尔的又一个骑车问题）与本题是属于本质相同的题目。,试题分析,由于林荫道不打分，也就是说，无论游客在林荫道中怎么走，都不会影响得分。因题可知，若游客需经过某一列的旅游街，则他一定要经过这一列的条旅游街中分值最大的一条，才会使他所经路线的总分值最大。这是一种贪心策略。贪心策略的目的是降维，使题目所给出的一个矩阵便为一个数列。下一步便是如何对这个数列进行处理。在这一步，很多人用动态规划法求解，这种算法的时间复杂度为（,2,），当林荫道较多时，效率明显下降。其实在这一步我们同样可以采用贪心法求解。这时的时间复杂度为（）。,28,贪心策略在求P类较优解问题中的应用,正如其他学科奥林匹克竞赛一样，国际信息学奥赛的发展同样经历了一个逐步成熟的发展过程。回顾十余年赛事的发展，我们不妨将国际信息学奥赛的发展分为两个阶段：第一阶段是,1989-1996,年，这一时期奥赛题目的特点是：试题全部为,P,类问题，且只允许求最优解，题目的设计强调对选手基本算法的掌握。第二阶段为,1997,年至今。在南非举行的,IOI97,中，命题方向一举突破传统模式，,NPC,类问题在竞赛中大量出现，每道题目到具有一定的实际背景，引进了崭新的程序评测机制。在求解,P,类问题时允许得出较优解并得到相应的分数。这些变化无疑更好地考察了选手的综合素质。在对,P,类较优解问题的求解过程中，贪心策略无疑扮演着重要角色。,IOI97,中的障碍物探测器问题便是运用贪心策略来求得较优解的,P,类问题。,29,例,5,障碍物探测器问题,试题描述,有一个登陆舱（,POD,），里面装有许多障碍物探测车（,MEV,），将在火星表面着陆，着陆后，探测车离开登陆舱向相距不远的先期到达的传送器（,Transmitter,）移动。,MEV,一边移动，采集岩石（,ROCK,）标本，岩石由第一个访问到它的,MEV,所采集，每块岩石只能被采集一次，但是这以后，其他,MEV,可以从该处通过。探测车,MEV,不能通过有障碍的地面。,本题限定探测车,MEV,只能沿着格子向南或向东从登陆处向传送器,transmitter,移动，允许多个探测车,MEV,在同一时间占据同一位置。,警告：,如果某个探测车,MEV,在到达传送器以前不能在继续合法前进时，则车中的石块必定不可挽回地全部丢失。,30,任务：,计算机探测车的每一步移动，使其送到传送器的岩石标本的数量尽可能多。这两项都做到会使你的得分最高。,输入：,火星表面上登陆舱,POD,和传送器之间的位置用网格,P,和,Q,表示，登陆舱,POD,的位置总是在（,1,，,1,）点，传送器的位置总是在（,P,，,Q,）点。,火星上的不同表面用三中不同的数字符号来表示：,0,代表平坦无障碍,1,代表障碍,2,代表石块,输入文件的第一行为探测车的个数，第二行为,P,的值，第三行为,Q,的值。接下来的,Q,行为一个,QP,的矩阵。,输出：,表示,MEV,移向,transmitter,的行动序列。每行包含探测车号和一个数，,0,或,1,，这里,0,表示向南移动，,1,表示向东移动。,31,得分：,分数的计算将根据收集的岩石样本（取到传送器上）的数目，,MEV,到达传送器和不到达传送器的数目有关,非法移动将导致求解无效，并记作零分，当,MEV,的障碍物上移动或移出网格，即视为非法。,得分,=,（收集的样品并取到传送器上的数目,+MEV,到达传送器上的数目,-MEV,没有到达传送器上的数目）与应得的最大的数目之比（,%,）,最高分为,100%,，最低分为,0%,32,就到这里吧！,33,