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

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

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

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

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

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

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

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

7、其外切四边形。向该正方形随机投掷n个点。落入圆内的点数为k。本讲稿第十七页，共九十二页用随机投点法计算用随机投点法计算值值计算定积分计算定积分解非线性方程组解非线性方程组本讲稿第十八页，共九十二页计算定积分用随机投点法计算定积分用平均值法计算定积分本讲稿第十九页，共九十二页用随机投点法计算定积分Y=f(x)Gxy101本讲稿第二十页，共九十二页用平均值法计算定积分本讲稿第二十一页，共九十二页本讲稿第二十二页，共九十二页满足概率分布函数满足概率分布函数f(x)的要求的要求本讲稿第二十三页，共九十二页算法实现用随机投点法计算定积分参看教材page245-246用平均值法计算定积分参看教材page2

8、46-247本讲稿第二十四页，共九十二页用随机投点法计算用随机投点法计算值值计算定积分计算定积分解非线性方程组解非线性方程组本讲稿第二十五页，共九十二页解非线性方程组求解过程会出现一些麻烦，求解过程会出现一些麻烦，甚至使方法失效而无法获得甚至使方法失效而无法获得一个近似解一个近似解本讲稿第二十六页，共九十二页利用概率算法求解方法直观、简单，方法直观、简单，但工作量较大但工作量较大本讲稿第二十七页，共九十二页算法改进本讲稿第二十八页，共九十二页概率算法在求解非线性方程组时，虽然有些概率算法在求解非线性方程组时，虽然有些耗时，但实际应用中还是比较有效的，对于耗时，但实际应用中还是比较有效的，对于那

9、些精度要求较高的问题，那些精度要求较高的问题，概率算法往往会概率算法往往会为其提供一个较好的初始值为其提供一个较好的初始值。算法实现过程参看教材page248-249本讲稿第二十九页，共九十二页提纲随机数数值概率算法舍伍德算法舍伍德算法拉斯维加斯算法蒙特卡罗算法本章小结本讲稿第三十页，共九十二页舍伍德算法舍伍德算法舍伍德算法目的：设法消除最坏情形行为与特定实例之间设法消除最坏情形行为与特定实例之间的关联性。的关联性。其计算时间复杂性对所有实例而言相对均匀，但同相应的确定性算法相比，其平均时间复杂性没有改进。本讲稿第三十一页，共九十二页本讲稿第三十二页，共九十二页本讲稿第三十三页，共九十二页实例

10、说明线性时间选择跳跃表本讲稿第三十四页，共九十二页线性时间选择线性时间选择跳跃表跳跃表本讲稿第三十五页，共九十二页线性时间选择线性时间选择线性时间选择问题所在：选择合适的划分基准对于选择问题，用拟中位数作为划分基准可以保证在最坏情况下用线性时间完成选择。舍伍德型选择算法舍伍德型选择算法随机选择一个组元素作为划分基准，既保证算法的线性时间平均性能，又可以避免计算中位数的麻烦。本讲稿第三十六页，共九十二页Select算法分析本讲稿第三十七页，共九十二页Select算法分析如何得到？如何得到？本讲稿第三十八页，共九十二页考虑这种情况：无论考虑这种情况：无论n是奇数还是奇数还是偶数，是偶数，T(n/2

11、)都出现都出现2次次本讲稿第三十九页，共九十二页结论结论结论非递归的舍伍德型选择算法Select可以在O(n)平均时间内找出个输入元素中的第小元素提示提示对于某些确定性算法，可以将其改造成舍伍德算法，使得该算法以高概率对任何实例均有效。对于某些不能直接改造的情况，可以借助预处借助预处理技术理技术，不改变原有的确定性算法，而仅对其对其输入元素进行随机洗牌输入元素进行随机洗牌，同样可以收到舍伍德算法的效果。本讲稿第四十页，共九十二页线性时间选择线性时间选择跳跃表跳跃表本讲稿第四十一页，共九十二页跳跃表跳跃表跳跃表如果用有序链表来表示一个含有个元素的有序集合，则在最坏情况下，搜索中的一个元素需要(n

12、)计算时间。为了跳高效率，可以在部分结点处增加附加指针来提高搜索性能（借助这些附加指针，可以跳过链表中的若干结点，从而加快搜索速度）。这种增加了向前附加指针的有这种增加了向前附加指针的有序链表称为跳跃表。序链表称为跳跃表。本讲稿第四十二页，共九十二页11131719230举例说明没有附加指针的有序链表没有附加指针的有序链表1113171923011113171923012增加附加指针后的有序链表增加附加指针后的有序链表跳跃表跳跃表本讲稿第四十三页，共九十二页如何进行搜索？1113171923012问题：问题：如何在该跳跃表中搜索元素？如何在该跳跃表中搜索元素？本讲稿第四十四页，共九十二页如何在

