贪心策略的特点与在信息学竞赛中的应用(一至六)

《贪心策略的特点与在信息学竞赛中的应用(一至六)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、浅谈贪心策略的特点与在信息学竞赛中的应用【关键字】贪心策略特点理论基础应用【摘要】本文着重探讨的是贪心策略的数学模型、理论基础（〃矩形胚〃结构）和贪心策略的特点。（贪心选择性质和局部最优解）介绍了3种体现〃贪心〃思想的图形算法：Dijkstra算法、Prim算法和Kruskal算法，并着重给出了近儿年来在各级各类程序设计竞赛中出现的一些题H。【正文】一、贪心策略的定义【定义】贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值（或较优解）的一种解题方法。其实，从〃贪心策略〃一词我们便可以看出，贪心策略总是做出在当前看来是垠优的选择，也就是说贪心策略并不是从整体上加

2、以考虑,它所做出的选择只是在某种意义I二的局部最优解，而许多问题口身的特性决定了该题运用贪心策略町以得到最优解或较优解。二、贪心算法的特点通过上文的介绍，可能有人会问：贪心算法有什么样的特点呢？我认为，适用于贪心算法解决的问题应具有以下2个特点：1、贪心选择性质：所谓贪心选择性质是指应用同一规则f,将原问题变为一个相似的、但规模更小的子问题、而后的每一步都是当前看似最佳的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。从全局來看，运用贪心策略解决的问题在程序的运行过程中无冋溯过程。关于贪心选择件质,读者口J在后文给出的贪心策略状态空间图屮得到深刻地体会。2、局部最优解

3、：我们通过特点2向大家介绍了贪心策略的数学描述。山于运川贪心策略解题在每一次都取得了最优解，但能够保证局部最优解得不一定是贪心算法。如大家所熟悉得动态规划算法就可以满足局部最优解，在广度优先搜索（BFS）中的解题过程亦可以满足局部最优解。在遇到具体问题吋，许多选手往往分不清哪些题该用贪心策略求解，哪些题该用动态规划法求解。在此，我们对两种解题策略进行比较。贪心策略动态规划相同点1时间效率较高、适用于对问题的求解有严格时间限制的题目。2均能保证局部最优解。不同点所占空间较小所占空间较大某次具体选择必是最优选择某次具体选择不一定是最优选择解题大体框架：线形?AUB“C1DA—B_C

4、_D为最优选择，腎中角结点氏C也簇优逋择解题大体框架：图或树A＜丄B、c・•ABCD为曇优解，B.C不一定是叢忧选理图一【引例】在一个NXM的方洛阵中，每一洛子赋予一个数（即为权）。规定新欠移动时只能向上或向右。现试找出一条路径，使其从左下角至右上角所经过的权之和最大。3■461210我们以2X3的矩阵为例。若按贪心策略求解，所得路径为：1-3-4-6；若按动态规划法求解，所得路径为:1->2-10-60由于贪心策略自身的特点，使得数字10所在的洛子成为一个“坏洛子笃即运用贪心策略找不到它，而运用动态规划法求解的第一歩（1->2）并不是最优选择，但却保证了若备订羽祖贝」％2、％

5、、••之臥純—定不在数列A中。对于一元素a“（2WpWm）,设a^=co,若保证全局最优解，则必在数列A中，但运用贪心策略求解时a“不在数列A中。由此可见，贪心策略并不到达间题状态的全部空间。若用空间图来表示贪心算法和动态规划算法（如下图），我们可以蓿楚地看到，贪心算法间题状态空间动态规划所用空间贪心策略所用空间是一种对输入数据进行不断收缩的过程。它并不到达间题的全部状态空间。这是由本文所述的贪心策略的线形解题框架所决定的°三、贪心策略的理论基础••矩阵胚正如前文所说的那样，贪心策略是最接近人类认知思维的一种解题策略。但是，越是显而易见的方法往往越难以证明。下面我们就來介绍贪心

6、策略的理论一矩阵胚。〃矩阵胚〃理论是一种能够确定贪心策略何时能够产生最优解的理论，虽然这套理论述很不完善，但在求解故优化问题时发挥着越來越重耍的作用。【定义3】矩阵胚是一个序对M二[S,I],其中S是一个有序非空集合，I是S的一个非空子集，成为S的一个独立子集。如果M是一个NXM的矩阵的话，即311»3=a?j，a左2a林/S是M的各个行，S=(apa2),I是龛形无关的若干行a：,巧,a去若M是无向图G的矩阵胚的话，则S为图的边集，I是所冇构成森林的一组边的子集。如杲对S的每一个元素X(XeS)赋予一个正的权值W(X),则称矩阵胚M二(S,I)为一个加权矩阵胚。适宜于用贪心策

7、略來求解的许多问题都可以归结为在加权矩阵胚屮找-个具有最大权值的独立子集的问题，即给定一个加权矩阵胚，M=(S,I),若能找出一个独立且具有最大可能权值的子集A,且A不被M屮比它更大的独立子集所包含，那么A为最优子集，也是一个最人的独立子集。我们认为，针对绝大多数的信息学问题，只要它具备了〃矩阵胚〃的结构，便可用贪心策略求解。矩阵胚理论对于我们判断贪心策略是否适用于某一复杂问题是十分有效的。四、几种典型的贪心算法贪心策略在图论中有着极其重要的应用。诸如KruskalsPrim、Dijkstr