小结-贪心、动态、分治、回溯等.pptxVIP

算法策略间的比较1算法策略和算法是有区别的,它们是算法设计中的两个方面，算法策略是面向问题的,算法是面向实现的；但二者又是不可分的,首先是通过算法策略才找出解决问题的算法，其次对于用不同算法求解的问题算法策略是自然不同的。

“贪婪算法”2这些策略求解的是最简单的一类问题，或者说是对问题要求最严格的算法策略。“贪婪算法”解决这类问题是按一定顺序（从前向后或从后向前等）一定的策略，只需考虑当前局部信息就能做出决策，即所谓局部最优就是全局最优。上节下节12

不同算法策略特点小结3“贪婪算法”01“分治法”01“动态规划法”“基于枚举思想的算法”(回朔法,分枝定界)01

“回朔法”4No.1类似于枚举法的思想,回朔法通过递归尝试遍问题各个可能解的通路，发现此路不通时回朔到上一步继续尝试别的通路。类似的还有分支定界算法。No.2上节下节

“分治法”5求解的则是较复杂的问题，这类问题是可以被分解成独立的子问题来解决的，将两个或两个以上的独立子问题的解“合成”，就得到较大的子问题的解，最后合成为总问题的解。上节下节12

“动态规划法”6动态规划法与贪心法类似，是通过多阶段决策过程来解决问题的。但每个阶段决策的结果是一个决策结果序列，这个结果序列中最后采用哪一个结果取决于以后每个阶段决策，因此称为“动态”规划法。当然每一次的决策结果序列都必须进行存储。因此，可以说“动态规划是高效率、高消费的算法”。另一方面，动态规划法与分治法类似，当问题不能分解为独立的子问题,但又符合最优化原理(最优子结构性质)时,用动态规划，通过多阶段决策过程从逐步找出子问题的最优解，从而决策出问题的结果。上节下节

算法策略间的关联7对问题进行分解的算法策略---分治法与动态规划法多阶段过程贪婪算法、动态规划法全面逐一尝试（带有选择性的）、比如“回溯法”、“分支定界算法”上节下节010302

对问题进行分解的算法策略01--“分治法”与“动态规划法”01“分治法”与“动态规划法”都是递归思想的应用之一，是找出大问题与小的子问题之间的关系,直到小的子问题很容易解决，再由小的子问题的解导出大问题的解。区别在于：01

9分治法所能解决的问题一般具有以下几个特征：1)该问题的规模缩小到一定的程度就可以容易地解决；2)该问题可以分解为若干个规模较小的相同问题。3)利用该问题分解出的子问题的解可以合并为该问题的解;4)该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。第一条特征是绝大多数问题都可以满足的;第二条特征是应用分治法的前提,它也是大多数问题可以满足的;第三条特征是关键。第四条特征涉及到分治法的效率。动态规划的实质是分治思想和解决冗余。

多阶段过程“贪婪算法”和“动态规划法”多阶段过程就是按一定顺序(从前向后或从后向前等)一定的策略,逐步解决问题的方法。“贪婪算法”每一步根据策略得到一个结果传递到下一步，自顶向下，一步一步地作出贪心选择。“动态规划法”则根据一定的决策,每一步决策出的不是一个结果，而只是使问题的规模不断的缩小。

全面逐一尝试、“枚举法”和“回溯法”考虑到有这样一类问题，问题中不易找到信息间的相互关系，也不能分解为独立的子问题,似乎只有把各种可能情况都考虑到,并把全部解都列出来之后,才能判定和得到最优解。对于规模不大的问题，这些策略简单方便;而当问题的计算复杂度高且计算量很大时,还是考虑采用“动态规划法”这个更有效的算法策略。

枚举法算法的实现依赖于循环,通过循环嵌套枚举问题中各种可能的情况,如八皇后问题能用八重循环嵌套枚举。而对于规模不固定的问题就无法用固定重数的循环嵌套来枚举了,有的问题可能通过变换枚举对象也能用循环嵌套枚举实现,但更多的任意指定规模的问题是靠回朔法来“枚举”或“遍历”各种可能的情况。比如图的着色问题能用“回朔法”通过递归实现。

4．算法策略的中心思想13所有算法策略的中心思想就是用算法的基本工具循环机制和递归机制实现算法。递推法自然不用多说，贪婪算法就是逐步决策解决问题，动态规划也是。01上节下节02

算法策略侧重的问题类型一般我们在实际应用中遇到的问题主要分为四类:判定性问题、计算问题、最优化问题和构造性问题。递推法、递归法算法较适合解决判定性问题、计算问题。“贪婪算法”、“分治法”、“动态规划法”与“枚举法”较适合解最优化问题。构造性问题更多地依赖于人的经验和抽象能力，算法一般是人类智能充分对问题解决步骤细化后才能得到算法，少有通用的算法策略。当然也有一些问题在构造过程中使用通用的算法策略。

下面就最优化问题讨论如下：在现实生活中，有这样的问题：他有n个输入