[算法介绍]贪心策略的特点与应用

Eastsun · 发表于 2005-8-27 12:48:00

[color=RED]四、贪心策略的理论基础--矩阵胚 [/color]
　　正如前文所说的那样，贪心策略是最接近人类认知思维的一种解题策略。但是，越是显而易见的方法往往越难以证明。下面我们就来介绍贪心策略的理论--矩阵胚。
　　"矩阵胚"理论是一种能够确定贪心策略何时能够产生最优解的理论，虽然这套理论还很不完善，但在求解最优化问题时发挥着越来越重要的作用。
　　【定义3】矩阵胚是一个序对M=[S，I] ，其中S是一个有序非空集合，I是S的一个非空子集，成为S的一个独立子集。
　　如果M是一个N×M的矩阵的话，即
　　若M是无向图G的矩阵胚的话，则S为图的边集，I是所有构成森林的一组边的子集。
　　如果对S的每一个元素X（X∈S）赋予一个正的权值W（X），则称矩阵胚M=（S，I）为一个加权矩阵胚。
　　适宜于用贪心策略来求解的许多问题都可以归结为在加权矩阵胚中找一个具有最大权值的独立子集的问题，即给定一个加权矩阵胚，M=（S，I），若能找出一个独立且具有最大可能权值的子集A，且A不被M中比它更大的独立子集所包含，那么A为最优子集，也是一个最大的独立子集。
　　我们认为，针对绝大多数的信息学问题，只要它具备了"矩阵胚"的结构，便可用贪心策略求解。矩阵胚理论对于我们判断贪心策略是否适用于某一复杂问题是十分有效的。
　　五、几种典型的贪心算法
　　贪心策略在图论中有着极其重要的应用。诸如Kruskal、 Prim、 Dijkstra等体现"贪心"思想的图形算法更是广泛地应用于树与图的处理。下面就分别来介绍Kruskal算法、Prim算法和Dijkstra算法。
　　Ⅰ、库鲁斯卡尔（Kruskal）算法

复制代码

Eastsun · 发表于 2005-8-27 12:50:00

