第7章 数据结构与算法精选PPT.ppt

《第7章 数据结构与算法精选PPT.ppt》由会员分享，可在线阅读，更多相关《第7章 数据结构与算法精选PPT.ppt（92页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第7章 数据结构与算法第1页，本讲稿共92页概率算法概率算法概率算法同前几章算法的区别概率算法允许算法在执行过程中随机地选择下一个允许算法在执行过程中随机地选择下一个计算步骤计算步骤。在许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择省时省时。概率算法的一个基本特征：对所求解问题的同对所求解问题的同一实例用同一概率算法求解两次，可能得到完一实例用同一概率算法求解两次，可能得到完全不同的效果。全不同的效果。反映在求解时间、结果质量等方面。第2页，本讲稿共92页概率算法的主要类型概率算法的主要类型概率算法的主要类型数值概率算法蒙特卡罗算法拉斯维加斯算法舍伍德算法第3页，本讲稿共

2、92页数值概率算法数值概率算法数值概率算法将一个问题的计算与某个概率分布已经确定的事件（或按需要构造满足某种概率分布的事件）联系起来。常用于数值问题的求解，得到的往往是近似解得到的往往是近似解解的精度随计算时间的增加而提高在许多情况下，计算出问题的精确解是不可能或没必要第4页，本讲稿共92页舍伍德算法舍伍德算法舍伍德算法总能求解得到问题的一个解，而且所求得得解总是正确的。总能求解得到问题的一个解，而且所求得得解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可在这个确定算法中引入随机性，将它改造成一个舍伍德算法，消除或减少问题的好坏实例间的差别。如

3、快速排序法：O(n2)(出现概率小);O(nlogn);舍伍德算法的精髓舍伍德算法的精髓不是避免算法的最坏情况，而是设法消除这种最坏情形行为与特定设法消除这种最坏情形行为与特定实例之间的关联性实例之间的关联性。数据洗牌+确定算法；第5页，本讲稿共92页蒙特卡罗算法蒙特卡罗算法蒙特卡罗算法用于求解问题的准确解在有些情况下，近似解没有意义，比如“0/1”判定问题可以求得问题的一个解，但该解未必正确可以求得问题的一个解，但该解未必正确求得正确解的概率依赖于算法的计算时间蒙特卡罗算法的主要缺点就在于无法有效判定所得到的解是否肯定正确。第6页，本讲稿共92页拉斯维加斯算法拉斯维加斯算法拉斯维加斯算法算法

4、停止时总能产生正确答案，但运行时间是输入的随机变量（不排除无穷步骤的可能性），而且其期望值是有界的。不会得到不正确的解但有时找不到问题的解但有时找不到问题的解找到正确解的概率随算法计算时间的增加而提高用同一拉斯维加斯算法反复对问题实例求解足够多次，可使求解失败的概率任意小。第7页，本讲稿共92页Sherwood算法：正确的概率算法：对一个问题，如果存在一个Sherwood算法，则一定有正确性算法。Las Vegas算法：算法结束时给出的答案总是正确的，以正的概率使算法停止；没有执行步骤的上界；算法执行步骤的期望值有保证。Monte Carlo算法：算法以正的概率给出正确答案，总能停机；执行步数

5、有限，一般给定执行步骤的上界。第8页，本讲稿共92页提纲随机数数值概率算法舍伍德算法拉斯维加斯算法蒙特卡罗算法本章小结第9页，本讲稿共92页提纲随机数随机数数值概率算法舍伍德算法拉斯维加斯算法蒙特卡罗算法本章小结第10页，本讲稿共92页随机数随机数随机数在科学计算中扮演非常重要的角色。现有的随机数产生器所产生的随机数都是伪随机数现有的随机数产生器所产生的随机数都是伪随机数在一定程度上是随机的常用的随机数产生方法线性同余法线性同余法第11页，本讲稿共92页线性同余法该随机序列的种子该随机序列的种子如何选取常数如何选取常数b、c、m将直接影响到所将直接影响到所产生随机序列的随机性。产生随机序列的随

6、机性。第12页，本讲稿共92页随机序列的产生与实验随机序列的产生随机序列的产生参看教材page241-242RandomfRandom模拟抛硬币实验模拟抛硬币实验参看教材page243-244第13页，本讲稿共92页提纲随机数数值概率算法数值概率算法舍伍德算法拉斯维加斯算法蒙特卡罗算法本章小结第14页，本讲稿共92页通过实例学习数值概率算法用随机投点法计算值计算定积分解非线性方程组第15页，本讲稿共92页用随机投点法计算用随机投点法计算值值计算定积分计算定积分解非线性方程组解非线性方程组第16页，本讲稿共92页用随机投点法计算值算法思想算法思想设有一半径为r的圆及其外切四边形。向该正方形随机投

