1.贪心算法
1.1 简介
- 贪心算法（又称贪婪算法），在求解问题时，总是做出在当前看来是最好的选择。也就是说，不从整体最优解进行考虑，而是得到某种意义上的局部最优解。
- 贪心算法采用自顶向下，以迭代的方法做出贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的问题。
- 每一次的贪心选择可得到问题的一个最优解，虽然能够保证每一步所获得的是局部最优解，但是不能保证全局解是最优的。
- 适用贪心算法解决问题的前提是：局部最优策略能够得到全局最优解
2.2 例题
- 钱币找零问题
- 活动选择问题
- 多机调度问题
- 小船过河问题
2.分治算法
2.1 简介
- 分值算法是将一个规模为N的问题分解为K个规模较小的子问题
- 这些子问题相互独立且与原问题性质相同
- 求出子问题的解，就可以得到原问题的解
2.2 解题步骤
- 分解：将要解决的问题分解成若干个子问题
- 求解：求解子问题
- 合并：合并子问题的解组成原问题的解
2.3 例题
- 二分搜索
- 大整数乘法
- Strassen矩阵乘法
- 棋盘覆盖
- 合并排序
- 快速排序
- 线性时间选择
- 最接近点对问题
- 汉诺塔
2.4 分治与递归的关系
- 分治是一种处理问题的思想，递归则是一种编程技巧
- 实际情况中，分治算法大都采用递归来实现
3.回溯算法
3.1 简介
- 是一个类似枚举的搜索尝试过程，主要是在搜索尝试中求解，当不满足条件时就“回溯”返回，尝试别的路径
3.2 解题步骤
- 确定了解空间的组织结构后，回溯法就从开始结点（根节点）出发，以深度优先（DFS）的方式遍历搜索整个空间
- 这个开始的结点就成为一个活结点，同时也成为当前的拓展结点
- 依次移动，当结点不能够再移动的时候，则当前拓展结点就成为死结点，此时应该往回移动（回溯）到最近的一个活结点处
- 直到没有活结点时
3.3 例题
- 八皇后问题
- 装载问题
- 批量作业调度问题
4.动态规划算法
4.1 简介
- DP是求解决策过程最优化的过程，能获得全局最优解
- 动态规划算法与分治法类似，其基本思想也是将待求解问题分成若干个子问题，先求解子问题，然后再从这些子问题中的解得到原问题的解
- 不同之处：
- 1.分治法分解的子问题相互独立，而动态规划发分解的子问题不是相互独立的
- 2.分治自顶向下，动态规划自底向上
- 需要在给定约束条件下优化某种指标时，动态规划很有用
- 每种动态规划解决方案都涉及网格，单元格中的值通常就是要优化的值
4.2 应用场景
- 具有最优子结构性质：问题的最优解包含子问题的最优解，反过来说就是，我们可以通过子问题的最优解推导出问题的最优解
- 无后效性：只关心前面阶段的状态值，而不关心这个状态是怎么一步一步推导出来的
- 具有重叠子问题的问题：子问题不是相互独立的
4.3 例题
- 游艇租聘
- 0-1背包问题
- 跳台阶问题
- 强盗抢劫问题
文章来源地址https://www.toymoban.com/news/detail-611955.html
文章来源：https://www.toymoban.com/news/detail-611955.html
到了这里，关于四大算法：贪心、分治、回溯、动态规划的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
