第7章 数据结构与算法优秀PPT.ppt

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

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

2、学习的是第3页，共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

7、页，共92页用随机投点法计算值算法思想算法思想设有一半径为r的圆及其外切四边形。向该正方形随机投掷n个点。落入圆内的点数为k。现在学习的是第17页，共92页用随机投点法计算用随机投点法计算值值计算定积分计算定积分解非线性方程组解非线性方程组现在学习的是第18页，共92页计算定积分用随机投点法计算定积分用平均值法计算定积分现在学习的是第19页，共92页用随机投点法计算定积分Y=f(x)Gxy101现在学习的是第20页，共92页用平均值法计算定积分现在学习的是第21页，共92页现在学习的是第22页，共92页满足概率分布函数满足概率分布函数f(x)的要求的要求现在学习的是第23页，共92页算法实现用

8、随机投点法计算定积分参看教材page245-246用平均值法计算定积分参看教材page246-247现在学习的是第24页，共92页用随机投点法计算用随机投点法计算值值计算定积分计算定积分解非线性方程组解非线性方程组现在学习的是第25页，共92页解非线性方程组求解过程会出现一些麻烦，求解过程会出现一些麻烦，甚至使方法失效而无法获得甚至使方法失效而无法获得一个近似解一个近似解现在学习的是第26页，共92页利用概率算法求解方法直观、简单，方法直观、简单，但工作量较大但工作量较大现在学习的是第27页，共92页算法改进现在学习的是第28页，共92页概率算法在求解非线性方程组时，虽然有概率算法在求解非线性

9、方程组时，虽然有些耗时，但实际应用中还是比较有效的，些耗时，但实际应用中还是比较有效的，对于那些精度要求较高的问题，对于那些精度要求较高的问题，概率算法概率算法往往会为其提供一个较好的初始值往往会为其提供一个较好的初始值。算法实现过程参看教材page248-249现在学习的是第29页，共92页提纲随机数数值概率算法舍伍德算法舍伍德算法拉斯维加斯算法蒙特卡罗算法本章小结现在学习的是第30页，共92页舍伍德算法舍伍德算法舍伍德算法目的：设法消除最坏情形行为与特定实例之间设法消除最坏情形行为与特定实例之间的关联性。的关联性。其计算时间复杂性对所有实例而言相对均匀，但同相应的确定性算法相比，其平均时间

10、复杂性没有改进。现在学习的是第31页，共92页现在学习的是第32页，共92页现在学习的是第33页，共92页实例说明线性时间选择跳跃表现在学习的是第34页，共92页线性时间选择线性时间选择跳跃表跳跃表现在学习的是第35页，共92页线性时间选择线性时间选择线性时间选择问题所在：选择合适的划分基准对于选择问题，用拟中位数作为划分基准可以保证在最坏情况下用线性时间完成选择。舍伍德型选择算法舍伍德型选择算法随机选择一个组元素作为划分基准，既保证算法的线性时间平均性能，又可以避免计算中位数的麻烦。现在学习的是第36页，共92页Select算法分析现在学习的是第37页，共92页Select算法分析如何得到？

11、如何得到？现在学习的是第38页，共92页考虑这种情况：无论考虑这种情况：无论n是奇数还是是奇数还是偶数，偶数，T(n/2)都出现都出现2次次现在学习的是第39页，共92页结论结论结论非递归的舍伍德型选择算法Select可以在O(n)平均时间内找出个输入元素中的第小元素提示提示对于某些确定性算法，可以将其改造成舍伍德算法，使得该算法以高概率对任何实例均有效。对于某些不能直接改造的情况，可以借助预处借助预处理技术理技术，不改变原有的确定性算法，而仅对其对其输入元素进行随机洗牌输入元素进行随机洗牌，同样可以收到舍伍德算法的效果。现在学习的是第40页，共92页线性时间选择线性时间选择跳跃表跳跃表现在学

12、习的是第41页，共92页跳跃表跳跃表跳跃表如果用有序链表来表示一个含有个元素的有序集合，则在最坏情况下，搜索中的一个元素需要(n)计算时间。为了跳高效率，可以在部分结点处增加附加指针来提高搜索性能（借助这些附加指针，可以跳过链表中的若干结点，从而加快搜索速度）。这种增加了向前附加指针的有序这种增加了向前附加指针的有序链表称为跳跃表。链表称为跳跃表。现在学习的是第42页，共92页11131719230举例说明没有附加指针的有序链表没有附加指针的有序链表1113171923011113171923012增加附加指针后的有序链表增加附加指针后的有序链表跳跃表跳跃表现在学习的是第43页，共92页如何进

