ACM+DP+算法++大集合..docx

第?27 讲 贪心与动态规划 贪心和动态规划在算法设计求解中均有着广泛的应用，因为它们都属于最优化问题的求解，因此这里将它们放在同一章节加以介绍。 虽然都是求解最优化问题，但是贪心和动态规划还是有很大的区别的。前者是从问题的源出发每一步都采取最优的选择，最终找到问题的解；而后者则从考虑问题的子问题入手，通过比较划分后的独立子问题的解，来确定当前问题的最优解。相对而言，贪心法的形式非常多样，不容易对它做具体的分类，许多算法之中都蕴含了贪心的思想，而动态规划则可以大致分出一些应用较多的独立模型。因此在这一章节，我们会把笔墨侧重于后者。?第一部分 贪心(Greedy) 在求解最优化问题时，有这样一种自然的想法，希望每一步都则采取最优的策略，最终得到全局的最优解，这就是贪心思想。它的最大特点就是运行速度快，效率高，因此备受程序设计员的喜爱。当然，由此也带来了贪心法的最大问题，如何证明其正确性？因为在很多时候，局部最优解的选择往往最终得不到全局最优解。于是，我们在运用贪心思想解决问题时，就需要格外的小心。 事实上，许多成熟的算法中都蕴含了贪心思想，比如求解最小生成树的Bellman-Ford算法，单源最短路径的Dijkstra算法，求解二分图匹配的匈牙利算法等等。 很多时候，贪心法虽然得不到最优解，但是仍具有重要的最用。比如，利用贪心法得到的近似解可以为有哪些信誉好的足球投注网站法提供较强的剪枝策略。就用一个例子来看看贪心法的应用吧：[例 1, POJ 2287] 田忌赛马田忌赛马的故事想必已经被大家所熟知了，孙膑“以君之下驷彼上驷，取君上驷与彼中驷，取君中驷与彼下驷”的策略使得田忌最终“一不胜而再胜”。如今，田忌与齐王决定再战一场，这一回双方决定用 n (n ≤ 1000)匹马较量一番。每一回合，先到的马将为主人赢得200美元，如果打平双方均无需指出。假设双方马匹的速度已给出，而田忌仍然能够提前知道齐王马匹的出场顺序，那么他最多能赢多少钱呢？[分析]乍看下去，似乎没有很好的贪心思路，倒是可以利用二分图匹配的方法解题，可是时间复杂度相对较高，改进得的匈牙利算法也匹配需要O（n3）的时间，即使Hopcraft算法，也需要O（）的时间复杂度。那么，真的不能运用贪心法吗？当年田忌获胜的方法或许能够给我们一些启迪。用下等马匹配齐王的上等马，虽然输掉了局部，却赢下了全局。也就是说，在最终的最优选择中，将有一些场次会输掉比赛。那么，既然是这样，我们何不学习田忌，用那些“下等马”输掉这些比赛，而让获胜者，均为齐王的“上等马”呢？这样的改进不会比原先的最优选择更差。设{An}为田忌的马，且按速度排序A1 A2 … An ,{Bn}为齐王的马，同样按速度排序B1 B2 … Bn ,假设Ap会输给它的对手，而Aq（p q）的选择使它至少不输掉该场比赛，那么将二者的对手对调，所得结果显然不会比之前更差；同样，若Bp不输给它的对手，而Bq（p q）则输给了它的对手，那么将再二者的对手对调，结果仍不会次于调换前。于是，调换后见下图：A1A2..An-1AnB1B2..Bn-1BnA1A2..An-1AnB1红线代表输的场次B2为了看得更清晰， .红线间若有交叉可通过.调整将其变为一组平行Bn-1 线，不会影响结果Bn 图1-1 最优策略????????????? ????????图1-2 改进后既然改进前是最优策略，那么改进后它必然也是最优策略。而改进后的图与田忌赛马有着异曲同工之处，那么顺着它的思路，我们似乎又有了另一个改进策略。在图1-2中除去所有输掉比赛的{A}以及它们的对手，剩下的图中所有的“交叉”都可以去掉。即假设Ap的对手为Br,Aq的对手为Bs，而pq,rq，那么我们可以对调双方的对手，显然结果不会变差。于是，改进后的图变成了如下： A1A2..An-1AnB1B2..Bn-1Bn 图 1-3 最终策略显然，这个最终策略仍然是最优策略。于是，我们只需要枚举输掉的比赛场次，逐个判断是否满足上述策略的要求，就能够找到最优解。?第二部分 动态规划（Dynamic Programming）动态规划是解决最优化问题的重要手段，它的优美精巧的结构特点深得程序设计员的喜爱，一段短小精悍的代码就能解决长长的回溯法所不能解决的问题，这是动态规划最吸引人的特点。动态规划是通过合并子问题的解来解决最优化问题的。许多时候，一个问题的若干子问题往往不是独立存在的，而和其它问题的子问题相同，于是对这些公共子问题的采取先计算求解并存值得方式，以便为将来反复调用时直接提供值，就成了动态规划的主体思想。可以看到，实现动态规划需要满足如下条件：1) 最优子结构性质，也就是说问题最优解与子问题的最优解有关。2) 无后效性，就是说问题的解只与已求得的子问题的解有关，与尚未求得的问题的解无关