2021-06-26动规相关算法

回溯算法

概念

1. 类似枚举搜索，枚举所有解，找到满足期望的解。
2. 把问题求解的过程分为多个阶段。每个阶段都会面对一个岔路口，先随机选一条路走。
3. 当发现此路不通（不符合期望解），就回退到上一个岔路口，另选一条走法继续走。

实现

递归

和深度优先的区别

1. 深度优先遍历的目的是“遍历”，本质是无序的。
2. 回溯法的目的是 “求解”，本质是有序的。

应用

1. 深度优先搜索（DFS）。
2. 八皇后
3. 0-1背包问题
4. 图的着色
5. 旅行商问题
6. 数独
7. 全排列
8. 正则表达式匹配。

动态规划

概念

一个模型（多阶段决策最优解模型）

1. 解决问题的过程，需要经历多个决策阶段。
2. 每个阶段都对应着一组状态。
3. 寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。

三个特征

• 最优子结构
  • 通过子问题的最优解，推导出问题的最优解。
• 无后效性
  1. 再推到后面阶段的状态的时候，只关心前面阶段的状态值，不关心是怎么一步步推导出来的。
  2. 某个阶段一旦确定，就不受之后阶段决策的影响。
• 重复字问题
  • 不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。

特点

1. 从最简单的问题开始，一点点的把问题复杂起来，在这个过程中找寻复杂问题是如何依赖简单问题的。
2. 需要记忆前面问题的解，然后用简单问题的解来求解复杂问题的解。

和分治的区别

1. 分治是自上向下解决问题。
2. 动规是自下向上解决问题。

解题思路

1. 状态转移表法：
   • 回溯算法实现 --定义状态 -- 画递归树 -- 找重复子问题 -- 画状态转移表 -- 根据对推关系填表 -- 将填表过程翻译成代码
2. 状态转移方程法
   • 找最优子结构 -- 写状态转移方程 -- 将状态转移方程翻译成代码

贪心算法

概念

每一步选择都采取当前状态下最有利的选择，从而希望结果是最优的。[无后效性]

应用

1. 适用场景比较有限，更多的是指导设计基础算法。
2. 经典应用有：
   • 霍夫曼编码、
   • Prim和Kruskal最小生成树算法、
   • Dijkstra单源最短路径算法。

解题步骤

1. 当遇到问题的时候，首先要联想到贪心算法。
2. 尝试看看问题是否可以用贪心算法解决。
3. 举几个例子看看贪心算法产生的结果是否是最优解。

分治算法

概念

1. 将原问题划分成n个规模较小，结构与原问题相似的子问题。
2. 递归的解决这些子问题，然后在合并其结果，就得到原问题的解。

和递归的区别

1. 分治算法是一种处理问题的思想。
2. 递归是一种编程技巧。
3. 分治算法一般比较适合用递归来实现。

实现

1. 分解
   • 将原问题分解为子问题
2. 解决
   • 递归的求解各个子问题，若子问题足够小，就直接求解。
3. 合并
   • 将子问题的结果合并成原问题。

应用条件

1. 原问题与子问题模式相同。
2. 原问题分解成的子问题可以独立求解，子问题之间没有相关性。
3. 具有分解终止条件
4. 可以将子问题合并成原问题。