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

1、1 算法策略和算法是有区别的算法策略和算法是有区别的, ,它们是算法设计中的两个方它们是算法设计中的两个方面，算法策略是面向问题的面，算法策略是面向问题的, ,算法是面向实现的；但二者又是算法是面向实现的；但二者又是不可分的不可分的, ,首先是通过算法策略才找出解决问题的算法，其次首先是通过算法策略才找出解决问题的算法，其次对于用不同算法求解的问题算法策略是自然不同的。对于用不同算法求解的问题算法策略是自然不同的。 算法策略间的比较2 “贪婪算法贪婪算法” 这些策略求解的是最简单的一类问题，或者说是对问这些策略求解的是最简单的一类问题，或者说是对问题要求最严格的算法策略。题要求最严格的算法策略

2、。“贪婪算法贪婪算法”解决这类问题是解决这类问题是按一定顺序（从前向后或从后向前等）一定的策略，只需按一定顺序（从前向后或从后向前等）一定的策略，只需考虑当前局部信息就能做出决策，即所谓局部最优就是全考虑当前局部信息就能做出决策，即所谓局部最优就是全局最优。局最优。 上节上节 下节下节3 “贪婪算法贪婪算法”“分治法分治法”“动态规划法动态规划法”“基于枚举思想的算法基于枚举思想的算法”( (回朔法回朔法, ,分枝定分枝定界界) ) 不同算法策略特点小结4 “回朔法回朔法” 类似于枚举法的思想类似于枚举法的思想, ,回朔法通过递归尝试遍问题各个回朔法通过递归尝试遍问题各个可能解的通路，发现此路

3、不通时回朔到上一步继续尝试别的可能解的通路，发现此路不通时回朔到上一步继续尝试别的通路。类似的还有分支定界算法。通路。类似的还有分支定界算法。 上节上节 下节下节5 “分治法分治法” 求解的则是较复杂的问题，这类问题是可以被分解成独求解的则是较复杂的问题，这类问题是可以被分解成独立的子问题来解决的，将两个或两个以上的独立子问题的解立的子问题来解决的，将两个或两个以上的独立子问题的解“合成合成”，就得到较大的子问题的解，最后合成为总问题的，就得到较大的子问题的解，最后合成为总问题的解。解。 上节上节 下节下节6 “动态规划法动态规划法” 动态规划法与贪心法类似，是通过多阶段决策过程来解动态规划法

4、与贪心法类似，是通过多阶段决策过程来解决问题的。但每个阶段决策的结果是一个决策结果序列，这决问题的。但每个阶段决策的结果是一个决策结果序列，这个结果序列中最后采用哪一个结果取决于以后每个阶段决策，个结果序列中最后采用哪一个结果取决于以后每个阶段决策，因此称为因此称为“动态动态”规划法。当然每一次的决策结果序列都必规划法。当然每一次的决策结果序列都必须进行存储。因此，可以说须进行存储。因此，可以说“动态规划是高效率、高消费的动态规划是高效率、高消费的算法算法”。 另一方面，动态规划法与分治法类似，当问题不能分解另一方面，动态规划法与分治法类似，当问题不能分解为独立的子问题为独立的子问题, ,但又

5、符合最优化原理但又符合最优化原理( (最优子结构性质最优子结构性质) )时时, ,用动态规划，通过多阶段决策过程从逐步找出子问题的最优用动态规划，通过多阶段决策过程从逐步找出子问题的最优解，从而决策出问题的结果。解，从而决策出问题的结果。 上节上节 下节下节7 1. 1. 对问题进行分解的算法策略对问题进行分解的算法策略-分治法分治法 与与 动态规划法动态规划法 2. 2. 多阶段过程多阶段过程 贪婪算法贪婪算法 、 动态规划法动态规划法 3. 3. 全面逐一尝试（带有选择性的）、比如全面逐一尝试（带有选择性的）、比如“回溯法回溯法”、“分支分支定界算法定界算法” 上节上节 下节下节算法策略间

6、的关联8对问题进行分解的算法策略 -“分治法”与“动态规划法” “分治法分治法”与与“动态规划法动态规划法”都是递归思想的应用之一，都是递归思想的应用之一，是找出大问题与小的子问题之间的关系是找出大问题与小的子问题之间的关系, ,直到小的子问题很容直到小的子问题很容易解决，再由小的子问题的解导出大问题的解。区别在于：易解决，再由小的子问题的解导出大问题的解。区别在于：9 分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征： 1) 1) 该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决； 2) 2) 该问题可以分解为若干个