六、贪心策略的应用
　　在现实世界中，我们可以将问题分为两大类。其中一类被称为P类问题，它存在有效算法，可求得最优解；另一类问题被称为NPC类问题，这类问题到目前为止人们尚未找到求得最优解的有效算法，这就需要每一位程序设计人员根据自己对题目的理解设计出求较优解的方法。下面我们着重分析贪心策略在求解P类问题中的应用。
　　§6.1 贪心策略在P类问题求解中的应用
　　§6.1.1 贪心策略在求P类最优解问题中的应用
　　
　　在现实生活中，P类问题是十分有限的，而NPC类问题则是普遍的、广泛的。在国际信息学奥林匹克竞赛的发展过程中，由于受到评测手段的限制，在1989年至1996年的8年赛事中，始终是以P类问题为主的，且只允许求最优解。在这些问题中，有的题目可以用贪心策略来直接求解，有的题目运用贪心策略后可以使问题得到极大的简化，使得程序对大信息量的处理提供了可能。
　　[例1]删数问题
　　试题描述键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按左右次序组成一个新的正整数。对给定的N和S，寻找一种删数规则使得剩下得数字组成的新数最小。
　　试题背景此题出自NOI94
　　试题分析这是一道运用贪心策略求解的典型问题。此题所需处理的数据从表面上看是一个整数。其实，大家通过对此题得深入分析便知：本题所给出的高精度正整数在具体做题时将它看作由若干个数字所组成的一串数，这是求解本题的一个重要突破。这样便建立起了贪心策略的数学描述。
　　[例2]数列极差问题
　　试题描述在黑板上写了N个正整数作成的一个数列，进行如下操作：每一次擦去其中的两个数a和b，然后在数列中加入一个数a×b+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的max，最小的为min，则该数列的极差定义为M=max-min。
　　编程任务：对于给定的数列，编程计算出极差M。
　　试题背景这是1997年福建队选拔赛的一道题目。
　　试题分析当看到此题时，我们会发现求max与求min是两个相似的过程。若我们把求解max与min的过程分开，着重探讨求max的问题。
　　下面我们以求max为例来讨论此题用贪心策略求解的合理性。
　　讨论：假设经（Ｎ－3）次变换后得到３个数：a,b,max＇（max＇≥ａ≥ｂ），其中max＇是（Ｎ－２）个数经（Ｎ－３）次ｆ变换后所得的最大值，此时有两种求值方式，设其所求值分别为，，则有：＝（ａ×ｂ＋１）×max＇＋１，＝（ａ×max＇＋１）×ｂ+１　所以　－＝max＇－ｂ≥０若经（Ｎ－２）次变换后所得的３个数为：ｍ，ａ，ｂ（ｍ≥ａ≥ｂ）且ｍ不为（Ｎ－２）次变换后的最大值，即ｍ＜max＇则此时所求得的最大值为：＝（ａ×ｂ+１）×ｍ+１　此时－＝（１+ａｂ）（max＇－ｍ）＞０　所以此时不为最优解。
　　所以若使第ｋ（１≤ｋ≤Ｎ－１）次变换后所得值最大，必使（ｋ－１）次变换后所得值最大（符合贪心策略的特点2），在进行第ｋ次变换时，只需取在进行（ｋ－１）次变换后所得数列中的两最小数ｐ，ｑ施加ｆ操作：ｐ←ｐ×ｑ+1，ｑ←∞即可（符合贪心策略特点1），因此此题可用贪心策略求解。讨论完毕。
　　在求ｍｉｎ时，我们只需在每次变换的数列中找到两个最大数ｐ，ｑ施加作用ｆ：ｐ←ｐ×ｑ+１，ｑ←-∞即可．原理同上。
　　这是一道两次运用贪心策略解决的一道问题，它要求选手有较高的数学推理能力。
　　［例３］最优乘车问题
　　试题描述　Ｈ城是一个旅游胜地，每年都有成千上万的人前来观光．为方便游客，巴士公司在各个旅游景点及宾馆、饭店等地都设置了巴士站，并开通了一些单向巴士线路。每条单向巴士线路从某个巴士站出发，依次途径若干个巴士站，最终到达终点巴士站。
　　阿昌最近到Ｈ城旅游，住在ＣＵＰ饭店。他很想去Ｓ公园游玩。听人说，从ＣＵＰ饭店到Ｓ公园可能有也可能没有直通巴士。如果没有，就要换乘不同线路的单向巴士，还有可能无法乘巴士到达。
　　现在用整数１，２，...，ｎ给Ｈ城的所有巴士站编号，约定ＣＵＰ饭店的巴士站编号为１，Ｓ公园巴士站的编号为Ｎ。
　　写一个程序，帮助阿昌寻找一个最优乘车方案，使他在从ＣＵＰ饭店到Ｓ公园的过程中换车的次数最少。
　　试题背景出自ＮＯＩ９７
　　试题分析此题看上去很像一道搜索问题。在搜索问题中，我们所求的使经过车站数最少的方案，而本题所求解的使换车次数最少的方案。这两种情况的解是否完全相同呢？我们来看一个实例：
　　　　　　　
　　　　　　　　　　　　　　　　　　　　图 5
　　如图5所示：共有５个车站（分别为ａ、ｂ、ｃ、ｄ、ｅ），　共有３条巴士线（线路Ａ：ａ→ｄ；线路Ｂ：ａ→ｂ→ｃ→ｅ；线路Ｃ：ｄ→ｅ）。此时要使换车次数最少，应乘坐线路Ｂ的巴士，路线为：ａ→ｂ→ｃ→ｅ，换车次数为０；要使途经车站数最少，乘坐线路应为ａ→ｄ→ｅ，换车次数为１。所以说使换车次数最少的路线和使途经车站数最少的方案不一定相同。这使不能用搜索发求解此问题的原因之一。
　　原因之二，来自对数学模型的分析。我们根据题中所给数据来建立一个图后会发现该图中存在大量的环，因而不适合用搜索法求解。
　　题目分析到这里，我们可以发现此题与NOI93的求最长路径问题有相似之处。其实，此题完全可以套用上文所提到的Dijkstra算法来求解。
　　以上三道题只是使用了单一的贪心策略来求解的。而从近几年的信息学奥林匹克竞赛的命题方向上看，题目更加灵活，同时测试数据较大，规定的出解时间较短。在一些问题中，我们采用贪心策略对问题化简，从而使程序具有更高的效率。

