文档介绍：“贪婪算法”
这些策略求解的是最简单的一类问题，或者说是对问题要求最严格的算法策略。“贪婪算法”解决这类问题是按一定顺序（从前向后或从后向前等）一定的策略，只需考虑当前局部信息就能做出决策，即所谓局部最优就是全局最优。
上节 下节
1
小结-贪心、动态、分治、回溯等
2021/1/13
“贪婪算法”
“分治法”
“动态规划法”
“基于枚举思想的算法”(回朔法,分枝定界)
不同算法策略特点小结
2
小结-贪心、动态、分治、回溯等
2021/1/13
“回朔法”
类似于枚举法的思想,回朔法通过递归尝试遍问题各个可能解的通路，发现此路不通时回朔到上一步继续尝试别的通路。类似的还有分支定界算法。
上节 下节
3
小结-贪心、动态、分治、回溯等
2021/1/13
“分治法”
求解的则是较复杂的问题，这类问题是可以被分解成独立的子问题来解决的，将两个或两个以上的独立子问题的解“合成”，就得到较大的子问题的解，最后合成为总问题的解。
上节 下节
4
小结-贪心、动态、分治、回溯等
2021/1/13
“动态规划法”
动态规划法与贪心法类似，是通过多阶段决策过程来解决问题的。但每个阶段决策的结果是一个决策结果序列，这个结果序列中最后采用哪一个结果取决于以后每个阶段决策，因此称为“动态”规划法。当然每一次的决策结果序列都必须进行存储。因此，可以说“动态规划是高效率、高消费的算法”。
另一方面，动态规划法与分治法类似，当问题不能分解为独立的子问题,但又符合最优化原理(最优子结构性质)时,用动态规划，通过多阶段决策过程从逐步找出子问题的最优解，从而决策出问题的结果。
上节 下节
5
小结-贪心、动态、分治、回溯等
2021/1/13
1. 对问题进行分解的算法策略---"分治法"与"动态规划法"
2. 多阶段过程"贪婪算法"、"动态规划法"
3. 全面逐一尝试（带有选择性的）、比如“回溯法”、“分支定界算法”
上节 下节
算法策略间的关联
6
小结-贪心、动态、分治、回溯等
2021/1/13
对问题进行分解的算法策略
---“分治法”与“动态规划法”
“分治法”与“动态规划法”都是递归思想的应用之一，是找出大问题与小的子问题之间的关系,直到小的子问题很容易解决，再由小的子问题的解导出大问题的解。区别在于：
7
小结-贪心、动态、分治、回溯等
2021/1/13
分治法所能解决的问题一般具有以下几个特征：
1) 该问题的规模缩小到一定的程度就可以容易地解决；
2) 该问题可以分解为若干个规模较小的相同问题。
3) 利用该问题分解出的子问题的解可以合并为该问题的解;
4) 该问题所分解出的各个子问题是相互独立的，即子问题
之间不包含公共的子问题。
第一条特征是绝大多数问题都可以满足的;
第二条特征是应用分治法的前提,它也是大多数问题可以满足的;
第三条特征是关键。
第四条特征涉及到分治法的效率。
动态规划的实质是分治思想和解决冗余。
8
小结-贪心、动态、分治、回溯等
2021/1/13
多阶段过程“贪婪算法”和“动态规划法”
多阶段过程就是按一定顺序(从前向后或从后向前等)一定的策略, 逐步解决问题的方法。
“贪婪算法”每一步根据策略得到一个结果传递到下一步，自顶向下，一步一步地作出贪心选择。
“动态规划法”则根据一定的决策, 每一步决策出的不是一个结果，而只是使问题的规模不断的缩小。
9
小结-贪心、动态、分治、回溯等
2021/1/13
全面逐一尝试、“枚举法”和“回溯法”
考虑到有这样一类问题，问题中不易找到信息间的相互关系，也不能分解为独立的子问题,似乎只有把各种可能情况都考虑到,并把全部解都列出来之后,才能判定和得到最优解。对于规模不大的问题，这些策略简单方便;而当问题的计算复杂度高且计算量很大时,还是考虑采用“动态规划法”这个更有效的算法策略。
10
小结-贪心、动态、分治、回溯等
2021/1/13