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

1,算法策略和算法是有区别的,它们是算法设计中的两个方面，算法策略是面向问题的,算法是面向实现的；但二者又是不可分的,首先是通过算法策略才找出解决问题的算法，其次对于用不同算法求解的问题算法策略是自然不同的。,算法策略间的比较,2,“贪婪算法”这些策略求解的是最简单的一类问题，或者说是对问题要求最严格的算法策略。“贪婪算法”解决这类问题是按一定顺序（从前向后或从后向前等）一定的策略，只需考虑当前局部信息就能做出决策，即所谓局部最优就是全局最优。上节 下节,3,“贪婪算法”“分治法”“动态规划法”“基于枚举思想的算法”(回朔法,分枝定界),不同算法策略特点小结,4,“回朔法”类似于枚举法的思想,回朔法通过递归尝试遍问题各个可能解的通路，发现此路不通时回朔到上一步继续尝试别的通路。类似的还有分支定界算法。上节 下节,5,“分治法”求解的则是较复杂的问题，这类问题是可以被分解成独立的子问题来解决的，将两个或两个以上的独立子问题的解“合成”，就得到较大的子问题的解，最后合成为总问题的解。上节 下节,6,“动态规划法”动态规划法与贪心法类似，是通过多阶段决策过程来解决问题的。但每个阶段决策的结果是一个决策结果序列，这个结果序列中最后采用哪一个结果取决于以后每个阶段决策，因此称为“动态”规划法。当然每一次的决策结果序列都必须进行存储。因此，可以说“动态规划是高效率、高消费的算法”。另一方面，动态规划法与分治法类似，当问题不能分解为独立的子问题,但又符合最优化原理(最优子结构性质)时,用动态规划，通过多阶段决策过程从逐步找出子问题的最优解，从而决策出问题的结果。上节 下节,7,1.对问题进行分解的算法策略-分治法与动态规划法 2.多阶段过程贪婪算法、动态规划法 3.全面逐一尝试（带有选择性的）、比如“回溯法”、“分支定界算法”上节 下节,算法策略间的关联,8,对问题进行分解的算法策略-“分治法”与“动态规划法”“分治法”与“动态规划法”都是递归思想的应用之一，是找出大问题与小的子问题之间的关系,直到小的子问题很容易解决，再由小的子问题的解导出大问题的解。区别在于：,9,分治法所能解决的问题一般具有以下几个特征：1)该问题的规模缩小到一定的程度就可以容易地解决；2)该问题可以分解为若干个规模较小的相同问题。3)利用该问题分解出的子问题的解可以合并为该问题的解;4)该问题所分解出的各个子问题是相互独立的，即子问题 之间不包含公共的子问题。第一条特征是绝大多数问题都可以满足的;第二条特征是应用分治法的前提,它也是大多数问题可以满足的;第三条特征是关键。第四条特征涉及到分治法的效率。动态规划的实质是分治思想和解决冗余。,10,多阶段过程“贪婪算法”和“动态规划法”多阶段过程就是按一定顺序(从前向后或从后向前等)一定的策略,逐步解决问题的方法。“贪婪算法”每一步根据策略得到一个结果传递到下一步，自顶向下，一步一步地作出贪心选择。“动态规划法”则根据一定的决策,每一步决策出的不是一个结果，而只是使问题的规模不断的缩小。,11,全面逐一尝试、“枚举法”和“回溯法”考虑到有这样一类问题，问题中不易找到信息间的相互关系，也不能分解为独立的子问题,似乎只有把各种可能情况都考虑到,并把全部解都列出来之后,才能判定和得到最优解。对于规模不大的问题，这些策略简单方便;而当问题的计算复杂度高且计算量很大时,还是考虑采用“动态规划法”这个更有效的算法策略。,12,枚举法算法的实现依赖于循环,通过循环嵌套枚举问题中各种可能的情况,如八皇后问题能用八重循环嵌套枚举。而对于规模不固定的问题就无法用固定重数的循环嵌套来枚举了,有的问题可能通过变换枚举对象也能用循环嵌套枚举实现,但更多的任意指定规模的问题是靠回朔法来“枚举”或“遍历”各种可能的情况。比如图的着色问题能用“回朔法”通过递归实现。,13,4算法策略的中心思想 所有算法策略的中心思想就是用算法的基本工具循环机制和递归机制实现算法。递推法自然不用多说，贪婪算法就是逐步决策解决问题，动态规划也是。上节 下节,14,算法策略侧重的问题类型 一般我们在实际应用中遇到的问题主要分为四类:判定性问题、计算问题、最优化问题和构造性问题。递推法、递归法算法较适合解决判定性问题、计算问题。“贪婪算法”、“分治法”、“动态规划法”与“枚举法”较适合解最优化问题。构造性问题更多地依赖于人的经验和抽象能力，算法一般是人类智能充分对问题解决步骤细化后才能得到算法，少有通用的算法策略。当然也有一些问题在构造过程中使用通用的算法策略。,15,下面就最优化问题讨论如下：在现实生活中，有这样的问题：他有n个输入,而他的解就由n个输入的某个子集组成，只是这个子集必须满足某些事先给定的条件。把那些必须满足的条件称为约束条件;而把满足约定条件的子集称为该问题的可行解。显然,满足约束条件的子集可能不止一个,因此，可行解一般来说是不唯一的。为了衡量可行解的优劣，事先也给出了一定的标准,这些标准一般以函数形式给出,这些函数称为目标函数。那些使目标函数取极值的可行解，称为最优解,这一类需求取最优解的问题,又可根据描述约束条件和目标函数的 数学模型的特性或求借问题方法的不同进行而细分为 线形规则、整数规则、非线形规则、动态规划等问题。,16,尽管各类规划问题都有一些相应的求解方法，但其中的某些问题，还可用一种更直接的方法来求解，这种方法就叫贪心方法。动态规划法是将问题实例归纳为更小的、相似的子问题,并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择,但不依赖于有待于做出的选择和子问题。而分治法中的各个子问题是独立的(即不包含公共的子子问题),因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。但不足的是,如果当前选择可能要依赖子问题的解时,则难以通过局部的贪心策略达到全局最优解;如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题。,17,动态规划在解决不独立子问题时，是分为若干个阶段进行的,而且在任一阶段后的行为都仅依赖i阶段的过程状态,而与i阶段之前的过程如何达到这种状态的方法无关,这样的过程就构成一个多阶段决策过程。动态规划不仅求出了当前状态到目标状态的最优值,而且同时求出了到中间状态的最优值。显然,用枚举的方法从所有可能的决策序列中选取最优决策序列是一种最笨的方法。,18,最优性原理指出,过程的最优序列有如下性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。如果求解问题的最优性原理成立,则说明用动态规划方法有可能解决该问题。而解决问题的关键在于获得各阶段间的递推关系式。因此,从某种意义上说动态规划是一种找出子问题间递推或递归关系的方法。动态规划相比一般穷举也存在一定缺点:空间占据过多,但对于空间需求量不大的题目来说,动态规划无疑是最佳方法！,