算法策略间的比较(修改)

1、算法策略算法策略的比较的比较 1. 1. 对问题进行分解的算法策略对问题进行分解的算法策略-分治法分治法 与与 动态规划法动态规划法 2. 2. 多阶段过程多阶段过程 贪婪算法贪婪算法 、 动态规划法动态规划法 3. 3. 全面逐一尝试、比较全面逐一尝试、比较 蛮力法蛮力法 、 枚举法枚举法“ 4 4算法策略的中心思想算法策略的中心思想 上节上节 下节下节4.6.2 4.6.2 算法策略间的关联算法策略间的关联1.对问题进行分解的算法策略 -“分治法”与“动态规划法” “分治法”与“动态规划法”都是递归思想的应用之一，是找出大问题与小的子问题之间的关系,直到小的子问题很容易解决，再由小的子问题

2、的解导出大问题的解。区别在于： 上节 下节 分治法分治法所能解决的问题一般具有以下几个特征：所能解决的问题一般具有以下几个特征： 1) 1) 该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决； 2) 2) 该问题可以分解为若干个规模较小的相同问题。该问题可以分解为若干个规模较小的相同问题。 3) 3) 利用该问题分解出的子问题的解可以合并为该问题的解利用该问题分解出的子问题的解可以合并为该问题的解; ; 4) 4) 该问题所分解出的各个子问题是相互独立的，即子问题该问题所分解出的各个子问题是相互独立的，即子问题 之间不包含公共的子问题。之间不包含公共的

3、子问题。 上节上节 下节下节 第一条特征是绝大多数问题都可以满足的第一条特征是绝大多数问题都可以满足的; ; 第二条特征是应用分治法的前提第二条特征是应用分治法的前提, ,它也是大多数问题可以满足的它也是大多数问题可以满足的; ; 第三条特征是关键。第三条特征是关键。 第四条特征涉及到分治法的效率。第四条特征涉及到分治法的效率。 动态规划的动态规划的实质实质是分治思想和解决冗余。是分治思想和解决冗余。上节上节 下节下节2 2多阶段过程多阶段过程“贪婪算法贪婪算法”、“递推法递推法”、 “递归法递归法”和和“动态规划法动态规划法” 多阶段过程就是按一定顺序多阶段过程就是按一定顺序( (从前向后或

4、从后向前等从前向后或从后向前等) )一一定的策略定的策略, , 逐步解决问题的方法。逐步解决问题的方法。 “ “贪婪算法贪婪算法”每一步根据策略得到一个结果传递到下一每一步根据策略得到一个结果传递到下一步，自顶向下，一步一步地作出贪心选择。步，自顶向下，一步一步地作出贪心选择。 上节上节 下节下节 “动态规划法动态规划法”则根据一定的决策则根据一定的决策, , 每一步决策出的不每一步决策出的不是一个结果，而只是使问题的规模不断的缩小，如果决策比是一个结果，而只是使问题的规模不断的缩小，如果决策比较简单较简单, ,是一般的算法运算是一般的算法运算, ,则可找到不同规模问题间的关系，则可找到不同规

5、模问题间的关系，使算法演变成使算法演变成“递推法递推法”、“递归法递归法”算法算法, ,所以说动态规划所以说动态规划更侧重算法设计策略，而不是算法。更侧重算法设计策略，而不是算法。 “ “递推法递推法”、“递归法递归法”更注重每一步之间的关系更注重每一步之间的关系, ,决策决策的因素较少。的因素较少。“递推法递推法”根据关系从前向后推根据关系从前向后推, ,由小规模的结由小规模的结论论, ,推解出问题的解。推解出问题的解。“递归法递归法”根据关系先从后向前使大问根据关系先从后向前使大问题，转化为小问题，最后同样由小规模结论，推解出问题的题，转化为小问题，最后同样由小规模结论，推解出问题的解。解

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

7、是考虑采用还是考虑采用“动态规划法动态规划法”这个更这个更有效的算法策略有效的算法策略。 上节 下节 枚举法算法的实现枚举法算法的实现依赖于循环依赖于循环, ,通过循环嵌套枚举问题中通过循环嵌套枚举问题中各种可能的情况各种可能的情况, ,如八皇后问题能用八重循环嵌套枚举。而对如八皇后问题能用八重循环嵌套枚举。而对于规模于规模不固定不固定的问题就无法用固定重数的循环嵌套来枚举了的问题就无法用固定重数的循环嵌套来枚举了, ,有的问题可能通过变换枚举对象也能用循环嵌套枚举实现有的问题可能通过变换枚举对象也能用循环嵌套枚举实现, ,但但更多的任意指定规模的问题是靠递归回朔法来更多的任意指定规模的问题是