13、该跳跃表中搜索元素？1113171923012元素位置元素位置11131719230121113171923012元素位置元素位置？元素不在集合中元素不在集合中本讲稿第四十五页，共九十二页有序链表跳跃表本讲稿第四十六页，共九十二页存在的问题应在哪些结点增加附应在哪些结点增加附加指针，增加多少？加指针，增加多少？11131719230本讲稿第四十七页，共九十二页随机算法的引入解决方案解决方案采用随机化方法来确定附加指针的增加结点位置和数量。使得跳跃表可以在O(logn)平均时间内支持关于有序集的搜索、插入和删除等运算操作。实现方案参看教材page255-256本讲稿第四十八页，共九十二页1113

14、171923012如何保持附加指针的平衡性，如何保持附加指针的平衡性，如何随机生成新插入结点的如何随机生成新插入结点的级别级别本讲稿第四十九页，共九十二页附加指针的平衡性可用于指导附加指针的设可用于指导附加指针的设置置本讲稿第五十页，共九十二页解决方案具体实现说明请参看教材具体实现说明请参看教材page254本讲稿第五十一页，共九十二页随机生成新插入结点的级别解决方案解决方案在完全跳跃表中，具有i级指针的结点中有一半同时具有i+1级指针方案方案事先确定一个实数p(0p1)，并要求在跳跃表中维持在具有i级指针的结点中同时具有i+1级指针的结点所占比例为p。在插入一个新结点时，先将其结点级别初始化

15、为0，然后随机反复产生一个0，1间的随机实数q。如果q=p为止。为避免出现过大的结点级别，用log1/pn作为新结点级别的上界参看教材参看教材page254-255本讲稿第五十二页，共九十二页跳跃表的算法实现跳跃表的算法实现算法实现参看教材page254-259本讲稿第五十三页，共九十二页提纲随机数数值概率算法舍伍德算法拉斯维加斯算法拉斯维加斯算法蒙特卡罗算法本章小结本讲稿第五十四页，共九十二页拉斯维加斯算法拉斯维加斯算法拉斯维加斯算法(Las Vegas)能够显著改进算法的有效性，对某些目前还找不到有效算法的问题，也能得到较为满意的算法不会得到不正确的解，但有时找不到问题的解但有时找不到问题

16、的解通常用boolean型方法来表示拉斯维加斯算法找到解，返回true;未找到解，返回false;此时，可以对同一实例再次调用相同的算法由随机算法的性质决定由随机算法的性质决定本讲稿第五十五页，共九十二页效率分析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)是算法o

17、bstinate对于具体实例找到解的平均时间s(x)和e(x)分别是算法对于具体实例求解成功或失败所需的平均时间本讲稿第五十六页，共九十二页实例说明实例说明实例说明后问题整数因子分解本讲稿第五十七页，共九十二页后问题后问题整数因子分解整数因子分解本讲稿第五十八页，共九十二页后问题后问题后问题问题描述：在n*n格的棋盘上放置彼此不受攻击的个皇后。用回溯法求解时，算法系统地对整个解空间树进行搜索，从而得到问题的解时问题的一个解时问题的一个解本讲稿第五十九页，共九十二页被忽视的问题细节被忽视的问题细节被忽视的问题细节对于后问题的任意一个解，每个皇后在棋盘上的位置无任何规律，不具有系统性（更象是被随机