复制代码

Eastsun · 发表于 2005-8-27 12:53:00

［例４］最佳浏览路线问题
　　试题描述　某旅游区的街道成网格状（见图），其中东西向的街道都是旅游街，南北向的街道都是林荫道。由于游客众多，旅游街被规定为单行道。游客在旅游街上只能从西向东走，在林荫道上既可以由南向北走，也可以从北向南走。
　　阿隆想到这个旅游区游玩。他的好友阿福给了他一些建议，用分值表示所有旅游街相邻两个路口之间的道路值得浏览得程度，分值从-１００到１００的整数，所有林荫道不打分。所有分值不可能全是负值。
　　例如下图是被打过分的某旅游区的街道图：
　　　　　　　　　
　　
　　阿隆可以从任一路口开始浏览，在任一路口结束浏览。请你写一个程序，帮助阿隆寻找一条最佳的浏览路线，使得这条路线的所有分值总和最大。
　　试题背景　　这道题同样出自ＮＯＩ９７，＇９７国际大学生程序设计竞赛的第二题（吉尔的又一个骑车问题）与本题是属于本质相同的题目。
　　试题分析由于林荫道不打分，也就是说，无论游客在林荫道中怎么走，都不会影响得分。因题可知，若游客需经过某一列的旅游街，则他一定要经过这一列的Ｍ条旅游街中分值最大的一条，才会使他所经路线的总分值最大。这是一种贪心策略。贪心策略的目的是降维，使题目所给出的一个矩阵便为一个数列。下一步便是如何对这个数列进行处理。在这一步，很多人用动态规划法求解，这种算法的时间复杂度为Ｏ（ｎ2），当林荫道较多时，效率明显下降。其实在这一步我们同样可以采用贪心法求解。这时的时间复杂度为Ｏ（ｎ）。
　　§6.1.2 贪心策略在求P类较优解问题中的应用
　　正如其他学科奥林匹克竞赛一样，国际信息学奥赛的发展同样经历了一个逐步成熟的发展过程。回顾十余年赛事的发展，我们不妨将国际信息学奥赛的发展分为两个阶段：第一阶段是1989-1996年，这一时期奥赛题目的特点是：试题全部为P类问题，且只允许求最优解，题目的设计强调对选手基本算法的掌握。第二阶段为1997年至今。在南非举行的IOI97中，命题方向一举突破传统模式，NPC类问题在竞赛中大量出现，每道题目到具有一定的实际背景，引进了崭新的程序评测机制。在求解P类问题时允许得出较优解并得到相应的分数。这些变化无疑更好地考察了选手的综合素质。在对P类较优解问题的求解过程中，贪心策略无疑扮演着重要角色。IOI97中的障碍物探测器问题便是运用贪心策略来求得较优解的P类问题。
　　[例5] 障碍物探测器问题
　　试题描述有一个登陆舱（POD），里面装有许多障碍物探测车（MEV），将在火星表面着陆，着陆后，探测车离开登陆舱向相距不远的先期到达的传送器（Transmitter）移动。MEV一边移动，采集岩石（ROCK）标本，岩石由第一个访问到它的MEV所采集，每块岩石只能被采集一次，但是这以后，其他MEV可以从该处通过。探测车MEV不能通过有障碍的地面。
　　本题限定探测车MEV只能沿着格子向南或向东从登陆处向传送器transmitter移动，允许多个探测车MEV在同一时间占据同一位置。
　　警告：如果某个探测车MEV在到达传送器以前不能在继续合法前进时，则车中的石块必定不可挽回地全部丢失。
　　任务：计算机探测车的每一步移动，使其送到传送器的岩石标本的数量尽可能多。这两项都做到会使你的得分最高。
　　输入：火星表面上登陆舱POD和传送器之间的位置用网格P和Q表示，登陆舱POD的位置总是在（1，1）点，传送器的位置总是在（P，Q）点。
　　火星上的不同表面用三中不同的数字符号来表示：
　　● 0代表平坦无障碍
　　● 1代表障碍
　　● 2代表石块
　　输入文件的第一行为探测车的个数，第二行为P的值，第三行为Q的值。接下来的Q行为一个Q×P的矩阵。
　　输出：表示MEV移向transmitter的行动序列。每行包含探测车号和一个数，0或1，这里0表示向南移动，1表示向东移动。
　　得分：分数的计算将根据收集的岩石样本（取到传送器上）的数目，MEV到达传送器和不到达传送器的数目有关
　　● 非法移动将导致求解无效，并记作零分，当MEV的障碍物上移动或移出网格，即视为非法。
　　● 得分=（收集的样品并取到传送器上的数目+MEV到达传送器上的数目-MEV没有到达传送器上的数目）与应得的最大的数目之比（%）
　　● 最高分为100%，最低分为0%
　　试题背景 IOI'97中的第一试第一题。国际信息学奥赛中出现的第一道NPC类问题。1997年美国的探测器再次到达火星。火星及太空搜索引起了人们的广泛关注，此题便是以此为素材而创作的。
　　试题分析关于迷宫问题相信每一个参加信息学奥赛的选手都不会陌生。对于不同的迷宫，我们可用搜索策略或动态规划进行求解。在本题中，无论运用哪种解题策略均不能得到问题的最优解，我们的任务是合理选择一种解题策略，使我们运用该策略得到的较优解尽可能地接近最优解。我们先来看一个例子（如图7所示）。对于一个探测车而言，我们运用动态规划的方法使探测车经过岩石最多的一条路线便可得到问题的最优解（如图8所示），这时共可收集到岩石10个。　
　　　　　　　　
　　　　　　　　　　　　　　　
　　当有2个探测车时，我们让第2辆探测车在图8的基础上从地图的起点S行进至终点f（如图9所示），这时我们共收集到岩石15个。而实际上两辆探测车可收集到地图中的全部岩石（共16个），
　　　　　　　
　　当探测车数量为3时，我们可以收集到全部的16个岩石。
　　我们可让从起点出发的每一辆探测车都收集到尽可能多的岩石，这实际上是一种贪心策略。对于本题而言，贪心策略并不能保证所得结果全部为最优解，但由于每一辆探测车都收集尽可能多的岩石，而对于由计算机随机产生的测试数据而言，岩石是比较均匀地分布在地图中的，于是我们认为：
　　探测车收集岩石数≈探测车所游历的地图空间
　　让每一辆探测车收集尽可能多的岩石，也就是让探测车经过尽可能大的地图空间。所以在探测车数量逐渐增多时，所有探测车所经过的地图空间越多，收集到的岩石也就越多，此时也就越接近最优解。
此题是否存在最优解呢？其实，我们可以用网络流的算法来解决此题。但实践证明，用网络流算法去求解本题所占空间较大，编程复杂度较高且程序调试起来较为困难，因此在实际比赛中，在限定的时间内用贪心策略完成对题目的求借不失为上策。

