一般实际生活中我们遇到的算法分为四类:
一>判定性问题
二>最优化问题
三>构造性问题
四>计算性问题
而今天所要总结的算法就是着重解决 最优化问题
《算法之道》对三种算法进行了归纳总结,如下表所示:
|
标准分治
|
动态规划
|
贪心算法
|
适用类型
|
通用问题
|
优化问题
|
优化问题
|
子问题结构
|
每个子问题不同
|
很多子问题重复(不独立)
|
只有一个子问题
|
最优子结构
|
不需要
|
必须满足
|
必须满足
|
子问题数
|
全部子问题都要解决
|
全部子问题都要解决
|
只要解决一个子问题
|
子问题在最优解里
|
全部
|
部分
|
部分
|
选择与求解次序
|
先选择后解决子问题
|
先解决子问题后选择
|
先选择后解决子问题
|
分治算法特征:
1)规模如果很小,则很容易解决。//一般问题都能满足
2)大问题可以分为若干规模小的相同问题。//前提
3)利用子问题的解,可以合并成该问题的解。//关键
4)分解出的各个子问题相互独立,子问题不再包含公共子问题。 //效率高低
【一】动态规划:
依赖:依赖于有待做出的最优选择
实质:就是分治思想和解决冗余。
自底向上(每一步,根据策略得到一个更小规模的问题。最后解决最小规模的问题。得到整个问题最优解)
特征:动态规划任何一个i+1阶段都仅仅依赖 i 阶段做出的选择。而与i之前的选择无关。但是动态规划不仅求出了当前状态最优值,而且同时求出了到中间状态的最优值。
缺点:空间需求大。
【二】贪心算法:
依赖:依赖于当前已经做出的所有选择。
自顶向下(就是每一步,根据策略得到一个当前最优解。传递到下一步,从而保证每一步都是选择当前最优的。最后得到结果)
【三】分治算法:
实质:递归求解
缺点:如果子问题不独立,需要重复求公共子问题
分享到:
相关推荐
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。《算法导论(原书第2版...
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通...
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通...
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通...
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通...
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通...
4、修订了动态规划和贪心算法相关内容。 5、流网络相关材料现在基于边上的全部流。 6、由于关于矩阵基础和Strassen算法的材料移到了其他章,矩阵运算这一章的内容所占篇幅更小。 7、修改了对Knuth-Morris-Pratt字符...
•修订了动态规划和贪心算法相关内容。 •流网络相关材料现在基于边上的全部流。 •由于关于矩阵基础和Strassen算法的材料移到了其他章,矩阵运算这一章的内容所占篇幅更小。 •修改了对Knuth-Morris-Pratt字符串...
书中专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。此书还介绍了对强连通...
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通...
书中专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。此书还介绍了对强连通...
书中专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。此书还介绍了对强连通...
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。《算法导论(原书第2版...
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通...
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通...
修订了动态规划和贪心算法相关内容。 流网络相关材料现在基于边上的全部流。 由于关于矩阵基础和strassen算法的材料移到了其他章,矩阵运算这一章的内容所占篇幅更小。 修改了对knuth-morris-pratt字符串...
算法导论第二版 英文 外加习题解析 描述了 贪心,动态规划,递归等算法,还有各种数据结构,如hash,二叉树,红黑树,线段树等,以及数论和网络流
本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通...