13、行搜索？1113171923012问题：问题：如何在该跳跃表中搜索元素？如何在该跳跃表中搜索元素？现在学习的是第44页，共92页如何在该跳跃表中搜索元素？1113171923012元素位置元素位置11131719230121113171923012元素位置元素位置？元素不在集合中元素不在集合中现在学习的是第45页，共92页有序链表跳跃表现在学习的是第46页，共92页存在的问题应在哪些结点增加附应在哪些结点增加附加指针，增加多少？加指针，增加多少？11131719230现在学习的是第47页，共92页随机算法的引入解决方案解决方案采用随机化方法来确定附加指针的增加结点位置和数量。使得跳跃表可以在O

14、(logn)平均时间内支持关于有序集的搜索、插入和删除等运算操作。实现方案参看教材page255-256现在学习的是第48页，共92页1113171923012如何保持附加指针的平如何保持附加指针的平衡性，如何随机生成新衡性，如何随机生成新插入结点的级别插入结点的级别现在学习的是第49页，共92页附加指针的平衡性可用于指导附加指针的可用于指导附加指针的设置设置现在学习的是第50页，共92页解决方案具体实现说明请参看教材具体实现说明请参看教材page254现在学习的是第51页，共92页随机生成新插入结点的级别解决方案解决方案在完全跳跃表中，具有i级指针的结点中有一半同时具有i+1级指针方案方案事

15、先确定一个实数p(0p1)，并要求在跳跃表中维持在具有i级指针的结点中同时具有i+1级指针的结点所占比例为p。在插入一个新结点时，先将其结点级别初始化为0，然后随机反复产生一个0，1间的随机实数q。如果q=p为止。为避免出现过大的结点级别，用log1/pn作为新结点级别的上界参看教材参看教材page254-255现在学习的是第52页，共92页跳跃表的算法实现跳跃表的算法实现算法实现参看教材page254-259现在学习的是第53页，共92页提纲随机数数值概率算法舍伍德算法拉斯维加斯算法拉斯维加斯算法蒙特卡罗算法本章小结现在学习的是第54页，共92页拉斯维加斯算法拉斯维加斯算法拉斯维加斯算法(L

16、as Vegas)能够显著改进算法的有效性，对某些目前还找不到有效算法的问题，也能得到较为满意的算法不会得到不正确的解，但有时找不到问题的解但有时找不到问题的解通常用boolean型方法来表示拉斯维加斯算法找到解，返回true;未找到解，返回false;此时，可以对同一实例再次调用相同的算法由随机算法的性质决定由随机算法的性质决定现在学习的是第55页，共92页效率分析Public static void obstinate(Object x,Object y)boolean success=false;while(!success)success=lv(x,y)反复调用拉斯维加斯反复调用拉斯维

17、加斯算法算法lv(x,y)，直到找，直到找到问题的一个解到问题的一个解y设p(x)是对输入调用拉斯维加斯算法获得问题一个解的概率，p(x)0设t(x)是算法obstinate对于具体实例找到解的平均时间s(x)和e(x)分别是算法对于具体实例求解成功或失败所需的平均时间现在学习的是第56页，共92页实例说明实例说明实例说明后问题整数因子分解现在学习的是第57页，共92页后问题后问题整数因子分解整数因子分解现在学习的是第58页，共92页后问题后问题后问题问题描述：在n*n格的棋盘上放置彼此不受攻击的个皇后。用回溯法求解时，算法系统地对整个解空间树进行搜索，从而得到问题的解时问题的一个解时问题的一

18、个解现在学习的是第59页，共92页被忽视的问题细节被忽视的问题细节被忽视的问题细节对于后问题的任意一个解，每个皇后在棋盘上的位置无任何规律，不具有系统性（更象是被随机放置的更象是被随机放置的）；可以在棋盘上相继的各行中随机放置皇后可以在棋盘上相继的各行中随机放置皇后,注意使新位置上的皇后与已放置的皇后之注意使新位置上的皇后与已放置的皇后之间互不攻击间互不攻击,直到直到N个皇后全部放置好个皇后全部放置好(或或下一个皇后没有可以放置的位置下一个皇后没有可以放置的位置)为止为止现在学习的是第60页，共92页算法实现Public static void nQueen()x=new intn+1;for

