开发工具:
文件大小: 280kb
下载次数: 0
上传时间: 2011-08-22
详细说明： 贪心算法一般来说是解决“最优问题”，具有编程简单、运行效率高、空间复杂度低等特点。 一、贪心算法与简单枚举和动态规划的运行方式比较 贪心算法一般是求“最优解”这类问题的。最优解问题可描述为：有n个输入， 它的解是由这n 个输入的某个子集组成，并且这个子集必须满足事先给定的条 件。这个条件称为约束条件。而把满足约束条件的子集称为该问题的可行解。这 些可行解可能有多个。为了衡量可行解的优劣，事先给了一个关于可行解的函数， 称为目标函数。目标函数最大（或最小）的可行解，称为最优解。 a)求“最优解”最原始的方法为搜索枚举方案法（一般为回溯法）。 b)其次现今竞赛中用的比较普遍的动态规划（需要满足阶段无后效性原则）。 动态规划主要是利用最最优子问题的确定性，从后向前（即从小规模向大规模） 得到当前最优策略，从而避免了重复的搜索。 举例说明：求多段图的最短路径。 动态规划要满足最优子结构原则，贪心算法呢？就目前的资料看，有个证明 模型是“矩阵胚理论”，但要证明一个问题是矩阵胚，十分困难。并且也不常见 的可用贪心算法问题都能用矩阵胚来证明。因此，可以认为贪心算法的正确性证 明是个难点。因此有些选手在没能证明时，也大胆设想结论应该是正确的。有时 这难免会放错。 例如 95年NOI中的“石子合并”一题： 例一、石子合并 试题： 在一个圆形操场的四周摆放N 堆石子(N≤100)，现要将石子有次序地合并 成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数， 记为该次合并的得分。 编一程序，由文件读入堆数N 及每堆石子数(≤20) 选择一种合并石子的方案，使得做N-1 次合并，得分的总 和最小；选择一种合并石子的方案，使得做N-1 次合并， 得分的总和最大。 例2 士兵排队问题（1996 年中国队选拔赛）----构造法证明 试题： 有N 个士兵(1≤N≤26)，编号依次为A，B，C，...。队列训练时，指挥官 要把一些士兵从高到矮依次排成一行，但现在指挥官不能直接获得每个人的身高 信息，只能获得“P1比P2高”这样的比较结果(P1，P2∈A，B，C，...，Z，记 为P1>P2)，如“A>B”表示A 比B高。 请编一程序，根据所得到的比较结果求出一种符合条件的排队方案。 例3 排队问题----反证法证明 试题： 在一个超市，有N 个人排队到一个柜台付款，已知每个人需要处理的时间为 Ti（0
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
