《算法设计与分析》-动态规划I-教学课件（非AI生成）.ppt

对问题进行分解的算法策略：分治法与动态规划法多阶段过程：贪婪法、递推法、递归法和动态规划法全面逐一尝试、比较：蛮力法、枚举法、递归法算法策略的中心思想4.6.2算法策略间的关联*1.对问题进行分解的算法策略：“分治法”与“动态规划法”“分治法”与“动态规划法”都是递归思想的应用之一，是找出大问题与小的子问题之间的关系，直到小的子问题很容易解决，再由小的子问题的解导出大问题的解。区别在于：*分治法所能解决的问题一般具有以下几个特征：1)该问题的规模缩小到一定的程度就可以容易地解决；2)该问题可以分解为若干个规模较小的相同问题，即该问题具有。3)利用该问题分解出的子问题的解可以合并为该问题的解;4)该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。第一条特征是绝大多数问题都可以满足的；第二条特征是应用分治法的前提，它也是大多数问题可以满足的；第三条特征是关键。第四条特征涉及到分治法的效率。动态规划的实质是分治思想和解决冗余。*2．多阶段过程：“贪婪法”、“递推法”、“递归法”和“动态规划法”多阶段过程就是按一定顺序(从前向后或从后向前等)一定的策略，逐步解决问题的方法。“贪婪法”每一步根据策略得到一个结果传递到下一步，自顶向下，一步一步地作出贪心选择*“动态规划法”则根据一定的决策，每一步决策出的不是一个结果，而只是使问题的规模不断的缩小，如果决策比较简单，是一般的算法运算，则可找到不同规模问题间的关系，使算法演变成“递推法”、“递归法”，所以说动态规划更侧重算法设计策略，而不是算法。“递推法”、“递归法”更注重每一步之间的关系，决策的因素较少。“递推法”根据关系从前向后推，由小规模的结论，推解出问题的解。“递归法”根据关系先从后向前使大问题，转化为小问题，最后同样由小规模结论，推解出问题的解。*3．全面逐一尝试、比较：“蛮力法”、“枚举法”、“递归法”考虑到有这样一类问题，问题中不易找到信息间的相互关系，也不能分解为独立的子问题，似乎只有把各种可能情况都考虑到，并把全部解都列出来之后,才能判定和得到最优解。对于规模不大的问题，这些策略简单方便；而当问题的计算复杂度高且计算量很大时，还是考虑采用“动态规划法”这个更有效的算法策略。枚举法算法的实现依赖于循环，通过循环嵌套枚举问题中各种可能的情况。而对于规模不固定的问题，就无法用固定重数的循环嵌套来枚举了,有的问题可能通过变换枚举对象也能用循环嵌套枚举实现。*4.算法策略的中心思想所有算法策略的中心思想就是用算法的基本工具循环机制和递归机制实现算法。递推法自然不用多说，贪婪算法就是逐步决策解决问题，动态规划也是。*4.6.3算法策略侧重的问题类型一般我们在实际应用中遇到的问题主要分为四类：判定性问题、计算问题、最优化问题和构造性问题。“递推法”、“递归法”较适合解决判定性问题、计算问题。“贪婪法”、“分治法”、“动态规划法”与“枚举法”较适合解最优化问题。构造性问题更多地依赖于人的经验和抽象能力，算法一般是人类智能充分对问题解决步骤细化后才能得到算法，少有通用的算法策略。当然也有一些问题在构造过程中使用通用的算法策略。*在现实生活中，有这样的问题：他有n个输入，而他的解就由n个输入的某个子集组成，只是这个子集必须满足某些事先给定的条件。把那些必须满足的条件称为约束条件；而把满足约定条件的子集称为该问题的可行解。显然，满足约束条件的子集可能不止一个，因此，可行解一般来说是不唯一的。为了衡量可行解的优劣，事先也给出了一定的标准，这些标准一般以函数形式给出，这些函数称为目标函数。那些使目标函数取极值的可行解，称为最优解，这一类需求取最优解的问题，又可根据描述约束条件和目标函数的数学模型的特性或求借问题方法的不同，而细分为线形规则、整数规则、非线形规则、动态规划等问题。*尽管各类规划问题都有一些相应的求解方法，但其中的某些问题，还可用一种更直接的方法来求解，这种方法就叫贪婪法。动态规划法是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。而分治法中的各个子问题是独立的(即不包含公共的子子问题)，因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。*动态规划在解决不独立子问题时，是分为若干个阶段进行的，而且在任一阶段后的行为都仅依赖i阶