《可视化计算》第3章基本算法和策略(B)

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,3,章,基本算法和策略,PART B,可视化计算,基本策略,算法设计过程中，发现问题、分析问题及解决问题的思路、步骤与其他学科中的方法是一致的，就是,寻找规律,计算机科学家在算法研究过程中总结了一些具有普遍意义的算法策略和一些可循的规律，能够帮助我们较快地找到算法,2,基本策略,贪心策略,分治策略,回溯策略,动态规划,将递归算法转成非递归实现,3,贪心策略,贪心算法,在对问题求解时，总是做出在当前看来是最好的选择，因此它仅仅是某种意义上的,局部最优解,但在相当广泛范围内，对许多问题它能产生整体最优解或者是整体最优解的近似解,“鼠目寸光”,是对贪心算法的最好描述,4,贪心算法的特点,以当前情况为基础根据某个偏好原则作最优选择，而不考虑各种可能的整体情况,省去了为寻找最优解要穷尽所有可能而必须耗费的大量时间,采用自顶向下,以迭代的方法做出相关的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题,5,贪心算法的特点,通过每一步贪心选择,可得到问题的一个,局部,最优解,但由此得到的全局解却不一定都是是最优的,6,求解数字三角形,有任意一个数字三角形，只能自第一层,(,顶层,),向下行走,且只能走下接的相邻两个结点,如第三层的,1,只能走第四层的,3,或,1,问能否找到一条路径，使得路径上的权值之和最大？,7,贪心法求解的算法设计,使用,文件保存,三角形的层数和所有数据,描述一个,n,层的三角形，需要,(n*,（,n+1,）,)/2,个数据和一个描述层次的数据,;,使用二维数组,a,，保存数字三角形的所有数据,二维数组的大小为,N*N,，当然，其中有一半的元素为空值,0;,8,贪心法求解的算法设计,使用,line,，,colum,两个变量在二维数组中，作为数字定位的指针；,x,作为保存权值累计的变量；,line,的值同时用来控制路径行走的循环,9,流程图,10,分治策略,分治法（,Divide and Conquer,）,的基本思想是，将一个较大规模的问题,分解,为若干个较小规模的,子问题,，找出子问题的解，然后把各个子问题的,解合并,从而得到整个问题的解,分治法的分（,Divide,）是指将较大的问题划分为若干个较小的问题，然后用递归法求解子问题；,分治法的治（,Conquer,）是指从小问题的解来构建大问题的解,11,分治策略,分治法算法中至少包含有,两次递归过程,，只有一个递归过程的算法在严格意义上不能算作分治算法,12,求用分治法进行幂运算降序求解,在公钥加密的,RSA,算法中将高次幂运算转换为低次幂运算可以加快加密和解密的计算过程，从而提高了,RSA,算法的运算速度,算法一：采用递推循环的方式实现类似,a*b,的计算过程；,算法二：采用递归方式实现分治算法：,a*b= (a*a)*(b/2) b=,偶数,a*b= a*(a*(b-1) b=,奇数,13,分治法的计算效率,以求,5,20,为例，使用分治方法与不使用分治方法的递归算法比较，分治法可以节省近三分之二时间,14,分治方法乘幂运算,流程图,15,回溯策略,如果问题的规模（数量）是按指数速度增加的，那么这些算法的能力将受到一定的限制,在这种情况下，回溯法（,Backtracking,）也许是一个更好的选择,回溯法也叫穷尽搜索法（,Brute-Force Search,），其基本思想是尝试分步地去解决一个问题,16,现有,n,种物品，对,1=i=n,，已知第,i,种物品的重量为正整数,W,i,，价值为正整数,V,i,，背包能承受的最大载重量为正整数,W,现要求找出这,n,种物品的一个子集，使得子集中物品的总重量不超过,W,且总价值尽量大,0-1,背包问题的数学描述,17,设有物件,n,项，重量为,w(5,3,2),价值,v(9,7,8),，如果背包只能装,5,斤，求可以放背包的物品最大价值。,使用回溯算法，决策树的建树过程为：,深度有限，左侧优先,，左侧分支不取东西，,右侧取当前物件,0-1,背包问题求解,（,3,，,5,，,0,）,（,2,，,3,，,8,）,（,2,，,5,，,0,）,（,1,，,2,，,7,）,（,1,，,5,，,0,）,（,1,，,3,，,8,）,i,：红色，,表示物品的编号,aw,：绿色，当前可用空间,V,：蓝色，当前物品价值,（,1,，,0,，,15,）,（,-,，,3,，,8,）,（,-,，,5,，,0,）,（,-,，,0,，,9,）,（,-,，,2,，,7,）,（,-,，,-3,，,16,）,（,-,，,-2,，,17,）,18,k,元组的概念,元组,(tuple),是一种有穷序列，,k,个元素的序列称为,k,元组。,与集合不同,，集合不考虑元素的顺序，但元组中的元素有严格的顺序规定,在,0-1,背包问题中的决策树中的元素和重量为,w(5,3,2),价值,v(9,7,8),，皆为,三元组,k,元组的概念在下一章的,有限状态机,和,图灵机,中还会用到,19,0-1,背包回溯算法的,main,子图,建议测试案例从简单的方案开始,20,0-1,背包问题,-,回溯法求解流程图,21,0-1,背包回溯算法说明,Maxvalue,是一个递归实现的子程序，其中的主要传递参数如下：,w：,项目物体的重量数组,v：,项目物体的价值数组,length_of(w),： 重量数组的长度，也是最后一个物件下标，遍历循环的开始点，直到第一个元素,max_weight：,背包的最大容量,：,最后的返回值，即背包中物体的价值,22,动态规划,计算,Fibonacci,数列的第,n,项：当项数大于,2,时，,F,（,n,）,=F,（,n-1,）,+F,（,n-2,）,如果计算,Fibonacci,数列第,n,项，这需要计算从第,3,项到第,n-1,项,随着,n,值的增大，递归解法的算法时间复杂性会按几何级数增长,这类问题的关键是,子问题,（,sub-problem,）有重叠，因而分治法并不适合于此类问题的求解,23,动态规划,基本思想是：如果一个较大问题可以被分解为若干个子问题，并且子问题有重叠，那么，可以将每个子问题的,解存放到一个表中,，然后通过,查表,来解决问题，减少不必要的重复计算,动态规划是,20,世纪,50,年代美国数学家,Richard Bellman,提出的,在这个术语中，,Programming,与编程没有关系，而是规划和设计的意思,24,动态规划,解,Fibonacci,数列第,n,项,25,算法说明,算法,递归子程序,中的三个传递参数的作用分别是：,a,：第,n,项的输入参数,b,：第,n,项的结果输出,c,：计算过程中的中间结果存留数组（也就是一个线形表）,在计算过程中，每次计算的结果都保存在,c,数组中，出现重叠子问题时，直接到,c,数组中调取结果,26,动态规划,的分析,要消除计算过程中的,重复性过程,，动态规划是比较好的选择,这也是计算机科学中，进行问题求解的重要途径之一,由于动态规划需要保存中间计算结果，势必占用较大的内存空间（这点贪心法就完全不同），但时间复杂性则会降低,这就是所谓“,空间换时间,“的策略,27,动态规划,的分析,动态规划与贪心法不同的地方，它是一种,最优化算法,当所有的解空间可以遍历的前提下，利用动态规划的思想保存所有可能的解,再通过比较就可以得到最优的解,实现原理非常简单，但,非常实用,，也是计算机科学中最常用的算法策略,请设计使用,动态规划,求解数字三角形,28,将递归算法转成非递归的实现,递归是计算机科学中非常重要的概念，其主要优点是递归的代码量比非递归的代码量少，算法可以设计的非常简洁,这是由于递归所使用的方式是函数调用,这在计算机算法实现中属于非常自然的栈结构,不,需要,记录位置信息，,不需要,添加控制语句,这些工作都由函数调用的特性自行解决,29,递归算法的弱点,递归算法的执行效率比一般非递归的执行效率要低,因为递归的实质既然是函数调用，而函数调用必然要进行,线程栈空间,的分配，记录每一次函数调用前的状态等工作，开销是比较大的,这个情况读者可以自行应用递归实现汉诺塔案例，输入,不同的,铁饼数，运行并观察,30,非递归算法,的特点,非递归算法则不需要进行这些工作,（,线程栈空间,的分配,等）,因为非递归使用额外的变量记录当前所处的位置信息，以及额外的控制语句,递归与非递归调用最主要区别就是在函数调用上,31,递归与非递归策略思想,因此对解决某些问题时，希望用,递归算法分析问题,，但用,非递归算法解决问题,这就需要把递归算法转换为非递归算法,32,递归算法转化为非递归算法,有如下三种基本方法,：,通过分析，跳过分解过程，直接用循环结构的算法实现求解过程。,自己用栈模拟系统的运行栈，通过分析只保存必须保存的信息，从而用非递归算法替代递归算法,利用栈保存参数，由于栈的后进先出特性吻合递归算法的执行过程，因而可以用非递归算法替代递归算法,33,使用非递归方法实现汉诺塔算法,34,算法说明,将三个柱子分别命名为,na1,，,na2,，,na3,，初始状态，所有的盘子都在,na1,上，三个柱子按逆时针方向排列成一个圆环,其中存在一个规律，当对于规模为,n,的汉诺塔问题时：,1,奇数编号盘子总是移动移动到它后的第,2,个柱子上；,2,偶数编号的盘子总是移动移动到它的后第,1,个柱子上,35,基本算法策略的讨论,最优化和非最优化,：,什么不去追求最优化的解？,因为,存在一个解空间的规模问题，如果在规定时间里，可以找到所有的解，那么选出其中的最优解；,但是，如果不可能（有许多,O(2,n,）,以上时间复杂度的问题,),，那么，只好退而求其次，用次优解来解决问题,而贪心策略就是求次优解的常用思,36,基本算法策略的讨论,时间换空间（或空间换时间）,大部分递归算法编写简单，但运行的时间会随着问题规模的增长而急剧增长,而分治方法，一般要花费较多的时间将问题划分成为较小规模，增加了程序的复杂性；递归程序的非传参实现，也是如此,但较为复杂的算法，却换来几何级数的运行时间节省,37,基本算法策略的讨论,回溯策略,所解的一些问题往往是不能用数学公式去直接求解的,它需要通过一个过程，此过程要经过若干个步骤才能完成，每一个步骤又分为若干种可能；,同时，为了完成任务，还必须遵守一些规则和约束,；,对于这样一类问题，一般采用搜索的方法来解决，回溯法就是搜索算法中的一种控制策略，它能够解决许多搜索中问题,38,基本算法策略的讨论,使用递归算法的思路分析问题，但用非递归算法解决问题。,使用递归的思路分析问题，可以得到简便、可行但运行效率低下的算法,通过非递归将该算法进行再实现，可以得到极高效率的优秀算法,39,小结与回顾,基本算法包含了穷举、分段函数、递推、递归、迭代、组合、模运算、数论问题等，这种问题分类和针对性方法的比对可以避免毫无方向的试错和摸索过程,而基本策略则是计算机科学中解决战略性问题的重要手段，本章专门选择了若干相对简单的案例来分别说明贪心、分治、回溯和动态规划的基本思想,而使用递归的方法分析问题，使用非递归的方法实现算法，具有更为深邃的战略意义,40,