18、放置的更象是被随机放置的）；可以在棋盘上相继的各行中随机放置皇后可以在棋盘上相继的各行中随机放置皇后,注意使新位置上的皇后与已放置的皇后之注意使新位置上的皇后与已放置的皇后之间互不攻击间互不攻击,直到直到N个皇后全部放置好个皇后全部放置好(或或下一个皇后没有可以放置的位置下一个皇后没有可以放置的位置)为止为止本讲稿第六十页，共九十二页算法实现Public static void nQueen()x=new intn+1;for(int i=0;i=n;i+)xi=0;/初始化x /反复调用随机放置皇后的拉斯维加斯算法，直到放置成功 while(!queensLV();算法实现参看教材算法实现参

19、看教材page260！存在的问题：！存在的问题：一旦出现无法下一个皇后无法放置一旦出现无法下一个皇后无法放置的情况，整个放置方案就需要推倒的情况，整个放置方案就需要推倒重来，而该方案中不排除包含部分重来，而该方案中不排除包含部分合理的皇后位置设置合理的皇后位置设置本讲稿第六十一页，共九十二页解决方案随机放置策略随机放置策略回溯法回溯法先按照随机放置策略，在棋盘上的若干行上先按照随机放置策略，在棋盘上的若干行上放置皇后（互不攻击），然后在剩下的行中，放置皇后（互不攻击），然后在剩下的行中，利用回溯法来完成其余皇后的放置工作，直利用回溯法来完成其余皇后的放置工作，直到所有皇后被放置完毕或无法为下一

20、个皇后到所有皇后被放置完毕或无法为下一个皇后安排位置为止安排位置为止随机放置的皇后数越多，后续回随机放置的皇后数越多，后续回溯搜索的时间就越少，但失败概溯搜索的时间就越少，但失败概率也越大率也越大*算法实现参看教材算法实现参看教材page261-263本讲稿第六十二页，共九十二页随机放置皇后数对算法效率的影响随机放置皇后数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.

21、500.12939.006.9755.930.12939.006.9755.93解皇后问题的拉斯维加斯算法中，随机放置皇后数所对应的算法效解皇后问题的拉斯维加斯算法中，随机放置皇后数所对应的算法效率率单纯使用回溯法单纯使用回溯法单纯使用随机放单纯使用随机放置策略置策略本讲稿第六十三页，共九十二页后问题后问题整数因子分解整数因子分解本讲稿第六十四页，共九十二页整数因子分解本讲稿第六十五页，共九十二页用于整数因子分割的split算法private static void split(n)int m=(int)Math.floor(Math.sqrt(double)n);for(int i=2;i0

22、即可；本讲稿第七十五页，共九十二页偏y0蒙特卡罗算法本讲稿第七十六页，共九十二页分析本讲稿第七十七页，共九十二页本讲稿第七十八页，共九十二页本讲稿第七十九页，共九十二页每一次调用每一次调用MC(x)都产生错误解，但都产生错误解，但发生这种情况的概率发生这种情况的概率(1-p)k本讲稿第八十页，共九十二页总结本讲稿第八十一页，共九十二页知识点蒙特卡罗算法的基本思想实例分析实例分析主元素问题素数测试本讲稿第八十二页，共九十二页主元素问题主元素问题素数测试素数测试本讲稿第八十三页，共九十二页主元素问题本讲稿第八十四页，共九十二页public static boolean majority(int t

23、,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，表示不是数组的主元素，表示不是数组的主元素（但并不说明中不含有主元素但并不说明中不含有主元素）；）；由于数组中非主元由于数组中非主元素的个数素的个数1/2，且majority2也返回true；（）majority返回false的概率，且majority2要

24、再次调用majority；如果不含有主元素，则majority返回的肯定是false，则且majority2也返回false；当含有主元素时，majority2返回true的概率为p+(1-p)p3/4 majority2是一个偏真是一个偏真3/4正确的蒙特卡罗算法正确的蒙特卡罗算法本讲稿第八十六页，共九十二页主元素问题主元素问题素数测试素数测试本讲稿第八十七页，共九十二页素数测试素数测试素数测试Wilson定理：对于给定的正整数，判定它为一个素数的充要条件是(n-1)!-1(mod n)理论价值高，但实际测试计算量大目前，尚未找到素数测试的有效确定性方法或拉斯维加斯算法费尔马小定理小定理本讲

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