`
Touch_2011
  • 浏览: 291103 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

浅析贪心算法

贪心最短路径最小生成树哈弗曼编码 
阅读更多

1.基本思路：

a.顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。

b.贪心算法一般可以先做一个排序，然后选择。

2.例题：

（1）迪杰斯特拉算法求最短路径

http://touch-2011.iteye.com/blog/1076031

（2）最小生成树的算法

http://touch-2011.iteye.com/blog/1075840

（3）哈弗曼编码

http://touch-2011.iteye.com/blog/1058800

0
顶
2
踩
分享到：
| 浅析动态规划算法
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    贪心算法_greedyalgorithm_

    《浅析贪心算法》和《贪心算法的探讨与研究》这两篇PDF文档可能详细介绍了贪心算法的基本概念、应用实例、优缺点以及与其他算法（如动态规划）的比较。它们可能会讨论如何设计贪心算法，如何分析其正确性，以及在...

    浅析java贪心算法

    贪心算法是一种优化策略，它在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的。在Java编程中，贪心算法同样被广泛应用于解决一些优化问题，如找零钱问题、任务...

    浅析动态规划算法

    贪心算法每次选择局部最优解，期望最终达到全局最优，而动态规划则是确保所有子问题的最优解组合成全局最优解。 “工具”标签可能暗示了文档中还会介绍一些辅助工具，比如使用Python或Java编程语言实现动态规划算法...

    图的遍历迷宫算法浅析

    我们可以使用贪心算法来选择遍历的方向，并使用回溯算法来避免重复遍历。 图的遍历迷宫算法可以生成各种复杂的迷宫，从简单的迷宫到复杂的迷宫。这种算法可以应用于各种领域，例如游戏开发、机器人导航、自动驾驶等...

    浅析回溯算法

    对于大规模问题，可能需要结合其他优化技术，如动态规划、贪心策略等，以降低搜索复杂度。 在提供的压缩包文件《回溯法ppt详细讲解.ppt》中，可能会包含更详细的讲解，如回溯算法的实例分析、代码实现、剪枝技巧等...

    浅析非完美算法在信息学竞赛中的应用_胡伟栋.ppt

    一些常见的非完美算法方法包括随机贪心算法，它在决策过程中引入随机性以求得近似最优解；抽样测试，通过选取总体的一小部分来估算整体的特性；以及部分忽略法，对于那些出现概率低且影响结果程度有限的情况选择忽略...

    全国信息学竞赛算法研究论文合集

    本章节重点介绍了一些典型问题中贪心思想的应用案例，帮助读者理解贪心算法的基本原理和应用范围。 #### 从一类单调性问题看算法的优化 单调性问题是信息学竞赛中常见的问题类型之一，通过对这类问题的深入分析，...

    浅析树的划分问题浅析树的划分问题

    解决这个辅助问题可以采用一种基于贪心思想的扫描算法，其基本思想是沿着树的深度顺序扫描节点，每次遇到满足条件的子树就将其划分出来。算法的具体步骤如下： - 按照节点的深度递减顺序遍历整棵树。 - 对于当前...

    浅析中职学校智能排课系统的设计与实现.rar

    在设计阶段，开发者可能采用了数据结构和算法来解决这些问题，例如使用图论中的拓扑排序来避免时间冲突，使用贪心算法或回溯法来优化教师的工作量分配，以及利用优先队列处理教室资源的优先级。 其次，实现智能排课...

    IOI国家集训队论文集1999-2019

    + [贪心](#贪心) + [压缩法](#压缩法) + [逆向思维](#逆向思维) + [穷举](#穷举) + [目标转换](#目标转换) + [类比](#类比) + [分割与合并](#分割与合并) + [平衡思想](#平衡思想) <small><i>...

    浅析C语言程序代码的优化.pdf

    - **算法改进**：针对特定问题，可能需要调整现有算法，如使用分治策略、贪心法或回溯法，以提高算法性能。 2. **数据结构优化**： - **数据结构选择**：根据问题的需求选择合适的数据结构，如数组、链表、树、图...

    浅析物联网与人工智能的结合

    基于深信度网(DBN)提出非监督贪心逐层训练算法，为解决深层结构相关的优化难题带来希望，随后提出多层自动编码器深层结构。此外Lecun等人提出的卷积神经网络是第一个真正多层结构学习算法，它利用空间相对关系减少...

    5.杨沐《浅析信息学中的“分”与“合”》.ppt

    《浅析信息学中的“分”与“合”》是由福建省福州第三中学的杨沐老师所作的一份报告，主要探讨了在信息学问题解决中常用的两种策略：“分”与“合”。这两种思想是计算机科学，特别是算法设计中的核心概念。 “分”...

    信息学国家集训队2005论文集

    例如，贪心算法虽然无法保证找到全局最优解，但在很多情况下能够迅速得到满意的近似解。动态规划的近似解法同样如此，它们能够在较短时间内给出接近最优的解决方案。胡伟栋的论文深入剖析了这些算法在竞赛中的应用，...

    acm国家集训队2008年论文合集

    2.高逸涵《部分贪心思想在信息学竞赛中的应用》 3.陈丹琦《基于连通性状态压缩的动态规划问题》 4.张煜承《一类算法复合的方法》 5.陈瑜希《Pólya计数法的应用》 6.余林韵《运用化归思想解决信息学中的数列问题》 7...

    2008年信息学奥林匹克中国国家国家集训队论文

    2.高逸涵《部分贪心思想在信息学竞赛中的应用》 3.陈丹琦《基于连通性状态压缩的动态规划问题》 4.张煜承《一类算法复合的方法》 5.陈瑜希《Pólya计数法的应用》 6.余林韵《运用化归思想解决信息学中的数列问题》 7...

    IOI 08集训队论文

    2.高逸涵《部分贪心思想在信息学竞赛中的应用》 3.陈丹琦《基于连通性状态压缩的动态规划问题》 4.张煜承《一类算法复合的方法》 5.陈瑜希《Pólya计数法的应用》 6.余林韵《运用化归思想解决信息学中的数列问题》 7...

    2013集训队论文集

    解决这类问题通常需要运用递归、动态规划、贪心算法等技术。理解并掌握方格取数问题的解题思路，对于提高算法设计能力和逻辑思维能力具有重要作用。 2. **Twostrings试题讨论** - 王康宁（吉林东北师大附中） ...

    国家集训队2009论文集 上

    论文可能会探讨不同类型的背包问题的解法，如动态规划、贪心策略等。 2. **汤可因《浅析竞赛中一类数学期望问题的解决方法》**： 数学期望是概率论中的一个重要概念，经常用于决策和优化问题。在信息学竞赛中，...

Magicbox
Global site tag (gtag.js) - Google Analytics