五大常用算法

五种常用算法的整理总结：分治算法、动态规划算法、贪心算法、分支界限法、回溯法。

五大常用算法

• 分治算法
  • 递归
  • 基本思想
    • 将一个难以解决的大问题，分解成若干规模较小的子问题，分而治之，后合并得到原问题的解
  • 适用情况
    • ①可以分解成若干个规模较小的相同问题
    • ②规模缩小到一定程度可以更容易的解决
    • ③各子问题的解可以合并为原问题的解
    • ④各子问题之间相互独立
  • 基本步骤
    • 分解：将原问题分解为若干个规模较小、相互独立，与原问题形式相同的子问题
    • 解决：若子问题规模较小容易被解决则直接解，否则递归的解各个子问题
    • 合并：将各个子问题的解合并为原问题的解
  • 应用
    • 二分搜索
    • 快速排序
    • 归并排序
    • 棋盘覆盖
    • 汉诺塔
• 动态规划算法
  • 递推
  • 基本思想
    • 将原问题分为若干阶段的子问题，按顺序求解每个阶段的局部最优解，并为下一阶段提供了相关信息，当求出最后阶段的最优解就是原问题的解。
      • 每一次决策都会引起状态的转移，是在动态变化中求解的，故称“动态规划”
  • 适用情况
    • ①满足最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理
    • ②无后效性：之后的决策不会影响之前的状态
    • ③有重叠子问题：子问题之间不独立，一个子问题在之后的决策中可能被多次用到
  • 基本步骤
    • 划分阶段：
      • 按照问题的时间or空间特征，把问题分为若干阶段。（划分后的阶段一定是有序或可排序的）
    • 确定状态和状态变量：
      • 将问题发展到各个阶段时所处的状态，并用合适的状态变量表示。（状态选择要满足无后效性）
    • 确定决策并写出状态转移方程：
      • 根据相邻两阶段的状态间关系确定决策，并写出状态转移方程。
    • 寻找边界条件：
      • 状态转移方程是一个递推式，需要递推的终止条件或边界条件。
    • 三要素
      • 问题的阶段
      • 每个阶段的状态
      • 递推关系
  • 应用
    • 斐波那契序列
    • 0/1背包问题
• 回溯法
  • 深度优先策略
  • 基本思想
    • 即深度优先策略。沿着一条路走下去，如果此路不通了，回到上一个分叉口选另一条路继续走，直到遍历完所有路径
  • 应用
    • 深度优先搜索
    • 二叉树先序遍历
    • 八皇后问题
    • 迷宫问题
• 分支界限法
  • 广度优先策略
  • 基本思想
    • 即广度优先策略。分层展开检查所有节点，直到找到最终结果。
  • 应用
    • 广度优先搜索
    • Dijkstra求最短路
    • prim算法
• 贪心算法
  • 大部分情况下易于实现，且效率不错
  • 基本思想
    • 在对问题求解时，总是做出在当前看来最好的选择，不能保证全局最优，但可能较优
  • 适用情况
    • 无后效性
    • 最好局部最优策略能导致产生全局最优解
  • 应用
    • Dijkstra求最短路
    • prim算法
    • Kruskal算法
    • 旅行商问题