7、掷n个点。落入圆内的点数为k。第17页，本讲稿共92页用随机投点法计算用随机投点法计算值值计算定积分计算定积分解非线性方程组解非线性方程组第18页，本讲稿共92页计算定积分用随机投点法计算定积分用平均值法计算定积分第19页，本讲稿共92页用随机投点法计算定积分Y=f(x)Gxy101第20页，本讲稿共92页用平均值法计算定积分第21页，本讲稿共92页第22页，本讲稿共92页满足概率分布函满足概率分布函数数f(x)的要求的要求第23页，本讲稿共92页算法实现用随机投点法计算定积分参看教材page245-246用平均值法计算定积分参看教材page246-247第24页，本讲稿共92页用随机投点法计

8、算用随机投点法计算值值计算定积分计算定积分解非线性方程组解非线性方程组第25页，本讲稿共92页解非线性方程组求解过程会出现一些麻烦，求解过程会出现一些麻烦，甚至使方法失效而无法获得甚至使方法失效而无法获得一个近似解一个近似解第26页，本讲稿共92页利用概率算法求解方法直观、简单，方法直观、简单，但工作量较大但工作量较大第27页，本讲稿共92页算法改进第28页，本讲稿共92页概率算法在求解非线性方程组时，虽然有概率算法在求解非线性方程组时，虽然有些耗时，但实际应用中还是比较有效的，些耗时，但实际应用中还是比较有效的，对于那些精度要求较高的问题，对于那些精度要求较高的问题，概率算法概率算法往往会为

9、其提供一个较好的初始值往往会为其提供一个较好的初始值。算法实现过程参看教材page248-249第29页，本讲稿共92页提纲随机数数值概率算法舍伍德算法舍伍德算法拉斯维加斯算法蒙特卡罗算法本章小结第30页，本讲稿共92页舍伍德算法舍伍德算法舍伍德算法目的：设法消除最坏情形行为与特定实例之间设法消除最坏情形行为与特定实例之间的关联性。的关联性。其计算时间复杂性对所有实例而言相对均匀，但同相应的确定性算法相比，其平均时间复杂性没有改进。第31页，本讲稿共92页第32页，本讲稿共92页第33页，本讲稿共92页实例说明线性时间选择跳跃表第34页，本讲稿共92页线性时间选择线性时间选择跳跃表跳跃表第35

10、页，本讲稿共92页线性时间选择线性时间选择线性时间选择问题所在：选择合适的划分基准对于选择问题，用拟中位数作为划分基准可以保证在最坏情况下用线性时间完成选择。舍伍德型选择算法舍伍德型选择算法随机选择一个组元素作为划分基准，既保证算法的线性时间平均性能，又可以避免计算中位数的麻烦。第36页，本讲稿共92页Select算法分析第37页，本讲稿共92页Select算法分析如何得到？如何得到？第38页，本讲稿共92页考虑这种情况：无论考虑这种情况：无论n是奇数是奇数还是偶数，还是偶数，T(n/2)都出现都出现2次次第39页，本讲稿共92页结论结论结论非递归的舍伍德型选择算法Select可以在O(n)平

11、均时间内找出个输入元素中的第小元素提示提示对于某些确定性算法，可以将其改造成舍伍德算法，使得该算法以高概率对任何实例均有效。对于某些不能直接改造的情况，可以借助预处借助预处理技术理技术，不改变原有的确定性算法，而仅对其对其输入元素进行随机洗牌输入元素进行随机洗牌，同样可以收到舍伍德算法的效果。第40页，本讲稿共92页线性时间选择线性时间选择跳跃表跳跃表第41页，本讲稿共92页跳跃表跳跃表跳跃表如果用有序链表来表示一个含有个元素的有序集合，则在最坏情况下，搜索中的一个元素需要(n)计算时间。为了跳高效率，可以在部分结点处增加附加指针来提高搜索性能（借助这些附加指针，可以跳过链表中的若干结点，从而

12、加快搜索速度）。这种增加了向前附加指这种增加了向前附加指针的有序链表称为跳跃表。针的有序链表称为跳跃表。第42页，本讲稿共92页11131719230举例说明没有附加指针的有序链表没有附加指针的有序链表1113171923011113171923012增加附加指针后的有序链表增加附加指针后的有序链表跳跃表跳跃表第43页，本讲稿共92页如何进行搜索？1113171923012问题：问题：如何在该跳跃表中搜索元素？如何在该跳跃表中搜索元素？第44页，本讲稿共92页如何在该跳跃表中搜索元素？1113171923012元素位置元素位置11131719230121113171923012元素位置元素位置

