数据结构-第五部分.ppt

1,第15章 算法设计技术,枚举法贪婪法分而治之法动态规划回溯法随机算法,介绍通用的算法设计模式,2,枚举法,枚举法适合于解的候选者是有限、可枚举的场合。枚举法就是对可能是解的众多候选者按某种顺序进行逐一枚举和检验，从中找出符合要求的候选解作为问题的解。基于枚举法的算法一般都比较直观，容易理解。但由于要检查所有的候选解，因此时间性能较差,3,枚举法实例,用50元钱买了三种水果：西瓜、苹果和桔子。各种水果加起来一共100个。假如，西瓜5元一个，苹果1元一个，桔子1元3个，设计一算法输出每种水果各买了几个。,4,约束条件,三种水果一共100个；买三种水果一共花了50元。如果西瓜有mellon个，苹果有apple个，桔子有orange个，那么：mellon+apple+orange 等于100 5*mellon+1*apple+orange/3等于50。,5,直观的枚举,For(mellon=1,mellon 99;+mellon)For(apple=1,apple 99;+apple)For(orange=1;orange 99;orange)If（mellon+apple+orange 等于100 并且 5*mellon+1*apple+orange/3等于50）输出此方案；,列出所有的情况，检查是否满足两个约束条件,6,改进的方案,int main()int mellon,apple,orange;for(mellon=1;mellon10;+mellon)for(apple=1;apple 50-5*mellon;+apple)orange=3*(50-5*mellon-apple);if(mellon+apple+orange=100)cout mellon:mellon;cout apple:apple;cout orange:orange endl;return 0;,按一个约束条件列出所有可行的情况，然后对每个可能解检查它是否满足第二个约束条件。,7,执行结果,Mellon：1 apple：18 orange：81Mellon：2 apple：11 orange：87Mellon：3 apple：4 orange：93,8,第15章 算法设计技术,枚举法贪婪法分而治之法动态规划回溯法随机算法,介绍通用的算法设计模式,9,贪婪法,贪婪法适合于分阶段完成的工作。在每一阶段都选择当前最好的答案，而不管将来如何。Dijkstra算法，prim算法和Kruskal算法都是贪婪算法贪婪法不一定能得到最优解，但是一个可行的、较好的解。,10,最少背包问题,假设有许多盒子，每个盒子能保存的总重量为1.0。有N个项i1,i2,iN，它们的重量分别是w1,w2,wN。目的是用尽可能少的盒子放入所有的项，任何盒子的重量不能超过他的容量。例如，如果项的重量为0.4,0.4,0.6和0.6，最佳的方案是用两个盒子。但要得到最佳方案，必须尝试所有种组合情况。当n很大时，这是不可能的。一种解决方案使用贪婪法,11,解决策略,按给定的次序扫描每一个项，把每一个项放入能够容纳他而不至于溢出的最满的盒子。如果项的重量为0.4,0.4,0.6和0.6，贪婪法的方案是用三个盒子。其装载的重量分别为0.8,0.6,0.6,12,第15章 算法设计技术,枚举法贪婪法分而治之法动态规划回溯法随机算法,介绍通用的算法设计模式,13,分而治之法,分而治之法的思想分：递归解决若干个较小的问题治：从子问题的答案中形成原始问题的解分治法的的算法至少有两个递归调用已见过的分治法算法：快速排序，树的遍历,14,分治法实例,最长连续子序列问题最近点问题数学计算问题,15,最长连续子序列问题,假设输入是4，3，5，2，1，2，6，2。我们把这个输入划分成两部分，前四个和后四个。这样最大连续子序列的和可能出现在下面三种情况中。情况1：整个位于前半部，可递归计算。情况2：整个位于后半部，可递归计算。情况3：从前半部开始但在后半部结束。,16,情况3的解决方法,从两半部分的边界开始，通过从右到左的扫描来找到左半段的最长序列。类似地，从左到右的扫描找到右半段的最长序列。把这两个子序列组合起来，形成跨越分割边界的最大连续子序列。在这个实例中，结果序列是从第一部分的第一个元素到第二部分的其余元素。总和是两个子序列的和，即4+7=11.,17,算法总结,递归地计算整个位于前半部的最大连续子序列。递归地计算整个位于后半部的最大连续子序列。通过两个连续循环，计算从前半部开始但在后半部结束的最大连续子序列的和。选择三个和中的最大值。,18,Int maxSum(int a,int left,int right)int maxLeft,maxRight,center;int leftSum=0,rightSum=0;int maxLeftTmp=NEGMAX,maxRightTmp=NEGMAX;center=(left+right)/2;if(left=right)return aleft 0?aleft:0;maxLeft=maxSum(a,left,center);maxRight=maxSum(a,center+1,right);,19,for(int i=center;i=left;-i)leftSum+=ai;if(leftSum maxLeftTmp)maxLeftTmp=leftSum;for(int i=center+1;i maxRightTmp)maxRightTmp=rightSum;return max3(maxLeft,maxRight,maxLeftTmp+maxRightTmp);,20,分治法实例,最长连续子序列问题最近点问题数学计算问题,21,最近点问题,在二维平面上有N个点，试找出距离最短的两个点。蛮力算法：计算两两之间的距离，从中找出最小的一个。N个点有N（N-1）/2对距离，因此时间复杂度为O(N2),22,分治法解法,将所有的点按x值排序。取一个合适的x值，把所有点分成两半PL和PR。距离最近的两个点可能出现在PL中(dL)，也可能出现在PR(dR)中，也可能一个点在PL，一个点在PR(dC)dL和dR可用递归得到dC的计算：设=min(dL,dR)如果dC比大，则没必要计算。因此用于计算dC的点必须落在分界线 的范围内，计算此范围中点对的距离中的最小值,23,24,优化,在最坏的情况下，所有的点都落在分界线以内。但此时不一定要计算所有点对的距离。只要两点的y坐标大于，这两点之间的距离也不用算了。假设该区间中的点按y坐标排序，则可得下列算法,25,for(i=0;i=)break;else if(dist(pj,pj+1)=dist(pj,pj+1);,26,分治法实例,最长连续子序列问题最近点问题数学计算问题,27,数学计算问题,设X和Y是两个N位的整数，假如一位乘法花费一个单位时间，那么计算 X*Y 的时间复杂性为O(N2)分治法计算将X和Y均分成两半，分别称为XL，XR，YL，YR。则 X=XL10N/2+XR，Y=YL10N/2+YR。那么，XY=XLYL10N+(XLYR+XRYL)10N/2+XRYR时间复杂度：T(N)=4T(N/2)+O(N)=O(N2),28,进一步改进,上述算法的问题是需要太多次（4次）的递归调用。如果能减少递归调用，则能提高时间性能注意：XLYR+XRYL=(XL XR)(YR YL)+XLYL+XRYR 代入前式，XY=XLYL10N+(XLYR+XRYL)10N/2+XRYR=XLYL10N+(XL XR)(YR YL)+XLYL+XRYR)10N/2+XRYR 可见只需3次递归调用时间复杂性：,29,第15章 算法设计技术,枚举法贪婪法分而治之法动态规划回溯法随机算法,介绍通用的算法设计模式,30,动态规划,用表代替递归例：斐波那契函数f(n)=f(n-1)+f(n-2)。计算f(n)需要计算f(n-1)和f(n-2)。当计算f(n-1)时要计算f(n-2)和f(n-3)。因此在计算f(n)中f(n-2)被计算了两次。为了减少重复的递归调用，我们可以反过来计算。先计算f(2)，有了f(2)再计算f(3)，以此类推，计算到f(n)。在此过程中不需要任何递归,31,动态规划,硬币找零问题最优二叉查找树,32,找零问题,对于一种货币，有面值为C1,C2,CN(分)的硬币，最少需要多少个硬币来找出K分钱的零钱。,33,贪婪法解法,我们不断使用可能的最大面值的硬币 如：美元的硬币有1、5、10和25分的面值(忽略流通频率很低的50分硬币)。我们可以通过使用2个25分、一个10分的硬币以及三个1分来找出63分钱，一共是6个硬币。如果美元中包含一个21分硬币时，贪心算法仍然给出一个用六个硬币的解，但是最佳的解是用三个硬币(三个都是21分的硬币。),34,解法1分治法,如果我们可以用一个硬币找零，这就是最小的。否则，对于每个可能的值i，我们可以独立计算找i分钱零钱和K-i分钱需要的最小硬币数。然后选择这个和最小的i。,35,怎样找出63分钱零钱,找出1分钱零钱和62分钱零钱分别需要的硬币数是1和4。因此，63分钱需要使用五个硬币。找出2分钱和61分钱分别需要2和4个硬币，一共是六个硬币。我们继续尝试所有的可能性。我们看到一个21分和42分的分解，它可以分别用一个和两个硬币来找开，因此，这个找零问题就可以用三个硬币解决。我们需要尝试的最后一种分解是31分和32分。我们可以用两个硬币找出31分零钱，用三个硬币找出32分零钱，一共是五个硬币。因此最小值是三个硬币。,36,int coin(int k)int i,tmp,int coinNum=k;if（能用一个硬币找零）return 1;for(i=1;ik;+i)if(tmp=coin(i)+coin(k-i)coinNum)coinNum=tmp;return coinNum;,37,上述解法分析,此算法的效率很低事实上63分钱找零的问题是不会在一个合理的时间内解决的。就如Finbonacci 函数一样,38,解法2,通过指定其中的一个硬币来递归地简化问题。例如，对于63分钱，我们可以给出以下找零的办法。一个1分的硬币加上递归地分派62分钱一个5分的硬币加上递归地分派58分钱一个10分的硬币加上递归地分派53分钱一个21分的硬币加上递归地分派42分钱一个25分的硬币加上递归地分派38分钱该算法的问题仍然是效率问题,39,动态规划解,效率低下主要是由于重复计算造成的。因此，可把已有子问题的答案存放起来，当再次遇到此子问题时就不用重复计算了。在本例中，我们用coinsUsedi代表了找i分零钱所需的最小硬币数。,40,算法思想,先找出一分钱的找零方法，把最小硬币数存入coinUsed1 依次找出2分钱、3分钱的找零方法，知道到达要找零的钱为止：对每个要找的零钱i，可以把i分解成某个coinsj和 i-coinsj，所需硬币数为coinUsedi-coinsj+1。对所有的j，取最小的coinUsedi-coinsj+1作为i元钱找零的的答案。,41,函数原型,Void makechange(int coins,int differentCoins,int maxChange,int coinUsed)Coins存放所有不同的硬币值，不同的硬币个数为differentCoins。maxChange为要找的零钱数,42,void makechange(int coins,int differentCoins,int maxChange,int coinUsed)coinUsed0=0;for(int cents=1;cents cents)continue;if(coinUsed cents-coinsj+1 minCoins)minCoins=coinUsed cents-coinsj+1;coinUsedcents=minCoins;,43,动态规划,硬币找零问题最优二叉查找树,44,最优二叉查找树,有一组词 w1,w2,wN，他们的出现概率分别为p1,p2,pN。构建一棵二叉排序树使得访问时间的期望值最小。即如果wi所在的层次是di，那么该问题类似于哈夫曼树，概率大的靠近根，概率小的远离根。但它比哈夫曼树更复杂。因为它还要满足二叉排序树的特性,45,贪婪法的解法,选择出现概率最大的词作为树根，把剩余的词分成两组：小于根的和大于根的。递归构建左子树和右子树。,显然不是最优的，代价为：2.43,46,最优解法,假如要对wleft到wright构建一棵最优二叉排序树，那么这棵树的形式一定是根为wi，左子树的节点为left到i-1，右子树的节点为i+1到right，左子树和右子树也是最优的设Cleft，right是树的代价，那么,47,最优解法,对 a,am.and,egg,if,the,two对所有的可能的情况计算它的代价，从中找出最小的：根为a，左子树为空，右子树为am，two。根为am，左子树为a，右子树为and,，two。根为and，左子树为a，am,右子树为egg,，two。根为egg，左子树为a,am,and,右子树为if,，two。在上述每一种情况中，我们需要继续递归。如：在尝试根为egg，左子树为a,am,and,右子树为if,，two的情况时，要找出最优的左子树，我们又要尝试根节点为a，左子树为空，右子树为am和and根节点为am，左子树为a，右子树为and根节点为and，左子树为a和am，右子树为空。,48,动态规划解法,从上述分析可以看出，在找出由a到two组成的最优树时，由a组成的树，由a和am组成的树，由am和and组成的树，会分别被计算很多次。解决方法：从小到大计算由n个节点组成的最优树，并把它保存在一个表中。当所有的节点形成了一棵树时，任务就完成了。每棵树的保存用两个信息：根和代价。,49,生成过程,先生成由一个节点组成的树。树的代价就是节点的权值。保存这些树和相应的代价。生成所有由两个节点组成的树：将第一个节点作为根，第二个节点作为右子树。计算代价。将第二个节点作为根，第一个节点作为右子树。计算代价。取代价小的树作为最终的树保存下来。生成由三个节点组成的树，四个节点组成的树,50,i=1i=2i=3i=4i=5i=6i=7,51,第15章 算法设计技术,枚举法贪婪法分而治之法动态规划回溯法随机算法,介绍通用的算法设计模式,52,第15章 算法设计技术,枚举法贪婪法分而治之法动态规划回溯法随机算法,介绍通用的算法设计模式,53,回溯法,八皇后问题分书问题,首先暂时放弃问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现候选解不可能是解时，就选择下一候选解。如果当前候选解除了不满足规模要求外，满足其他所有要求时，继续扩大当前候选解的规模，并继续试探。如果当前的候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。,54,八皇后问题,在一个8*8的棋盘上放8个皇后，使8个皇后中没有两个以上的皇后会在同一行、同一列或同一对角线上,55,八皇后问题的求解过程,求解过程从空配置开始，在第一列到第m列为合理配置的基础上再配置m+1列，直到第n列的配置也时合理时，就找到了一个解。另外在一列上也有n种配置。开始时配置在第一行，以后改变时，顺序选择第二行、第三行、。、第n行。当配置到第n行时还找不到一个合理的配置时，就要回朔，去改变前一列的配置。,56,算法,m=0;/*从空配置开始*/good=true;/*配置中的皇后不冲突*/do if(good)if(m=8)输出解；重新寻找下一可行的解；else 向前试探，扩展至下一列；else 回朔，形成下一候选解；good=检查当前候选解的合理性；while(m!=0);,57,棋盘的数据结构的设计,比较直观的方法是采用一个二维数组，但仔细考察，就会发现，这种表示方法给调整候选解及检查其合理性会带来困难。对于本题来说，我们关心的并不是皇后的具体位置，而是“一个皇后是否已经在某行和某条斜线合理地安置好了”。因为在每一列上恰好放一个皇后，所以引入一个一维数组(设为col（9）)，值colj表示在棋盘第j列上的皇后位置。如col3的值为4，就表示第三列的皇后在第四行。另外，为了使程序在找完了全部解后回溯到最初位置，设定col0的初值为0。当回溯到第0列时，说明程序已求得全部解(或无解)，结束程序执行。,58,候选解的合理性检查,引入以下三个工作数组 数组a9，aA=true表示第A行上还没有皇后；数组b16，bA=true表示第A条右高左低斜线上没有皇后；从左上角依次编到右下角(1-15)。数组c16，cA=true表示第A条左高右低斜线上没有皇后。从左下角依次编到右上角(1-15)。,59,void queen_a11(int k)/在8x8棋盘的第k列上找合理的配置int i,j;char awn;for(i=1;i awn;if(awn=Q|awn=q)exit(0);else queen_a11(k+1);/递归至第k十1列 ai=bk+i-1=c8+k-i=true;/恢复对应位置无皇后,60,主程序,int col9;bool a9,b17,c17;int main()int j;for(j=0;j=8;j+)aj=true;for(j=0;j=16;j+)bj=cj=true;queen_a11(1);return 0;,61,回溯法,八皇后问题分书问题,首先暂时放弃问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现候选解不可能是解时，就选择下一候选解。如果当前候选解除了不满足规模要求外，满足其他所有要求时，继续扩大当前候选解的规模，并继续试探。如果当前的候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。,62,分书问题,有编号为0，1，2，3，4的5本书，准备分给5个人A，B，C，D，E，每个人的阅读兴趣用一个二维数组描述：Likeij=true i喜欢书j Likeij=false i不喜欢书j 写一个程序，输出所有皆大欢喜的分书方案,63,存储设计,用一个二维数组like存储用户的兴趣用一个一维的整型数组take表示某本书分给了某人。Takej=i表示第j本书给了第i个人。,64,解题思路,依次尝试把书j分给人i。如果第i个人不喜欢第j本书，则尝试下一本书，如果喜欢，并且第j本书尚未分配，则把书j分配给i。如果i是最后一个人，则方案数加1，输出该方案。否则调用try（i+1)为第i+1个人分书。回溯。让第i个人退回书j，尝试下一个j，即寻找下一个可行的方案由于在每次try中都要用到like，take以及目前找到的方案数n，因此可将它们作为全局变量，以免每次函数调用时都要带一大串参数。,设计一个函数try(i)给第i个人分书。,65,void trynext(int i)int j,k;for(j=0;j5;+j)if(likeij,66,当like矩阵的值为,调用trynext(0);的结果为：,67,第14章 算法设计技术,枚举法贪婪法分而治之法动态规划回溯法随机算法,介绍通用的算法设计模式,68,随机算法,在算法中，至少有一个地方使用随机数作决策。随机算法的时间复杂度取决于选择的随机数随机算法的时间复杂度用期望的运行时间来表示。一般假设随机数的选择是均匀分布的例如，在快速排序中将中间点用随机数来选择，则快速排序成为一个随机算法。可以证明，期望的时间复杂度为O(NlogN),69,随机算法实例,跳表素数检测,70,跳表,以O(logN)的期望的时间复杂性支持插入和删除的数据结构跳表的概念：支持动态查找必须用链表，但链表查找的时间为N。可以用增加链的方式提高查找效率增加一条链，让头节点指向第二个节点，第二个节点指向第四个节点，第四个节点指向第六个节点，。查找时间为再增加一条链，让头节点指向第四个节点，第四个节点指向第八个节点，第八个节点指向第十二个节点，。查找时间为推而广之，对于2iN2i+1个节点，设置i条链，第j条链指向其后的第2j个节点,71,72,查找过程（节点x）,首先查找第i条链，如下一节点比x大，则查找第i-1条链，否则继续查找第i条链。依次执行，直到找到或找不到x最坏情况下的时间性能：,73,插入过程,当插入一节点时，所有的节点都要变化。为了避免这个变化，插入采用随机算法定义：有k条链的节点称为level-k节点在跳表中，level-i的节点有N/2i个，即level-i的节点出现的概率为1/2i。插入过程：查找到插入点生成一个新节点按概率生成节点的level插入该节点因此跳表并不一定是严格的隔2i个节点有一条第i层的链，而只是从概率上讲符合此分布,74,随机算法实例,跳表素数检测,75,素数检测,方法一：依次检测1到N能否被N整除，如果能被整除的数的个数等于2，则N是素数。时间复杂度为O（N）方法二：依次检测2、3、5、7到sqrt(N)，只要有一个能整除N，则N为非素数。最坏情况的时间复杂度O(N1/2)上述两方法对小素数适合，大素数不适合方法三：随机算法。该算法能保证：当声称是非素数时，100%为非素数；当声称是素数时，有一个可以忽略不计的很小的误差。,76,理论基础,定理一：如果p是素数，并且0 a p，那么 ap-1 1(mod p)定理二：如果p是素数，并且0 xp，那么方程x21(mod p)的唯一可能的根是x=1 和 x=p-1算法思想：计算ap-1(mod p)，如果结果违反定理一，则p不是素数；在计算过程中，如果发现x21(mod p)的根不是1或p-1，则p不是素数,77,正确性,定理一是一个充分条件，但并不是必要条件。它只能说明对任意选择的满足条件的a，当ap-1 1(mod p)，p不是素数。但当ap-1 1(mod p)并不保证p是素数。一般有25%的出错率解决方法：多找一些a来测试。如随机地找50个a，那么出错率为(25%)50=2-100,78,算法设计,测试素数最基本的工作是计算ap-1(mod p)，为此设计了函数witness。当n为偶数时，an=an/2*an/2；n为奇数时，an=a*a(n-1)/2*a(n-1)/2；因此，witness可采用递归函数实现，递归终止条件：a0=1计算ai(mod p)的函数原型：HugeInt witness(const HugeInt&a,const HugeInt&i,const HugeInt&p)；,79,素数测试程序,const int TRIALS=5;bool isPrime(long int p)srand(time(0);for(int counter=0;counter TRIALS;counter+)if(witness(rand()*(p-2)/RAND_MAX+2,p-1,p)!=1)return false;return true;,80,Witness函数的设计,在计算an的过程中，对中间结果作模p的运算，减小计算量。对每个模p的结果应用定理二，淘汰合数。,81,Witness函数,long int witness(long int a,long int i,long int p)if(i=0)return 1;long int x=witness(a,i/2,p);if(x=0)return 0;long int y=(x*x)%p;if(y=1,82,总结,本章简单介绍了算法设计中的几种常用的方法及适用的范围，对每个算法我们都给出了一些实例说明他们的用法。选择适当的算法，并结合合适的数据结构，往往可以迅速而高效地解决问题,