`

【算法导论】贪心算法,递归算法,动态规划算法总结

 
阅读更多

一般实际生活中我们遇到的算法分为四类:

一>判定性问题

二>最优化问题

三>构造性问题

四>计算性问题

而今天所要总结的算法就是着重解决 最优化问题

《算法之道》对三种算法进行了归纳总结,如下表所示:

标准分治

动态规划

贪心算法

适用类型

通用问题

优化问题

优化问题

子问题结构

每个子问题不同

很多子问题重复(不独立)

只有一个子问题

最优子结构

不需要

必须满足

必须满足

子问题数

全部子问题都要解决

全部子问题都要解决

只要解决一个子问题

子问题在最优解里

全部

部分

部分

选择与求解次序

先选择后解决子问题

先解决子问题后选择

先选择后解决子问题

分治算法特征:

1)规模如果很小,则很容易解决。//一般问题都能满足

2)大问题可以分为若干规模小的相同问题。//前提

3)利用子问题的解,可以合并成该问题的解。//关键

4)分解出的各个子问题相互独立,子问题不再包含公共子问题。 //效率高低

【一】动态规划:

依赖:依赖于有待做出的最优选择

实质:就是分治思想和解决冗余。

自底向上(每一步,根据策略得到一个更小规模的问题。最后解决最小规模的问题。得到整个问题最优解)

特征:动态规划任何一个i+1阶段都仅仅依赖 i 阶段做出的选择。而与i之前的选择无关。但是动态规划不仅求出了当前状态最优值,而且同时求出了到中间状态的最优值。

缺点:空间需求大。

【二】贪心算法:

依赖:依赖于当前已经做出的所有选择。

自顶向下(就是每一步,根据策略得到一个当前最优解。传递到下一步,从而保证每一步都是选择当前最优的。最后得到结果)

【三】分治算法:

实质:递归求解

缺点:如果子问题不独立,需要重复求公共子问题

分享到:
评论

相关推荐

    中科大 算法导论 课件(全套10)贪心算法

    **知识点生成:中科大《算法导论》课件——贪心算法** ### 一、贪心算法概述 **1.1 贪心算法的概念** 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择策略,以便产生全局最优解的...

    算法导论(英文原版教材).pdf

    本书共分为 34 章,涵盖了算法的基础知识、设计和分析,包括排序、搜索、图算法、动态规划、贪心算法、回溯法等。 算法的角色 在计算机科学中,算法扮演着非常重要的角色。算法可以帮助我们解决复杂的问题,使得...

    算法导论第四版 英文

    《算法导论第四版》探讨了分治法、动态规划、贪心算法、回溯算法、分支限界法等算法设计范式。每种范式都有其适用的问题类型和解决问题的方法论。通过对这些范式的理解和实践,读者可以学会如何将复杂问题分解为更易...

    算法导论答案算法导论教师手册

    《算法导论》深入探讨了算法的设计原则,包括递归、动态规划、贪心算法和分治策略,并提供了多种分析工具,如渐进分析、最坏情况和平均情况分析,帮助理解算法的时间复杂度和空间复杂度。 #### 数据结构的重要性 ...

    算法导论中文版

    9. 贪心算法:解释贪心算法如何工作,探讨其适用条件和局限性,并给出经典的贪心算法示例,如哈夫曼编码。 10. NP完全性:介绍NP完全问题的定义,探讨如何识别这类问题,并讲解近似算法和启发式算法等解决NP完全...

    算法导论.rar

    《算法导论》第三版还引入了最新的研究成果,如近似算法、线性规划和动态规划的更深入探讨,以及新加入的计算几何和网络流等内容,使得这本教材更加全面和实用。无论是初学者还是专业人士,都能从中受益匪浅,提升...

    算法导论第三版及2-25章部分答案

    前者很显然是《算法导论》第三版的电子版,读者可以通过这份PDF文档深入学习书中涵盖的各种算法,如排序、搜索、图算法、动态规划、贪心算法、分治策略等。这些算法是计算机科学的基础,对于提升编程能力和解决复杂...

    算法导论第二版课后答案中文完全版

    首先,这份资源涵盖了算法设计与分析的基本方法,包括分治策略、动态规划、贪心算法以及回溯法等。这些方法是解决各种复杂问题的基石,通过阅读答案,读者可以清晰地看到如何将这些方法应用到具体问题上,从而提升...

    mit算法导论期末试题+答案原版

    - **算法设计方法**:包括分治法、贪心算法、动态规划等。 - **分治法**:将问题分解成若干个规模较小的相同子问题,然后递归地求解这些子问题。 - **贪心算法**:在每个步骤中都采取当前看来最优的选择,以期获得...

    算法导论.epub

    本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通...

    算法导论(第二版)清晰版

    《算法导论》第二版涵盖了广泛的算法主题,包括排序、搜索、图算法、动态规划、贪心算法、分治策略、回溯法、随机化算法以及近似算法等。这些算法在日常编程工作中都有广泛的应用,例如,排序算法中的快速排序、归并...

    中科大算法导论期末考试试卷

    4. **动态规划**:动态规划用于解决最优化问题,如背包问题、最长公共子序列、最小编辑距离等,通过构造状态转移方程来求解。 5. **图论算法**:包括Dijkstra最短路径算法、Floyd-Warshall所有对最短路径、Kruskal...

    算法导论章节答案(31~35章)

    《算法导论》是计算机科学领域的一本经典教材,涵盖了广泛的算法分析和设计技术。这本书的第31至35章包含了许多关键的算法概念,这些章节深入探讨了不同的算法主题,对于理解和掌握算法有着至关重要的作用。以下是这...

    算法导论(第三版)英文原版

    书中还介绍了分治算法、动态规划和贪心算法等经典的算法设计范式。比如,分治法中的主定理(Master Theorem),这是解决递归式复杂度的一个重要工具。书中还提到了概率分析和随机化算法,例如通过雇佣问题来说明随机...

    算法导论 第三版 中文版

    4、修订了动态规划和贪心算法相关内容。 5、流网络相关材料现在基于边上的全部流。 6、由于关于矩阵基础和Strassen算法的材料移到了其他章,矩阵运算这一章的内容所占篇幅更小。 7、修改了对Knuth-Morris-Pratt字符...

    [麻省理工学院-算法导论].rar

    《麻省理工学院-算法导论》是一门深入探讨算法设计与分析的课程资料集合,主要面向具有一定英语基础的学习者。这个压缩包包含了课程的作业、讲义、测试题和教师手册,提供了全面的学习资源。 算法是计算机科学的...

    算法导论 算法导论 算法导论

    《算法导论》是计算机科学领域的一本经典著作,它深入浅出地介绍了算法的设计、分析和实现。这本书广泛应用于大学计算机科学课程,是学习算法的必备参考书。以下是基于《算法导论》的一些核心知识点的详细阐述: 一...

    算法导论第三版答案(完整版)

    《算法导论》是计算机科学领域的一本经典著作,它深入浅出地介绍了算法的设计、分析和实现。这本书的第三版更是集大成者,涵盖了众多重要的算法和数据结构,对于学习和研究计算机科学的人来说是不可或缺的参考书。...

    算法导论讲义\算法导论讲义算法导论讲义\算法导论讲义

    《算法导论》是计算机科学领域的一本经典教材,它深入浅出地介绍了算法的设计、分析和实现。这些讲义来自于MIT(麻省理工学院)的教师,具有极高的学术价值和教学价值,适合计算机科学的学生和专业人士学习。以下是...

Global site tag (gtag.js) - Google Analytics