复制代码

Eastsun · 发表于 2005-8-27 12:54:00

§6.2 关于运用贪心策略求解NPC类问题的讨论
　　正如前面所讲的那样，在南非举行的第九届国际奥林匹克信息学竞赛中首次引入了NPC类问题，在杭州举行的NOI98中引入了NOI发展史上的第一道NPC类问题--并行计算。可以说，NPC类问题正在日益引起人们的兴趣。它要求选手根据题意自己建立适当的模型，使程序的解尽量逼近最优解。目前，信息学竞赛所涉及到的少量NPC类问题主要是运用贪心策略或随机化算法去求较优解的。但是对于同一道NPC类问题来说，运用不同的贪心选择所求得的最优解是不同的，不同的贪心选择针对不同的测试数据所得解与最优解的逼近程度也是不同的。所以有关NPC类问题的众多特性以及哪些问题运用贪心策略求得的较优解逼近于最优解仍是需要我们花费大量精力去研究的。信息学奥林匹克的精华-激励创新也许在求解NPC类问题时会得到最大程度的体现。
　　七、总结
　　通过对贪心策略的分析，大家可以看出：贪心策略作为一种高效算法，广泛地应用与信息学奥林匹克竞赛中。即使表面上看起来与贪心策略关系甚微的题目，运用贪心算法也可使程序的运行效率大大提高。因此，深刻理解贪心策略的数学模型、特点、理论基础、尤其是运用其基本思想解决具体问题是十分重要的。希望本文能给参赛选手以一定的启发。
　　【附录】
　　【参考书目】
　　１　《实用算法的分析与程序设计》
　　　　吴文虎，王健德编著，电子工业出版社，ISBN 7-5053-4402-1
　　２　《计算机算法导引》
　　　　卢开澄编著，清华大学出版社，ISBN 7-302-02277-1
　　3、《国际大学生程序设计竞赛试题解析》
　　　　王建德，柴晓路编著，复旦大学出饭社 ISBN 7-309-02141-X/T·210
　　【部分试题及源程序】
　　1、吉尔的又一个乘车问题：
　　Input file:jill.in
　　Jill likes to ride her bicycle, but since the pretty city of Greenhills where she lives has grown, Jill often uses the excellent public bus system for part of her journey. She has a folding bicycle which she carries with her when she uses the bus for the first part of her trip. She follows the bus route until she reaches her destination of she comes to a part of the city she does not like. In the latter event she will board the bus to finish her trip.
　　Through years of experience, Jill has rated each road on an integer scale of "niceness". Positive niceness values indicate roads Jill likes; negative values are used for roads she does not like. Jill plans where to leave the bus and start bicycling, as well as where to stop bicycling and re-join the bus, so that the sum of niceness values of the roads she bicycles on is maximized. This means that she will sometimes cycle along a road she does not like, provided that it joins up two other parts of her journey involving roads she likes enough to compensate. It may be that no part of the route if suitable for cycling so that Jill takes the bus for its entire route. Conversely, it may be that the whole route is so nice Jill will not use the bus at all.
　　Since there are many different bus routes, each with several stops at which Jill could leave or enter the bus, she feels that a computer program could help her identify the best part to cycle for each bus route.
　　INPUT
　　The input file contains information on several bus routes. The first line of the file is a single integer b representing the number of route descriptions in the file. The identifier for each route (r) is the sequence number within the data files,1≤r≤b. Each route description begins with the number of stops on the route : an integer s, 2≤s≤20,000 on a line by itself. The number of stops is followed by s-1 lines, each line i(1≤i≤s) is an integer ni representing Jill's assessment of the niceness of the road between the two stops i and i+1.
　　OUTPUT
　　For each route r in the input file, your program should identify the beginning bus stop i and the ending bus stop j that identify the segment of the route which yields the maximal sum of niceness m=ni+ni+1+…+nj-1.If more than one segment is maximally nice, choose the one with longest cycle ride(largest j-i). To break ties in longest maximal segments, choose the segment that begins with the earliest stop(lowest i).For each route r in the input file, print a line in the form:
The nicest part of route r is between stops i AND j.
　　However, if the maximal sum is not positive, your program should print:
Route r has no nice parts.
　　INPUT SAMPLE
　　3
　　3
　- 1
　6
　10
4
5
　4
3
　4
　4
4
4
　　- 5
4
2
3
4
　　OUTPUT SAMPLE
　　The nicest part of route 1 is between stops 2 and 3
　　The nicest part of route 2 if between stops 3 and 9
　　Route 3 has no nice parts
2、求最长路径问题（NOI93）：
　　对一个不存在回路的有向图，编程求出途经结点数最多的一条路径。有向图存放在一个文本文件中，第0行为一个数字，为该图的结点总数N，其下还有N行，每行有N个非0即1的数字。若第i行第j列的数字为1，则表示结点i到结点j存在由i指向j的边，否则该数为0。
　　3、删数问题的源程序：
　　输入数据：一个高精度正整数N，所删除的数字个数S。
　　输出数据：去掉的数字的位置和组成的新的正整数。
　　Program Delete_digit;
　　Var n:string;{n是由键盘输入的高精度正整数}
　　　　s,a,b,c:byte;{s是所要删除的数字的个数}
　　　　data:array[1..200] of 0..9; {记录删除的数字所在位置}
　　begin
　　　readln(n);
　　　readln(s);
　　　for a:=1 to s do
　　　　for b:=1 to length(n) do if n[ b]>n[b+1] then {贪心选择}
　　　　begin
　　　　　delete(n,b,1);
　　　　　data[a]:=b+a-1; {记录所删除的数字的位置}
　　　　　break;
　　　　end;
　　　while n[1]='0' do delete(n,1,1); {将字符串首的若干个"0"去掉}
　　　writeln(n);
　　　for a:=1 to s do writeln(data[a],' ');
　　　end.
　　4、最优乘车问题
　　输入数据：输入文件INPUT.TXT。文件的第行是一个数字M（1≤M≤100）表示开通了M条单向巴士线路，第2行是一个数字N（1<N≤500），表示共有N个车站。从第3行到第M+2行依次给出了第一条到第M条巴士线路的信息。其中第i+2行给出的是第i条巴士线路的信息，从左至右依次按行行驶顺序给出了该线路上的所有站点，相邻两个站号之间用一个空格隔开。
　　输出数据：输出文件是OUTPUT.TXT。文件只有一行，为最少换车次数（在0，1，…，M-1中取值），0表示不需换车即可达到。如果无法乘车达到S公园，则输出"NO"。
　　Program Travel;
　　var m:1..100; {m为开通的单向巴士线路数}
　　　　n:1..500; {n为车站总数}
　　　　result:array[1..501] of -1..100; {到某车站的最少换车数}
　　　　num:array[1..500,1..50] of 1..500; {从某车站可达的所有车站序列}
　　　　sum:array[1..500] of 0..50; {从某车站可达的车站总数}
　　　　check:array[1..500] of Boolean; {某车站是否已扩展完}
　　Procedure Init;
　　var f1:text;
　　　　a,b,c,d:byte;
　　　　data:array[1..100] of 0..100;
　　begin
　　　assign(f1,'input.txt');
　　　reset(f1);
　　　readln(f1,m);
　　　readln(f1,n);
　　　result[501]:=100;
　　　for a:=1 to m do
　　　begin
　　　　for b:=1 to 100 do data[ b]:=0;
　　　　b:=0;
　　　　repeat
　　　　　inc(b);
　　　　　read(f1,data[ b]);
　　　　until eoln(f1);
　　　　for c:=1 to b-1 do
　　　　　for d:=c+1 to b do
　　　　　begin
　　　　　　inc(sum[data[c]]);
　　　　　　num[data[c],sum[data[c]]]:=data[d];
　　　　　end;
　　　end;
　　end;
　　Procedure Done;
　　var min,a,b,c,total:integer;
　　begin
　　　fillchar(result,sizeof(result),-1);
　　　result[1]:=0;
　　　for c:=1 to sum[1] do result[num[1,c]]:=0;
　　　b:=data[1,1];
　　　repeat
　　　　for c:=1 to sum[ b] do
　　　　　if (result[num[b,c]]=-1) then result[num[b,c]]:=result[ b]+1;
　　　　min:=501;
　　　　for c:=1 to n do if (result[c]<>-1) and (result[c]<result[min])
　　　　　　　　　then min:=c;
　　　　b:=min;
　　　until result[n]<>-1;
　　　writeln(result[n]);{到达S公园的最少换车次数}
　　end;
　　begin
　　　Init;
　　end.
　　5、最佳游览路线问题
　　输入数据：输入文件是INPUT.TXT。文件的第一行是两个整数M和N，之间用一个空格符隔开，M表示有多少条旅游街（1≤M≤100），N表示有多少条林荫道（1≤N≤20000）。接下里的M行依次给出了由北向南每条旅游街的分值信息。每行有N-1个整数，依次表示了自西向东旅游街每一小段的分值。同一行相邻两个数之间用一个空格隔开。
　　输出文件：输出文件是 OUTPUT.TXT。文件只有一行，是一个整数，表示你的程序找到的最佳浏览路线的总分值。
　　Program Tour;
　　var m,n:integer; {M为旅游街数，N为林荫道数}
　　　　data:array[1..20000] of -100..100;{data是由相邻两条林荫道所分}
　　procedure Init; {隔的旅游街的最大分值}
　　var a,b,c:integer;
　　　　f1:text;
　　begin
　　　assign(f1,'input.txt');
　　　reset(f1);
　　　read(f1,m,n);
　　　for a:=1 to n-1 do read(f1,data[a]); {读取每一段旅游街的分值}
　　　for a:=2 to m do
　　　　for b:=1 to n-1 do
　　　　begin
　　　　　read(f1,c);
　　　　　if c>data[ b] then data[ b]:=c; {读取每一段旅游街的分值，并选择}
　　　　end; {到目前位置所在列的最大分值记入数组data}
　　　close(f1);
　　end;
　　procedure Done;
　　var a,sum,result,c:integer;
　　　　f2:text;
　　begin
　　　result:=0;
　　　sum:=0;
　　　a:=0;
　　　while (a<n) do
　　　begin
　　　　inc(a); {从数组的第一个数据开始累加，将累加所}
　　　　sum:=sum+data[a]; {得到的最大分值记入result}
　　　　if sum>result then result:=sum;
　　　　if sum<0 then sum:=0; {若当前累加值为负数，则从当前状态起从新}
　　　end; {累加}
　　　assign(f2,'output.txt');
　　　rewrite(f2);
　　　writeln(f2,result);
　　　close(f2);
　　end;
　　begin
　　　Init;
　　　Done;
　　end.

