贪心策略的特点与在信息学竞赛中的应用

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

1、孙贺论文集第19页共19页贪心策略的特点与在信息学竞赛中的应用【关键字】贪心策略特点理论基础应用【摘要】本文着重探讨的是贪心策略的数学模型、理论基础（“矩形胚”结构）和贪心策略的特点。（贪心选择性质和局部最优解）介绍了3种体现“贪心”思想的图形算法：Dijkstra算法、Prim算法和Kruskal算法，并着重给出了近几年来在各级各类程序设计竞赛中出现的一些题目。【正文】一、引论信息，人类社会发展的重要标志。人类对信息的记载，可以追溯到原始社会。在漫长的人类社会发展过程中，伴随着科学技术的发展，人类对客观世界的认识不断加深，现实世界的信

2、息量急剧增大。为了满足人们对大数据量信息处理的渴望，1946年世界上第一台电子数字计算机ENIAC应运而生。在此后的半个世纪中，为解决各种实际问题，计算机算法学得到了飞速的发展。线形规划、动态规划等一系列运筹学模型纷纷运用到计算机算法学中，解决了诸如经济决策等一系列现实问题。在众多的计算机解题策略中，贪心策略可以算得上是最接近人们日常思维的一种解题策略，正基于此，贪心策略在各级各类信息学竞赛、尤其在对NPC类问题的求解中发挥着越来越重要的作用。二、贪心策略的定义【定义1】贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值

3、(或较优解)的一种解题方法。其实，从“贪心策略”一词我们便可以看出，贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心策略可以得到最优解或较优解。三、贪心算法的特点孙贺论文集第19页共19页通过上文的介绍，可能有人会问：贪心算法有什么样的特点呢？我认为，适用于贪心算法解决的问题应具有以下2个特点：1、贪心选择性质：所谓贪心选择性质是指应用同一规则f，将原问题变为一个相似的、但规模更小的子问题、而后的每一步都是当前看似最佳的选择

4、。这种选择依赖于已做出的选择，但不依赖于未做出的选择。从全局来看，运用贪心策略解决的问题在程序的运行过程中无回溯过程。关于贪心选择性质，读者可在后文给出的贪心策略状态空间图中得到深刻地体会。2、局部最优解：我们通过特点2向大家介绍了贪心策略的数学描述。由于运用贪心策略解题在每一次都取得了最优解，但能够保证局部最优解得不一定是贪心算法。如大家所熟悉得动态规划算法就可以满足局部最优解，在广度优先搜索（BFS）中的解题过程亦可以满足局部最优解。在遇到具体问题时，许多选手往往分不清哪些题该用贪心策略求解，哪些题该用动态规划法求解。在此，我们对两

5、种解题策略进行比较。图1孙贺论文集第19页共19页【引例】在一个N×M的方格阵中，每一格子赋予一个数（即为权）。规定每次移动时只能向上或向右。现试找出一条路径，使其从左下角至右上角所经过的权之和最大。3461210我们以2×3的矩阵为例。若按贪心策略求解，所得路径为：1→3→4→6；图二若按动态规划法求解，所得路径为：1→2→10→6。aaaaaaaaaaaa由于贪心策略自身的特点，使得数字10所在的格子成为一个“坏格子”，即运用贪心策略找不到它，而运用动态规划法求解的第一步（1→2）并不是最优选择，但却保证了全局最优解；运用贪心策略求

6、解的第一步（1→3）保证了图三局部最优解，却无法保证全局最优解。我们若用图3所示的N×M的矩阵表示一组数,设运用与引例同样的移动规则后得到了由若干个元素组成的数列A。可得如下结论：若a>a,则a、a、…a一定不在数列A中。对于一元素a(2≤p≤m)，设a=∞，若保证全局最优解，则a必在数列A中，但运用贪心策略求解时a不在数列A中。由此可见，贪心策略并不到达问题状态的全部空间。若用空间图来表示贪心算法和动态规划算法（如下图），我们可以清楚地看到，贪心算法问题状态空间动态规划所用空间贪心策略所用空间图4是一种对输入数据进行不断收缩的过程。它

7、并不到达问题的全部状态空间。这是由本文所述的贪心策略的线形解题框架所决定的。四、贪心策略的理论基础孙贺论文集第19页共19页——矩阵胚正如前文所说的那样，贪心策略是最接近人类认知思维的一种解题策略。但是，越是显而易见的方法往往越难以证明。下面我们就来介绍贪心策略的理论——矩阵胚。“矩阵胚”理论是一种能够确定贪心策略何时能够产生最优解的理论，虽然这套理论还很不完善，但在求解最优化问题时发挥着越来越重要的作用。【定义3】矩阵胚是一个序对M=[S，I]，其中S是一个有序非空集合，I是S的一个非空子集，成为S的一个独立子集。如果M是一个N×M的

8、矩阵的话，即a,a,......,a......M=a,a,......,a......a,a,......,aS是M的各个行，S=（a,a,......,a），I是线形无关的若干行a,a,a......若