正如前文所说的那样，贪心策略是最接近人类认知思维的一种解题策略。但是，越是显而易见的方法往往越难以证明。下面我们就来介绍贪心策略的理论--矩阵胚。 "矩阵胚"理论是一种能够确定贪心策略何时能够产生最优解的理论，虽然这套理论还很不完善，但在求解最优化问题时发挥着越来越重要的作用。 【定义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）算法
贪心策略的应用
在现实世界中，我们可以将问题分为两大类。其中一类被称为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算法来求解。 以上三道题只是使用了单一的贪心策略来求解的。而从近几年的信息学奥林匹克竞赛的命题方向上看，题目更加灵活，同时测试数据较大，规定的出解时间较短。在一些问题中，我们采用贪心策略对问题化简，从而使程序具有更高的效率。转自：中国教育曙光网
Powered by: C++博客 Copyright © oyjpart
