文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > 部分贪心算法思想在信息学竞赛中的应用
侵权投诉

部分贪心算法思想在信息学竞赛中的应用

在某些数据规模非常大的问题当中,我们常常希望使用贪心法解决问题,但是纯粹的贪心在某些情形下会有反例存在。在这些情况下,我们可以采取一种折中的方案——部分贪心。降问题规模降低到较小的范围内以后,再采用其他方法解决。

1. 首先从S找一条最短的路到下一层节点,即S->A

2. 然后从A找一条最短的路到下一层节点,即A->E

3. 最后从E到T是唯一的决策。

这样,我们得到的路径为S->A->E->T,路径长度为1+4+4=9。

当然,这样做显然是不正确的,事实上,有更短的路径S->B->D->T,路径长度为2+2+2=6

贪心法的优势和劣势

一个正确的贪心法有着许许多多的优点,比如说思路直接,程序效率高,代码量小,空间消耗小等等。然而不幸的是,对于大多数问题,我们难以找到一个简单可行的贪心思路,即使我们找到一个看上去很正确的贪心思路,我们也需要严格的正确性证明来支持这一思路。这往往给我们直接使用贪心算法带来了巨大的困难。

什么是部分贪心

很多时候,当我们试图使用贪心算法解决问题,却发现存在种种特殊情况,使得我们的贪心算法会产生一些小的错误,这些特殊情况的普遍特点是,数据规模很小,而我们的贪心思路往往是针对大局设计的,而这些细节上的特殊情况往往会使我们感到无从下手。

在这种情况下,我们可以考虑一种特殊贪心方式,在接近初始状态或者目标状态的决策中采用搜索或者动态规划这类可以保证正确性的算法来处理,而对于

部分贪心算法思想在信息学竞赛中的应用

上一页第2页

你可能喜欢

  • 算法合集
  • 课程设计
  • 算法设计与分析
  • 贪心算法
  • 算法艺术与信息学竞赛
  • 常用算法

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email