复制代码

Eastsun · 发表于 2005-8-27 12:57:00

附录:
贪心法矩阵胚理论介绍

矩阵胚的定义是：
M={S,I}
其中S为有限集，I为S的一个子集族，满足下面条件：
1.{}属于I
2.如果集合X属于I，则X的所有子集都属于I。
3.如果集合W，V都属于I，且|V|>|W|,则V中存在一个不在W中的集合z，使W并{z}属于I。

I中的集合叫做矩阵胚的独立子集。上面三个定义保证了独立子集具有如下属性：
1.独立子集至少有一个（空集）
2.独立子集是“遗传”的。
3.只要一个独立子集不是最大（元素最多）的，我们总可以把它变得更大。

定义：把S中的元素加非负的权，我们可以得到一个加权矩阵胚。

定理1：贪心的扩展加权矩阵胚可以得到最优子集。

证明：设贪心法得到的独立子集是B，最优独立子集为T(如果有多个T，选择使B交T最大的那个)，那么：
i)如果B=T,则成功
ii)否则，设x为不在T中的第一个被贪心法选择的元素，则T并x为非独立集（否则与T最大矛盾）。
设C为T并x的子集中的最小的非独立集，则x属于C(否则C就为T的子集，与属性2矛盾)。这样，我们取C
中任意不属于B的元素y，又条件3，C-{y}为独立集。