7、规模较小的相同问题。该问题可以分解为若干个规模较小的相同问题。 3) 3) 利用该问题分解出的子问题的解可以合并为该问题的解利用该问题分解出的子问题的解可以合并为该问题的解; ; 4) 4) 该问题所分解出的各个子问题是相互独立的，即子问题该问题所分解出的各个子问题是相互独立的，即子问题 之间不包含公共的子问题。之间不包含公共的子问题。 第一条特征是绝大多数问题都可以满足的第一条特征是绝大多数问题都可以满足的; ; 第二条特征是应用分治法的前提第二条特征是应用分治法的前提, ,它也是大多数问题可以满它也是大多数问题可以满足的足的; ; 第三条特征是关键。第三条特征是关键。 第四条特征涉及到分治

8、法的效率。第四条特征涉及到分治法的效率。 动态规划的实质是分治思想和解决冗余。动态规划的实质是分治思想和解决冗余。10多阶段过程多阶段过程“贪婪算法贪婪算法”和和“动态规划法动态规划法” 多阶段过程就是按一定顺序多阶段过程就是按一定顺序( (从前向后或从后向前等从前向后或从后向前等) )一一定的策略定的策略, , 逐步解决问题的方法。逐步解决问题的方法。 “ “贪婪算法贪婪算法”每一步根据策略得到一个结果传递到下一每一步根据策略得到一个结果传递到下一步，自顶向下，一步一步地作出贪心选择。步，自顶向下，一步一步地作出贪心选择。 “ “动态规划法动态规划法”则根据一定的决策则根据一定的决策, ,

9、每一步决策出的不每一步决策出的不是一个结果，而只是使问题的规模不断的缩小。是一个结果，而只是使问题的规模不断的缩小。11全面逐一尝试、全面逐一尝试、“枚举法枚举法”和和“回溯法回溯法” 考虑到有这样一类问题，问题中不易找到信息间的相互考虑到有这样一类问题，问题中不易找到信息间的相互关系，也不能分解为独立的子问题关系，也不能分解为独立的子问题, ,似乎只有把各种可能情况似乎只有把各种可能情况都考虑到都考虑到, ,并把全部解都列出来之后并把全部解都列出来之后, ,才能判定和得到最优解。才能判定和得到最优解。对于规模不大的问题，这些策略简单方便对于规模不大的问题，这些策略简单方便; ;而当问题的计算

10、复而当问题的计算复杂度高且计算量很大时杂度高且计算量很大时, ,还是考虑采用还是考虑采用“动态规划法动态规划法”这个更这个更有效的算法策略有效的算法策略。12 枚举法算法的实现依赖于循环枚举法算法的实现依赖于循环, ,通过循环嵌套枚举问题中通过循环嵌套枚举问题中各种可能的情况各种可能的情况, ,如八皇后问题能用八重循环嵌套枚举。而对如八皇后问题能用八重循环嵌套枚举。而对于规模不固定的问题就无法用固定重数的循环嵌套来枚举了于规模不固定的问题就无法用固定重数的循环嵌套来枚举了, ,有的问题可能通过变换枚举对象也能用循环嵌套枚举实现有的问题可能通过变换枚举对象也能用循环嵌套枚举实现, ,但但更多的任

11、意指定规模的问题是靠回朔法来更多的任意指定规模的问题是靠回朔法来“枚举枚举”或或“遍历遍历”各种可能的情况。比如图的着色问题能用各种可能的情况。比如图的着色问题能用“回朔法回朔法”通过递通过递归实现。归实现。134 4算法策略的中心思想算法策略的中心思想 所有算法策略的中心思想就是用算法的基本工具循环所有算法策略的中心思想就是用算法的基本工具循环机制和递归机制实现算法。递推法自然不用多说，贪婪算法机制和递归机制实现算法。递推法自然不用多说，贪婪算法就是逐步决策解决问题，动态规划也是。就是逐步决策解决问题，动态规划也是。 上节 下节14 算法策略侧重的问题类型算法策略侧重的问题类型 一般我们在实

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

