课外资料计算机常用算法.ppt

计算机常用算法,7、动态规划,1、穷举法（枚举法）,2、递归法,3、回溯法,4、模拟法,6、分治法,5、贪心法,枚举法穷举法,枚举法（通常也称为穷举法）是指在一个有穷的可能的解的集合中，枚举出集合中的每一个元素，用题目给定的约束条件去判断其是否符合条件，若满足条件，则该元素即为整个问题的解；否则就不是问题的解。枚举的思想往往是最容易想到的一种解题策略，枚举法从本质上说是一种搜索的算法，但适用枚举法解题必须满足下列条件：,1）可预先确定解元素的个数n,且问题的规模不是特别大；,2）对于每个解变量A1，A2，。An的可能值必须为一个连续的值域。,枚举法的算法流程：设ai1为解变量Ai的最小值；aik为解变量的最大值；其中1in.A1a11,a12,a1KA2a21,A22,A2KAiai1,Ai2,AiKAnan1,An2,AnK我们称解变量为枚举变量。例如某问题的枚举变量有三个：A1，A2，A3。,A11，2，A22，3，4，A35，6，7则问题的可能解为（A1，A2，A3）（1，2，5），（1，2，6），（1，2，7），（1，3，5），（1，3，6），（1，3，7），（1，4，5），（1，4，6），（1，4，7），（2，2，5），（2，2，6），（2，2，7），（2，3，5），（2，3，6），（2，3，7），（2，4，5），（2，4，6），（2，4，7）在上述18个可能解的集合中，满足问题给定的检验条件的解元素即为问题的解。,枚举法的优化方法：1）减少枚举的变量，在使用枚举法之前，先考虑一下解元素之间的关联，将一些非枚举不可的解元素列为枚举变量，其他元素通过计算得出解元素的可能值。,例1、巧妙填数。将19这9个数字填入到9个空格中。每一横行的三个数字组成一个三位数。如果要使第二行的三个三位数是第一行的2倍，第三行的三位数是第一行的三倍，应怎样填数。如图,2）减少枚举变量的值域,3）分解约束条件，将拆分的约束条件嵌套在相应的循环体间。,本题目有9个格子，要求填数，如果不考虑问题给出的条件，共有9！=362880种方案，在这些方案中符合条件的即为解。因此可以用枚举法。,但仔细分析问题，显然第一行的数不会超过400，实际上只要确定第一行的数就可以根据条件算出其他两行的数了。这样仅需枚举400次。,递归法,一个函数、过程、概念或数学结构，如果在其定义或说明内部直接或间接地出现有其本身的引用，或者是为了描述问题的某一状态，必须用到它的上一状态，而描述上一状态，又必须用到它的上一状态这种用自己来定义自己的方法，称之为递归或者是递归定义。在程序设计中，过程或函数直接或者间接调用自己，就被称为递归调用。子程序直接调用自己，称为直接递归；嵌套关系的子程序a和b,内层的b调用外层的a,是间接递归；平级关系的子程序a和b,其中a调用了b,b又调用了a,这也是间接递归。,数学函数式递归,例1、阶乘n!=1*2*3*（n-1）*n,算法分析：要求n!,只需求出(n-1)!,因为n!=n*(n-1)!,要求出(n-1)!,只需求出(n-2)!,因为(n-1)!=(n-1)*(n-2)!,所以可得到阶乘的递归定义式：,例2、斐波那契数列0，1，1，2，3，5，8，13，21，34，55，,从第三项开始，每一项是前两项的和，其递归定义式为：,求此数列第n项。,例3、楼梯共有n层台阶，上楼可以一步走一层，也可以一步走两层。编程序计算上n层台阶共有多少种走法？,回溯法,回溯是重要的算法之一，有一些问题，要求找到一组解，或要求找到一个满足某些限制的最优解。对于解决这样的问题，可以通过使用彻底的搜索方法来解决。然而，彻底搜索的运算量很大，有时大到计算机承受不了的程度。彻底的搜索，要进行大量的比较，大量的舍弃，以大量的运算，大量的时间为代价。因此，用穷举法解某些实际问题是不现实的，回溯算法为我们提供了一个好方法，使用回溯法可以大大减少实际的搜索。例如，迷宫问题，八皇后问题，骑士周游世界问题。,算法思想：通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索往前试探，若试探成功，就得到解，若试探失败，就逐步往回退，换别的路线再往前试探。实际上是广度与深度搜索结合的搜索，深度搜索过程中碰到条件不满足，则退回上一层，在每一层上也进行全面的搜索。,关键：找到回溯的条件。,求解八皇后问题：在n*n个方块排成n行n列的棋盘上，如果两个皇后位于同一行、同一列或同一对角线上，则称它们互相攻击。现在要求找出使棋盘上n个皇后互不攻击布局。,列号：（8，2，4，1，7，5，3，6）,分析：为了找出互不攻击的布局，需要对n*n个方案进行检查，将有攻击的布局剔除掉。这是一种穷举法。但这种方法对于较大的n，其工作量会急剧的增大，而逐一列举是没有必要的。,算法：由于在第一行上的皇后在第一列，则第二行上的皇后就不可能在第一列。首先将每一行上安置一个皇后，并假设第i个皇后在第i行上，用一个一维数组queen1.n用于记录安放皇后的过程中随时记录第i行上的皇后所在的列号。由此可知，在这种情况下，实际上已经剔除了两个皇后在同一行的可能性。因此，在安置每一行上的皇后时，只需考虑每两个皇后不能在同一列或同一对角线上的可能性。,从第一行（即i=1）开始布局。设前i-1行上的皇后已布局好，即它们互不攻击。现考虑安排第i行上皇后位置，使之与前i-1行上的皇后也互不攻击。为了实现这一点，可以从第i行皇后的当前位置开始向右搜索。,引进集合a,b,c分别表示各列、各条右对角线和各条左对角线上是否放置了皇后。在同一右对角线上，i-j是常量。在同一左对角线上，i+j是常量。第i行第j列上放皇后在第i-j条右对角线和第i+j条左对角线上。能放皇后时为真，不能放皇后时为假。数组queen存放各行皇后所在的列号。,随机数的介绍在自然界和日常生活中,许多现象具有不确定的性质,有些问题甚至很难建立数学模型,或者很难用计算机建立递推,递归,枚举,回溯法等算法.在这种情况下,一般采用模拟策略.在对实际问题中的随机现象进行数学模拟时,利用计算机产生的随机数是必不可少的,由于用计算机产生的随机数总是受字长的限制,其随机的意义要比实际问题中真实的随机变量稍差,因此,通常将计算机产生的随机数称为伪随机数.,TURBO.PASCAL的系统中有两个产生伪随机数的单元:Randomize过程伪随机数发生器初始化,Random(range)函数产生一个范围在0x=2*k+1），甲每次取a颗,（N,k,a均为随机数），乙怎样取赢的可能性最大？设甲为计算机产生的随机数，乙为由你编的计算机程序。,贪心法是从问题的某一个初始解出发,向给定的目标推进.但不同的是,推进的每一步不是依据某一固定的递推式,而是做一个当时看似最佳的贪心选择,不断地将问题实例归纳为更小的相似的子问题,并期望通过所做的局部最优选择产生出一个全局最优解.背包问题：在杂货店比赛中你获得了第一名，奖品是一车免费杂货。店中有n种不同的货物。规则规定从每种货物中最多只能拿一件，车子的容量为c，物品i需占用wi的空间，价值为pi。你的目标是使车中装载的物品价值最大。当然，所装货物不能超过车的容量，且同一种物品不得拿走多件。如何选择量度标准才能找到最优解？,找零钱问题：一个小孩买了价值为33美分的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为25美分、10美分、5美分、及1美分的硬币。(求解所用方法即为贪心算法）,分治策略指的是分而治之的方法。当我们处理大规模问题时，求解可能比较困难，对于这类问题，我们可以将原问题分解成规模较小而结构与原问题相似的子问题，然后递归地解决这些子问题，最后由这些小问题的解构造出原问题的解。因此一个问题能否用分治法解决，关键是看该问题算法能否将原问题分成n个规模较小而结构与原问题相似的子问题。递归地解决这些子问题，然后合并其结果就得到原问题的解。当n=2时的分治法又称二分法。,分治策略一般分为三个步骤：1、分解：将要解决的问题划分成若干个规模较小的同类问题。2、求解：当子问题划分得足够小时，用较简单的方法解决。3、合并：按原问题的要求，将子问题的解逐层合并成原问题的解。,使用分治策略的问题常常要借助递归的结构，逐层求解，当问题规模达到某个简单情况时，解容易直接得出，而不必继续分解。其过程大致如下：,分治策略,If问题不可分thenbegin直接求解；返回问题的解；elsebegin从原问题中划分出含1/n运算对象的子问题1；递归调用分治法过程，求出解1；从原问题中划分出含1/n运算对象的子问题2；递归调用分治法过程，求出解2；从原问题中划分出含1/n运算对象的子问题n；递归调用分治法过程，求出解n；将解1、解2、解n组合成整个问题的解；end;,例1、求一组数中的最大值和最小值。,算法分析：假设数据个数为n，存放在数组A1.n中。可以直接进行比较。min:=a1;max:=a1;fori:=2tondoifaimaxthenmax:=aielseifai2)个数据先分成两组，分别求最大值、最小值，然后分别将这两组的最大值和最小值进行比较，求出全部元素的最大值和最小值。若分组后元素个数还大于2，则再次分组，直至组内元素小于等于2。,使用这一算法，比较次数为2（n-1）。若n=10，则比较18次。,动态规划是对最优化问题的一种新的算法设计方法。在实际生活中，有这样的一类问题，它们的活动过程可以分为若干个阶段，而且在任意一个阶段x，过程在阶段x以后的行为，仅依赖于x阶段的过程状态，而与x之前过程如何达到这种状态的方式无关，这样的过程就构成一个多阶段决策过程。由此提出了解决这类问题的“最优化原理”，创建了最优化问题的一种新的算法设计方法-动态规划。,动态规划解题方法是一种高效率的解题方法，可以解决相当大的信息量，其时间复杂度通常为O(n2)、O(n3)等。它适用的原则是优化原则，它可以将整体优化分解为若干个局部优化。,动态规划算法,动态规划算法的一般模式：1）划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意有序或可排序。2）确定状态和状态变量：将问题发展到各个阶段时所处的各种情况用不同状态表示出来。3）确定决策并写出状态转移方程：一般是根据相邻两个阶段各状态之间的关系来确定决策。4）寻找终止条件：给出的状态转移方程是一个递推式，必须有一个递推的终止条件。5）编写程序。,例如：求从A点到D点的最短路径。,通过三段路程的最短路径可以用各自的最短路径，求他们的和。其和为AB，BC，CD的最短路径之和，将其作为整个问题的最短路径，且其解法为最优解。,算法分析：穷举法：时间复杂度：n1*n2*n3,贪心法：时间复杂度：n1+n2+n3,可行。,动态规划算法的应用,例1、设有一个三角形的数塔，顶点为根结点，每个结点有一个整数值。从顶点出发，可以向左走或向右走，如图：,从根结点13出发向左、向右的路径长度可以是：13-11-7-14-7，其和为5213-11-12-14-13，其和为63若要求从根结点开始，找出一条路径，使路径之和最大，若存在多条请输出任意一条。,解析：1）用穷举法：从根结点开始，将所有可能的路径求和，找出最大值，但算法时间复杂度使问题成为不可能。当N=1，P=1N=2，P=2N=3，P=4N=k,P=2k-1。当N=50，P=249=500万亿条路径。2）用贪心法：本题若用贪心法则：13-11-12-14-13，其和为63，实际上存在另一条路径：13-8-26-15-24，其和为86；贪心法问题所在：眼光短浅。,3）动态规划求解：动态规划求解问题的过程归纳为：自顶向下分析，自底向上计算。基本方法：划分阶段：按三角形的行，划分阶段，若有n行，则有n-1个阶段，找到问题求解的最优途径。A、从根结点13出发，选取它的两个方向中的一条支路，选择的依据是比较两个支路中其路径和最大的支路；B、设x为从11出发到底端的最大路径值，y为从8到底端的最大路径值。C、ifxythen选择x且取得最大和为13+xelse选择y且取得最大和为13+y这样，原先求根结点到底端的最大路径问题，变为从11出发和和从8出发求路径和的子问题。,同理，求从11出发到底端的最大路径问题可以转化为从12出发和从7出发的最大路径问题。决策：路径和最大状态转移方程：Fi=max(Fi-1(左),Fi-1(右),A、当到倒数第二层时，每个结点其后继仅有两个结点，可以直接比较，选择最大值为前进方向，从而求得从根结点开始到底端的最大路径。终止条件B、自底向上计算从底层开始，本身数即为最大数；倒数第二层的计算，取决于底层的数据：12+6=18，13+14=27，24+15=39，24+8=32最后的路径为：13-8-26-8-24,4）数据结构及算法设计：A、图形转化：直角三角形，便于搜索，向下或向右B、用三维数组表示数塔：ax,y,1表示行、列及结点本身数据ax,y,2表示能够取得最大值ax,y,3表示前进方向，0向下，1向右。C、算法：数组初始化，输入每个结点值以及初始的最大路径、前进方向0；从倒数第二层开始向上一层求最大路径，共循环n-1次；从顶向下，输出路径：关键是j的值，由于行逐渐递增，表示向下，究竟是向下还是向右取决于列的值。若j的值比原先多1则向右，否则向下。,例3、一个n行m列迷宫（1n,m50）,入口位于左上角，规定只能往下或往右走。迷宫中存在一些障碍物无法通过。迷宫的某些地方里藏有不同价值的宝藏。求所能收集的宝藏的最大价值。,子结构划分：逐行扫描。考虑迷宫某一点，要求走到这一点所能收集的宝藏的最大价值，先求出走到它在边和上边所能收集的宝藏的最大价值。,算法分析：,变量的定义：Ai,j=迷宫第i行第j列的宝藏价值，-1表示障碍物；Fi,