下面，我们从C-{y}出发构造一个最优独立子集T_1，使B交T_1比B交T更大。

对于C-{y}，我们把T中不属于其中的元素依次加到里面（根据属性3），则最后我们得到一个T_1,
其中T_1=T-{y}+{x}。

下面，我们来说明w(x)=w(y)。
1.T是最优的，因此w(T_1)<=w(T),即w(x)<=w(y)
2.假设贪心算法选择x之前选择过的元素集合为X,那么：X为T的子集，且X并{y}也是T的子集。那么，在
选择x的时候，y也是可以选的。但是贪心算法选择的是x,必有w(x)>=w(y),故w(x)=w(y)

这样，T_1也是最优独立子集，但是T_1比T多一个在B中的元素x,与T的选择矛盾。故贪心法能够选择最优
独立子集。

定理2：如果F关于子集运算是封闭的，而对于任何权函数(F,w),贪心法都适用，则F为某个矩阵胚的
独立子集族。

这里略去定理的证明，想知道证明的朋友可以来信问我。

两个常用的独立子集的例子是：
1.有限个n维向量集合中个线性无关的向量。
2.某个图中没有圈的边集。

根据定理一，我们如果可以把问题归结成在加权矩阵胚中求最优独立子集的问题（需要验证问题的结构满足矩阵胚
的三个定义），我们就可以采用贪心法。也就是每次选取权值最优的元素加到独立子集中，最后得到的最大独立子
集必然是最优的。