19、(int i=0;i=n;i+)xi=0;/初始化x /反复调用随机放置皇后的拉斯维加斯算法，直到放置成功 while(!queensLV();算法实现参看教材算法实现参看教材page260！存在的问题：！存在的问题：一旦出现无法下一个皇后无法放置一旦出现无法下一个皇后无法放置的情况，整个放置方案就需要推倒的情况，整个放置方案就需要推倒重来，而该方案中不排除包含部分重来，而该方案中不排除包含部分合理的皇后位置设置合理的皇后位置设置现在学习的是第61页，共92页解决方案随机放置策略随机放置策略回溯法回溯法先按照随机放置策略，在棋盘上的若干行上先按照随机放置策略，在棋盘上的若干行上放置皇后（互不攻

20、击），然后在剩下的行中，放置皇后（互不攻击），然后在剩下的行中，利用回溯法来完成其余皇后的放置工作，直利用回溯法来完成其余皇后的放置工作，直到所有皇后被放置完毕或无法为下一个皇后到所有皇后被放置完毕或无法为下一个皇后安排位置为止安排位置为止随机放置的皇后数越多，后续回随机放置的皇后数越多，后续回溯搜索的时间就越少，但失败概溯搜索的时间就越少，但失败概率也越大率也越大*算法实现参看教材算法实现参看教材page261-263现在学习的是第62页，共92页随机放置皇后数对算法效率的影响随机放置皇后数pset1.0000114.00-114.001.000039.63-39.630.875022.53

21、39.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解皇后问题的拉斯维加斯算法中，随机放置皇后数所对解皇后问题的拉斯维加斯算法中，随机放置皇后数所对应的算法效率应的算法效率单纯使用回溯法单纯使用回溯法单纯使用随机放单纯使用随机放置策略置策略现在学习的是第63页，共92页后问题后问题整数因子分解整数因子分解现在学习的是第64页，共92页整数因子分解现在学习的是第65页，共92页用于整数因子分割的s

22、plit算法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)都产生错误解，但都产生错误解，但发生这种情况的概率发生这种情况的概率(1-p)k现在学习的是第80页，共92页总结现在学习的是第81页，共92页知识点蒙特卡罗算法的基本思想实例分析实例分析主元素问题素数测试现在学

23、习的是第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，表示是数组的主元素，表示是数组的主元素（说明含有主元素）；（说明含有主元素）；返回结果为返回结果为false，表示不是数组的主元素，表示不是数组的主元素（但并不说明

24、中不含有主元素但并不说明中不含有主元素）；）；由于数组中非主元由于数组中非主元素的个数素的个数1/2，且majority2也返回true；（）majority返回false的概率，且majority2要再次调用majority；如果不含有主元素，则majority返回的肯定是false，则且majority2也返回false；当含有主元素时，majority2返回true的概率为p+(1-p)p3/4 majority2是一个偏真是一个偏真3/4正确的蒙特卡罗算法正确的蒙特卡罗算法现在学习的是第86页，共92页主元素问题主元素问题素数测试素数测试现在学习的是第87页，共92页素数测试素数测试素

25、数测试Wilson定理：对于给定的正整数，判定它为一个素数的充要条件是(n-1)!-1(mod n)理论价值高，但实际测试计算量大目前，尚未找到素数测试的有效确定性方法或拉斯维加斯算法费尔马小定理小定理现在学习的是第88页，共92页费尔马小定理费尔马小定理小定理如果是一个素数，且0ap，则ap-11(mod p)判定一个数是否为素数的必要条件满足费尔马小定理条件的整数未必都是素数，比如561，这些满足条件的合数被称做Carmichael数采用二次探二次探测定理定理来避免将这些合数误判为素数现在学习的是第89页，共92页二次探测定理二次探测定理二次探测定理如果是一个素数，且0 xp，则方程x21(mod p)的解为x=1,p-1可以在利用费尔马小定理计算an-1 mod n的过程中增加对于整数的二次测试。*素数测试的蒙特卡罗算法的实现参看教材素数测试的蒙特卡罗算法的实现参看教材page265现在学习的是第90页，共92页提纲随机数数值概率算法舍伍德算法拉斯维加斯算法蒙特卡罗算法本章小结本章小结现在学习的是第91页，共92页本章小结本章小结本章小结概率算法的基本特征四种类型的概率算法（基本概念实例分析）数值概率算法蒙特卡罗算法拉斯维加斯算法舍伍德算法现在学习的是第92页，共92页