13、？元素不在集合中元素不在集合中第45页，本讲稿共92页有序链表跳跃表第46页，本讲稿共92页存在的问题应在哪些结点增加附应在哪些结点增加附加指针，增加多少？加指针，增加多少？11131719230第47页，本讲稿共92页随机算法的引入解决方案解决方案采用随机化方法来确定附加指针的增加结点位置和数量。使得跳跃表可以在O(logn)平均时间内支持关于有序集的搜索、插入和删除等运算操作。实现方案参看教材page255-256第48页，本讲稿共92页1113171923012如何保持附加指针的如何保持附加指针的平衡性，如何随机生平衡性，如何随机生成新插入结点的级别成新插入结点的级别第49页，本讲稿共9

14、2页附加指针的平衡性可用于指导附加指针可用于指导附加指针的设置的设置第50页，本讲稿共92页解决方案具体实现说明请参看教材具体实现说明请参看教材page254第51页，本讲稿共92页随机生成新插入结点的级别解决方案解决方案在完全跳跃表中，具有i级指针的结点中有一半同时具有i+1级指针方案方案事先确定一个实数p(0p1)，并要求在跳跃表中维持在具有i级指针的结点中同时具有i+1级指针的结点所占比例为p。在插入一个新结点时，先将其结点级别初始化为0，然后随机反复产生一个0，1间的随机实数q。如果q=p为止。为避免出现过大的结点级别，用log1/pn作为新结点级别的上界参看教材参看教材page254

15、-255第52页，本讲稿共92页跳跃表的算法实现跳跃表的算法实现算法实现参看教材page254-259第53页，本讲稿共92页提纲随机数数值概率算法舍伍德算法拉斯维加斯算法拉斯维加斯算法蒙特卡罗算法本章小结第54页，本讲稿共92页拉斯维加斯算法拉斯维加斯算法拉斯维加斯算法(Las Vegas)能够显著改进算法的有效性，对某些目前还找不到有效算法的问题，也能得到较为满意的算法不会得到不正确的解，但有时找不到问题的解但有时找不到问题的解通常用boolean型方法来表示拉斯维加斯算法找到解，返回true;未找到解，返回false;此时，可以对同一实例再次调用相同的算法由随机算法的性质决定由随机算法的

16、性质决定第55页，本讲稿共92页效率分析Public static void obstinate(Object x,Object y)boolean success=false;while(!success)success=lv(x,y)反复调用拉斯维加斯反复调用拉斯维加斯算法算法lv(x,y)，直到找，直到找到问题的一个解到问题的一个解y设p(x)是对输入调用拉斯维加斯算法获得问题一个解的概率，p(x)0设t(x)是算法obstinate对于具体实例找到解的平均时间s(x)和e(x)分别是算法对于具体实例求解成功或失败所需的平均时间第56页，本讲稿共92页实例说明实例说明实例说明后问题整数因

17、子分解第57页，本讲稿共92页后问题后问题整数因子分解整数因子分解第58页，本讲稿共92页后问题后问题后问题问题描述：在n*n格的棋盘上放置彼此不受攻击的个皇后。用回溯法求解时，算法系统地对整个解空间树进行搜索，从而得到问题的解时问题的一个解时问题的一个解第59页，本讲稿共92页被忽视的问题细节被忽视的问题细节被忽视的问题细节对于后问题的任意一个解，每个皇后在棋盘上的位置无任何规律，不具有系统性（更象是被随机放置的更象是被随机放置的）；可以在棋盘上相继的各行中随机放置皇后可以在棋盘上相继的各行中随机放置皇后,注意使新位置上的皇后与已放置的皇后注意使新位置上的皇后与已放置的皇后之间互不攻击之间互