8、靠递归回朔法来“枚举枚举”或或“遍历遍历”各种可能的情况。比如各种可能的情况。比如n n皇后问题只能用皇后问题只能用“递归回朔递归回朔法法”通过递归实现（当然可以通过栈通过递归实现（当然可以通过栈, ,而不用递归）。而不用递归）。 上节上节 下节下节4 4算法策略的中心思想算法策略的中心思想 所有算法策略的中心思想就是用算法的基本工具循环所有算法策略的中心思想就是用算法的基本工具循环机制和递归机制实现算法。递推法自然不用多说，贪婪算法机制和递归机制实现算法。递推法自然不用多说，贪婪算法就是逐步决策解决问题，动态规划也是。就是逐步决策解决问题，动态规划也是。 上节 下节 4.6.3 4.6.3

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

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

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

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

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

14、心策则难以通过局部的贪心策略达到全局最优解略达到全局最优解; ;如果各子问题是不独立的如果各子问题是不独立的, ,则分治法要做许则分治法要做许多不必要的工作多不必要的工作, ,重复地解公共的子问题。重复地解公共的子问题。 上节上节 下节下节 动态规划在解决不独立子问题时，是分为若干个阶段进行动态规划在解决不独立子问题时，是分为若干个阶段进行的的, ,而且在任一阶段后的行为都仅依赖而且在任一阶段后的行为都仅依赖i i阶段的过程状态阶段的过程状态, , 而与而与i i阶段之前的过程如何达到这种状态的方法无关阶段之前的过程如何达到这种状态的方法无关, ,这样的过程就构这样的过程就构成一个成一个多阶段

15、决策过程多阶段决策过程。 动态规划不仅求出了当前状态到目标动态规划不仅求出了当前状态到目标状态的最优值状态的最优值, ,而且同时求出了到中间状态的最优值。而且同时求出了到中间状态的最优值。 显然显然, ,用枚举的方法从所有可能的决策序列中选取最优决策用枚举的方法从所有可能的决策序列中选取最优决策序列是一种最笨的方法。序列是一种最笨的方法。 上节上节 下节下节 最优性原理最优性原理指出指出, , 过程的过程的最优序列最优序列有如下性质：无论过程的有如下性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一

16、个最优决策序列。所产生的状态构成一个最优决策序列。 如果求解问题的最优性原理成立如果求解问题的最优性原理成立, , 则说明用动态规划方法有则说明用动态规划方法有可能解决该问题。而解决问题的关键在于获得各阶段间的递推关可能解决该问题。而解决问题的关键在于获得各阶段间的递推关系式。因此系式。因此, , 从某种意义上说从某种意义上说动态规划是一种找出子问题间递推动态规划是一种找出子问题间递推或递归关系的方法或递归关系的方法。 动态规划相比一般穷举也存在一定动态规划相比一般穷举也存在一定缺点缺点: :空间占据过多空间占据过多, ,但对但对于空间需求量不大的题目来说于空间需求量不大的题目来说, ,动态规

17、划无疑是最佳方法！动态规划无疑是最佳方法！ 上节 下节图的搜索算法小结 1 1深度优先搜索与广度优先搜索算法有何区别深度优先搜索与广度优先搜索算法有何区别 通常深度优先搜索法不全部保留结点，扩展完的结点从数据存通常深度优先搜索法不全部保留结点，扩展完的结点从数据存储结构栈中弹出删去，这样，一般在数据栈中存储的结点数就是解储结构栈中弹出删去，这样，一般在数据栈中存储的结点数就是解空间树的深度，因此它占用空间较少。所以，当搜索树的结点较多，空间树的深度，因此它占用空间较少。所以，当搜索树的结点较多，用其它方法易产生内存溢出时，深度优先搜索不失为一种有效的求用其它方法易产生内存溢出时，深度优先搜索不

18、失为一种有效的求解方法。解方法。广度优先搜索算法，一般需存储产生的所有结点，占用的存储广度优先搜索算法，一般需存储产生的所有结点，占用的存储空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢出空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢出和节省内存空间的问题。但广度优先搜索法一般无回溯操作，即入和节省内存空间的问题。但广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索要快些。栈和出栈的操作，所以运行速度比深度优先搜索要快些。 上一页 下一页 返回首页 5.52. 2 2回溯与分支限界法回溯与分支限界法 回溯法以深度优先的方式搜索解空间树回溯法以深度优

19、先的方式搜索解空间树T T，而分支限界法则，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树以广度优先或以最小耗费优先的方式搜索解空间树T T。由于它由于它们在问题的解空间树们在问题的解空间树T上搜索的方法不同，适合解决的问题上搜索的方法不同，适合解决的问题也就不同。一般情况下，回溯法的求解目标是找出也就不同。一般情况下，回溯法的求解目标是找出T中满足中满足约束条件的所有解的方案，而分支限界法的求解目标则是找约束条件的所有解的方案，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出出满足约束条件的一个解，或是在满足约束条件的解中找出使用某一目标函数值达到