13、问题解决步骤细化后才能得到算法，少有通用的算法策略。当然也有一些问题在构造过程中使用通用的算法策略。算法策略。当然也有一些问题在构造过程中使用通用的算法策略。15下面就最优化问题讨论如下：下面就最优化问题讨论如下： 在现实生活中，有这样的问题：他有在现实生活中，有这样的问题：他有n n个输入个输入, , 而他的解就而他的解就由由n n个输入的某个子集组成，只是这个子集必须满足某些事先给个输入的某个子集组成，只是这个子集必须满足某些事先给定的条件。把那些必须满足的条件称为约束条件定的条件。把那些必须满足的条件称为约束条件; ;而把满足约定而把满足约定条件的子集称为该问题的可行解。显然条件的子集称

14、为该问题的可行解。显然, ,满足约束条件的子集可满足约束条件的子集可能不止一个能不止一个, ,因此，可行解一般来说是不唯一的。为了衡量可行因此，可行解一般来说是不唯一的。为了衡量可行解的优劣，事先也给出了一定的标准解的优劣，事先也给出了一定的标准, ,这些标准一般以函数形式这些标准一般以函数形式给出给出, , 这些函数称为目标函数。这些函数称为目标函数。 那些使目标函数取极值的可行那些使目标函数取极值的可行解，解， 称为最优解称为最优解, , 这一类需求取最优解的问题这一类需求取最优解的问题, , 又可根据描述又可根据描述约束条件和目标函数的约束条件和目标函数的 数学模型的特性或求借问题方法的

15、不同数学模型的特性或求借问题方法的不同进行而细分为进行而细分为 线形规则、整数规则、非线形规则、动态规划等线形规则、整数规则、非线形规则、动态规划等问题。问题。16 尽管各类规划问题都有一些相应的求解方法，但其中的某尽管各类规划问题都有一些相应的求解方法，但其中的某些问题，还可用一种更直接的方法来求解，这种方法就叫贪心些问题，还可用一种更直接的方法来求解，这种方法就叫贪心方法。方法。 动态规划法是将问题实例归纳为更小的、动态规划法是将问题实例归纳为更小的、 相似的子问题相似的子问题, , 并通过求解子问题产生一个全局最优解。其中贪心法的当前选并通过求解子问题产生一个全局最优解。其中贪心法的当前

16、选择可能要依赖已经作出的所有选择择可能要依赖已经作出的所有选择, , 但不依赖于有待于做出的但不依赖于有待于做出的选择和子问题。选择和子问题。 而分治法中的各个子问题是独立的而分治法中的各个子问题是独立的( (即不包含即不包含公共的子子问题公共的子子问题),),因此一旦递归地求出各子问题的解后，便可因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。但不足的是自下而上地将子问题的解合并成问题的解。但不足的是, , 如果如果当前选择可能要依赖子问题的解时当前选择可能要依赖子问题的解时, , 则难以通过局部的贪心策则难以通过局部的贪心策略达到全局最优解略达到全局最优解; ;

17、如果各子问题是不独立的如果各子问题是不独立的, ,则分治法要做许则分治法要做许多不必要的工作多不必要的工作, ,重复地解公共的子问题。重复地解公共的子问题。 17 动态规划在解决不独立子问题时，是分为若干个阶段进行动态规划在解决不独立子问题时，是分为若干个阶段进行的的, ,而且在任一阶段后的行为都仅依赖而且在任一阶段后的行为都仅依赖i i阶段的过程状态阶段的过程状态, , 而与而与i i阶段之前的过程如何达到这种状态的方法无关阶段之前的过程如何达到这种状态的方法无关, ,这样的过程就构这样的过程就构成一个多阶段决策过程。成一个多阶段决策过程。 动态规划不仅求出了当前状态到目标动态规划不仅求出了当前状态到目标状态的最优值状态的最优值, ,而且同时求出了到中间状态的最优值。而且同时求出了到中间状态的最优值。 显然显然, ,用枚举的方法从所有可能的决策序列中选取最优决策用枚举的方法从所有可能的决策序列中选取最优决策序列是一种最笨的方法。序列是一种最笨的方法。18 最优性原理指出最优性原理指出, , 过程的最优序列有如下性质：无论过程的过程的最优序列有如下性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。所产生的状态构成一个最优决策序列。 如果求解问题的最优性原理成