18、不攻击,直到直到N个皇后全部放置好个皇后全部放置好(或下一个皇后没有可以放置的位置或下一个皇后没有可以放置的位置)为止为止第60页，本讲稿共92页算法实现Public static void nQueen()x=new intn+1;for(int i=0;i=n;i+)xi=0;/初始化x /反复调用随机放置皇后的拉斯维加斯算法，直到放置成功 while(!queensLV();算法实现参看教材算法实现参看教材page260！存在的问题：！存在的问题：一旦出现无法下一个皇后无法放一旦出现无法下一个皇后无法放置的情况，整个放置方案就需要置的情况，整个放置方案就需要推倒重来，而该方案中不排除包推

19、倒重来，而该方案中不排除包含部分合理的皇后位置设置含部分合理的皇后位置设置第61页，本讲稿共92页解决方案随机放置策略随机放置策略回溯法回溯法先按照随机放置策略，在棋盘上的若干行上先按照随机放置策略，在棋盘上的若干行上放置皇后（互不攻击），然后在剩下的行中，放置皇后（互不攻击），然后在剩下的行中，利用回溯法来完成其余皇后的放置工作，直利用回溯法来完成其余皇后的放置工作，直到所有皇后被放置完毕或无法为下一个皇后到所有皇后被放置完毕或无法为下一个皇后安排位置为止安排位置为止随机放置的皇后数越多，随机放置的皇后数越多，后续回溯搜索的时间就越后续回溯搜索的时间就越少，但失败概率也越大少，但失败概率也越

20、大*算法实现参看教材算法实现参看教材page261-263第62页，本讲稿共92页随机放置皇后数对算法效率的影响随机放置皇后数pset1.0000114.00-114.001.000039.63-39.630.875022.5339.6728.200.493113.4815.1029.010.261810.318.7935.100.16249.337.2946.920.13759.056.9853.500.12939.006.9755.930.12939.006.9755.93解皇后问题的拉斯维加斯算法中，随机放置皇后数解皇后问题的拉斯维加斯算法中，随机放置皇后数所对应的算法效率所对应的算法效

21、率单纯使用回溯法单纯使用回溯法单纯使用随机放单纯使用随机放置策略置策略第63页，本讲稿共92页后问题后问题整数因子分解整数因子分解第64页，本讲稿共92页整数因子分解第65页，本讲稿共92页用于整数因子分割的split算法private static void split(n)int m=(int)Math.floor(Math.sqrt(double)n);for(int i=2;i0即可；第75页，本讲稿共92页偏y0蒙特卡罗算法第76页，本讲稿共92页分析第77页，本讲稿共92页第78页，本讲稿共92页第79页，本讲稿共92页每一次调用每一次调用MC(x)都产生错误解，但都产生错误解，但

22、发生这种情况的概率发生这种情况的概率(1-p)k第80页，本讲稿共92页总结第81页，本讲稿共92页知识点蒙特卡罗算法的基本思想实例分析实例分析主元素问题素数测试第82页，本讲稿共92页主元素问题主元素问题素数测试素数测试第83页，本讲稿共92页主元素问题第84页，本讲稿共92页public static boolean majority(int t,int n)rnd=new Random();int i=rnd.fRandom();int x=ti;/随机选择数组元素 int k=0;for(int j=1;in/2);/kn/2时，含有主元素 返回结果为返回结果为true，表示是数组的主

23、元素，表示是数组的主元素（说明含有主元素）；（说明含有主元素）；返回结果为返回结果为false，表示不是数组的主元素，表示不是数组的主元素（但并不说明中不含有主元素但并不说明中不含有主元素）；）；由于数组中非主元由于数组中非主元素的个数素的个数1/2，且majority2也返回true；（）majority返回false的概率，且majority2要再次调用majority；如果不含有主元素，则majority返回的肯定是false，则且majority2也返回false；当含有主元素时，majority2返回true的概率为p+(1-p)p3/4 majority2是一个偏真是一个偏真3/4

24、正确的蒙特卡罗算法正确的蒙特卡罗算法第86页，本讲稿共92页主元素问题主元素问题素数测试素数测试第87页，本讲稿共92页素数测试素数测试素数测试Wilson定理：对于给定的正整数，判定它为一个素数的充要条件是(n-1)!-1(mod n)理论价值高，但实际测试计算量大目前，尚未找到素数测试的有效确定性方法或拉斯维加斯算法费尔马小定理小定理第88页，本讲稿共92页费尔马小定理费尔马小定理小定理如果是一个素数，且0ap，则ap-11(mod p)判定一个数是否为素数的必要条件满足费尔马小定理条件的整数未必都是素数，比如561，这些满足条件的合数被称做Carmichael数采用二次探二次探测定理定理

25、来避免将这些合数误判为素数第89页，本讲稿共92页二次探测定理二次探测定理二次探测定理如果是一个素数，且0 xp，则方程x21(mod p)的解为x=1,p-1可以在利用费尔马小定理计算an-1 mod n的过程中增加对于整数的二次测试。*素数测试的蒙特卡罗算法的实现参看教材素数测试的蒙特卡罗算法的实现参看教材page265第90页，本讲稿共92页提纲随机数数值概率算法舍伍德算法拉斯维加斯算法蒙特卡罗算法本章小结本章小结第91页，本讲稿共92页本章小结本章小结本章小结概率算法的基本特征四种类型的概率算法（基本概念实例分析）数值概率算法蒙特卡罗算法拉斯维加斯算法舍伍德算法第92页，本讲稿共92页