一般实际生活中我们遇到的算法分为四类:
一>判定性问题
二>最优化问题
三>构造性问题
四>计算性问题
而今天所要总结的算法就是着重解决 最优化问题
《算法之道》对三种算法进行了归纳总结,如下表所示:
|
标准分治
|
动态规划
|
贪心算法
|
适用类型
|
通用问题
|
优化问题
|
优化问题
|
子问题结构
|
每个子问题不同
|
很多子问题重复(不独立)
|
只有一个子问题
|
最优子结构
|
不需要
|
必须满足
|
必须满足
|
子问题数
|
全部子问题都要解决
|
全部子问题都要解决
|
只要解决一个子问题
|
子问题在最优解里
|
全部
|
部分
|
部分
|
选择与求解次序
|
先选择后解决子问题
|
先解决子问题后选择
|
先选择后解决子问题
|
分治算法特征:
1)规模如果很小,则很容易解决。//一般问题都能满足
2)大问题可以分为若干规模小的相同问题。//前提
3)利用子问题的解,可以合并成该问题的解。//关键
4)分解出的各个子问题相互独立,子问题不再包含公共子问题。 //效率高低
【一】动态规划:
依赖:依赖于有待做出的最优选择
实质:就是分治思想和解决冗余。
自底向上(每一步,根据策略得到一个更小规模的问题。最后解决最小规模的问题。得到整个问题最优解)
特征:动态规划任何一个i+1阶段都仅仅依赖 i 阶段做出的选择。而与i之前的选择无关。但是动态规划不仅求出了当前状态最优值,而且同时求出了到中间状态的最优值。
缺点:空间需求大。
【二】贪心算法:
依赖:依赖于当前已经做出的所有选择。
自顶向下(就是每一步,根据策略得到一个当前最优解。传递到下一步,从而保证每一步都是选择当前最优的。最后得到结果)
【三】分治算法:
实质:递归求解
缺点:如果子问题不独立,需要重复求公共子问题
分享到:
相关推荐
**知识点生成:中科大《算法导论》课件——贪心算法** ### 一、贪心算法概述 **1.1 贪心算法的概念** 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择策略,以便产生全局最优解的...
本书共分为 34 章,涵盖了算法的基础知识、设计和分析,包括排序、搜索、图算法、动态规划、贪心算法、回溯法等。 算法的角色 在计算机科学中,算法扮演着非常重要的角色。算法可以帮助我们解决复杂的问题,使得...
《算法导论第四版》探讨了分治法、动态规划、贪心算法、回溯算法、分支限界法等算法设计范式。每种范式都有其适用的问题类型和解决问题的方法论。通过对这些范式的理解和实践,读者可以学会如何将复杂问题分解为更易...
《算法导论》深入探讨了算法的设计原则,包括递归、动态规划、贪心算法和分治策略,并提供了多种分析工具,如渐进分析、最坏情况和平均情况分析,帮助理解算法的时间复杂度和空间复杂度。 #### 数据结构的重要性 ...
9. 贪心算法:解释贪心算法如何工作,探讨其适用条件和局限性,并给出经典的贪心算法示例,如哈夫曼编码。 10. NP完全性:介绍NP完全问题的定义,探讨如何识别这类问题,并讲解近似算法和启发式算法等解决NP完全...
《算法导论》第三版还引入了最新的研究成果,如近似算法、线性规划和动态规划的更深入探讨,以及新加入的计算几何和网络流等内容,使得这本教材更加全面和实用。无论是初学者还是专业人士,都能从中受益匪浅,提升...
前者很显然是《算法导论》第三版的电子版,读者可以通过这份PDF文档深入学习书中涵盖的各种算法,如排序、搜索、图算法、动态规划、贪心算法、分治策略等。这些算法是计算机科学的基础,对于提升编程能力和解决复杂...
首先,这份资源涵盖了算法设计与分析的基本方法,包括分治策略、动态规划、贪心算法以及回溯法等。这些方法是解决各种复杂问题的基石,通过阅读答案,读者可以清晰地看到如何将这些方法应用到具体问题上,从而提升...
- **算法设计方法**:包括分治法、贪心算法、动态规划等。 - **分治法**:将问题分解成若干个规模较小的相同子问题,然后递归地求解这些子问题。 - **贪心算法**:在每个步骤中都采取当前看来最优的选择,以期获得...
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通...
《算法导论》第二版涵盖了广泛的算法主题,包括排序、搜索、图算法、动态规划、贪心算法、分治策略、回溯法、随机化算法以及近似算法等。这些算法在日常编程工作中都有广泛的应用,例如,排序算法中的快速排序、归并...
4. **动态规划**:动态规划用于解决最优化问题,如背包问题、最长公共子序列、最小编辑距离等,通过构造状态转移方程来求解。 5. **图论算法**:包括Dijkstra最短路径算法、Floyd-Warshall所有对最短路径、Kruskal...
《算法导论》是计算机科学领域的一本经典教材,涵盖了广泛的算法分析和设计技术。这本书的第31至35章包含了许多关键的算法概念,这些章节深入探讨了不同的算法主题,对于理解和掌握算法有着至关重要的作用。以下是这...
书中还介绍了分治算法、动态规划和贪心算法等经典的算法设计范式。比如,分治法中的主定理(Master Theorem),这是解决递归式复杂度的一个重要工具。书中还提到了概率分析和随机化算法,例如通过雇佣问题来说明随机...
4、修订了动态规划和贪心算法相关内容。 5、流网络相关材料现在基于边上的全部流。 6、由于关于矩阵基础和Strassen算法的材料移到了其他章,矩阵运算这一章的内容所占篇幅更小。 7、修改了对Knuth-Morris-Pratt字符...
《麻省理工学院-算法导论》是一门深入探讨算法设计与分析的课程资料集合,主要面向具有一定英语基础的学习者。这个压缩包包含了课程的作业、讲义、测试题和教师手册,提供了全面的学习资源。 算法是计算机科学的...
《算法导论》是计算机科学领域的一本经典著作,它深入浅出地介绍了算法的设计、分析和实现。这本书广泛应用于大学计算机科学课程,是学习算法的必备参考书。以下是基于《算法导论》的一些核心知识点的详细阐述: 一...
《算法导论》是计算机科学领域的一本经典著作,它深入浅出地介绍了算法的设计、分析和实现。这本书的第三版更是集大成者,涵盖了众多重要的算法和数据结构,对于学习和研究计算机科学的人来说是不可或缺的参考书。...
《算法导论》是计算机科学领域的一本经典教材,它深入浅出地介绍了算法的设计、分析和实现。这些讲义来自于MIT(麻省理工学院)的教师,具有极高的学术价值和教学价值,适合计算机科学的学生和专业人士学习。以下是...