20、极大或极小的解，即在某种意义下使用某一目标函数值达到极大或极小的解，即在某种意义下的最优解。的最优解。相对而言，分支限界算法的解空间比回溯法大得相对而言，分支限界算法的解空间比回溯法大得多，多， 因此当内存容量有限时，回溯法成功的可能性更大。因此当内存容量有限时，回溯法成功的可能性更大。 下表列出了回溯法和分支限界法的一些区别：下表列出了回溯法和分支限界法的一些区别：上一页 下一页 返回首页 5.53.上一页 下一页 返回首页 5.54. 在处理最优问题时，采用穷举法、回溯法或分支限界法都可以在处理最优问题时，采用穷举法、回溯法或分支限界法都可以通过利用当前最优解和上界函数加速。仅就对限界剪支

21、的效率而通过利用当前最优解和上界函数加速。仅就对限界剪支的效率而言，优先队列的分支限界法显然要更充分一些。在穷举法中通过言，优先队列的分支限界法显然要更充分一些。在穷举法中通过上界函数与当前情况下函数值的比较可以直接略过不合要求的情上界函数与当前情况下函数值的比较可以直接略过不合要求的情况而省去了更进一步的枚举和判断；回溯法则因为层次的划分，况而省去了更进一步的枚举和判断；回溯法则因为层次的划分，可以在上界函数值小于当前最优解时，剪去以该结点为根的子树，可以在上界函数值小于当前最优解时，剪去以该结点为根的子树，也就是节省了搜索范围；分支限界法在这方面除了可以做到回溯也就是节省了搜索范围；分支限

22、界法在这方面除了可以做到回溯法能做到的之外，同时若采用优先队列的分支限界法，用上界函法能做到的之外，同时若采用优先队列的分支限界法，用上界函数作为活结点的优先级，一旦有叶结点成为当前扩展结点，就意数作为活结点的优先级，一旦有叶结点成为当前扩展结点，就意味着该叶结点所对应的解即为最优解，可以立即终止其余的过程。味着该叶结点所对应的解即为最优解，可以立即终止其余的过程。在前面的例题中曾说明，优先队列的分支限界法更象是有选择、在前面的例题中曾说明，优先队列的分支限界法更象是有选择、有目的地进行深度优先搜索，时间效率、空间效率都是比较高的。有目的地进行深度优先搜索，时间效率、空间效率都是比较高的。上一

23、页 下一页 返回首页 5.55. 3动态规划与搜索算法动态规划与搜索算法 撇开时空效率的因素不谈，在解决最优化问题的算法中，搜索撇开时空效率的因素不谈，在解决最优化问题的算法中，搜索可以说是可以说是“万能万能”的。所以动态规划可以解决的问题，搜索也一的。所以动态规划可以解决的问题，搜索也一定可以解决。动态规划要求阶段决策具有无后向性，而搜索算法定可以解决。动态规划要求阶段决策具有无后向性，而搜索算法没有此限止。没有此限止。 动态规划是自底向上的递推求解，而无论深度优先搜索或广度动态规划是自底向上的递推求解，而无论深度优先搜索或广度优先搜索都是自顶向下求解。利用动态规划法进行算法设计时，优先搜索

24、都是自顶向下求解。利用动态规划法进行算法设计时，设计者在进行算法设计前已经用大脑自己构造好了问题的解空间，设计者在进行算法设计前已经用大脑自己构造好了问题的解空间，因此可以自底向上的递推求解；而搜索算法是在搜索过程中根据因此可以自底向上的递推求解；而搜索算法是在搜索过程中根据一定规则自动构造，并搜索解空间树的。由于在很多情况下，问一定规则自动构造，并搜索解空间树的。由于在很多情况下，问题的解空间太复杂用大脑构造有一定困难，仍然需要采用搜索算题的解空间太复杂用大脑构造有一定困难，仍然需要采用搜索算法。法。上一页 下一页 返回首页 5.5 另外动态规划在递推求解过程中，需要用数组存储有关信息，另外

25、动态规划在递推求解过程中，需要用数组存储有关信息，而数组的下标只能是整数，所以要求问题中相关的数据必须为而数组的下标只能是整数，所以要求问题中相关的数据必须为整数，对于这类信息非整数或不便于转换为整数的问题，同样整数，对于这类信息非整数或不便于转换为整数的问题，同样需要采用搜索算法。需要采用搜索算法。 一般说来，动态规划算法在时间效率上的优势是搜索无法比一般说来，动态规划算法在时间效率上的优势是搜索无法比拟的，但动态规划总要遍历所有的状态，而搜索可以排除一些拟的，但动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。更重要的是搜索还可以剪枝，可能剪去大量不必要无效状态。更重要的是搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。如何协的状态，因此在空间开