UltraSoon · 发表于 2005-8-29 10:03:00

我收下了
好东西！

Eastsun · 发表于 2005-8-27 12:43:21

【关键字】[color=RED] 贪心策略特点理论基础应用 [/color]
　　【摘要】
　　本文着重探讨的是贪心策略的数学模型、理论基础（"矩形胚"结构）和贪心策略的特点。（贪心选择性质和局部最优解）介绍了3种体现"贪心"思想的图形算法：Dijkstra算法、Prim算法和Kruskal算法，并着重给出了近几年来在各级各类程序设计竞赛中出现的一些题目。
　　【正文】
　　一、引论
　　信息，人类社会发展的重要标志。人类对信息的记载，可以追溯到原始社会。在漫长的人类社会发展过程中，伴随着科学技术的发展，人类对客观世界的认识不断加深，现实世界的信息量急剧增大。为了满足人们对大数据量信息处理的渴望，1946年世界上第一台电子数字计算机ENIAC应运而生。在此后的半个世纪中，为解决各种实际问题，计算机算法学得到了飞速的发展。线形规划、动态规划等一系列运筹学模型纷纷运用到计算机算法学中，解决了诸如经济决策等一系列现实问题。在众多的计算机解题策略中，贪心策略可以算得上是最接近人们日常思维的一种解题策略，正基于此，贪心策略在各级各类信息学竞赛、尤其在对NPC类问题的求解中发挥着越来越重要的作用。
　　二、贪心策略的定义
　　【定义1】贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。
　　其实，从"贪心策略"一词我们便可以看出，贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心策略可以得到最优解或较优解。
　　三、贪心算法的特点
　　通过上文的介绍，可能有人会问：贪心算法有什么样的特点呢？我认为，适用于贪心算法解决的问题应具有以下2个特点：
　　1、贪心选择性质：
　　所谓贪心选择性质是指应用同一规则f，将原问题变为一个相似的、但规模更小的子问题、而后的每一步都是当前看似最佳的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。从全局来看，运用贪心策略解决的问题在程序的运行过程中无回溯过程。关于贪心选择性质，读者可在后文给出的贪心策略状态空间图中得到深刻地体会。
　　2、局部最优解：
　　我们通过特点2向大家介绍了贪心策略的数学描述。由于运用贪心策略解题在每一次都取得了最优解，但能够保证局部最优解得不一定是贪心算法。如大家所熟悉得动态规划算法就可以满足局部最优解，在广度优先搜索（BFS）中的解题过程亦可以满足局部最优解。
　　在遇到具体问题时，许多选手往往分不清哪些题该用贪心策略求解，哪些题该用动态规划法求解。在此，我们对两种解题策略进行比较。
　　　　
　　　　　　　　　　　　　　　　　　　　　　图一

复制代码

		自动登录	找回密码
密码			加入易码

[算法介绍]贪心策略的特点与应用

浏览过的版块