《算法分析与设计里的概率算法-概率算法.ppt》由会员分享，可在线阅读，更多相关《算法分析与设计里的概率算法-概率算法.ppt（132页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1算法设计与分析算法设计与分析黄刘生黄刘生中国科学技术大学计算机系中国科学技术大学计算机系 国家高性能计算中心（合肥）国家高性能计算中心（合肥）2Ch.1 概率算法概率算法1.故故事事：想想象象自自己己是是神神化化故故事事的的主主人人公公，你你有有一一张张不不易易懂懂的的地地图图，上上面面描描述述了了一一处处宝宝藏藏的的藏藏宝宝地地点点。经经分分析析你你能能确确定定最最有有可可能能的的两两个个地地点点是是藏藏宝宝地地点点，但但二二者者相相距距甚甚远远。假假设设你你如如果果已已到到达达其其中中一一处处，就就立立即即知知道道该该处处是是否否为为藏藏宝宝地地点点。你你到到达达两两处处之之一一地地点点
2、及及从从其其中中一一处处到到另另一一处处的的距距离离是是5天天的的行行程程。进进一一步步假假设设有有一一条条恶恶龙龙，每每晚晚光光顾顾宝宝藏藏并并从从中中拿拿走走一一部部分分财财宝宝。假假设设你你取取宝宝藏的方案有两种：藏的方案有两种：1.1 引言引言3 方方案案1.花花4天天的的时时间间计计算算出出准准确确的的藏藏宝宝地地点点，然然后出发寻宝，一旦出发不能重新计算后出发寻宝，一旦出发不能重新计算 方方案案2.有有一一个个小小精精灵灵告告诉诉你你地地图图的的秘秘密密，但但你你必须付给他报酬，相当于龙必须付给他报酬，相当于龙3晚上拿走的财宝晚上拿走的财宝 若若忽忽略略可可能能的的冒冒险险和和出出
3、发发寻寻宝宝的的代代价价，你你是是否否接受小精灵的帮助？接受小精灵的帮助？显显然然，应应该该接接受受小小精精灵灵的的帮帮助助，因因为为你你只只需需给给出出3晚晚上上被被盗盗窃窃的的财财宝宝量量，否否则则你你将将失失去去4晚晚被被盗财宝量。盗财宝量。但是，若冒险，你可能做得更好！但是，若冒险，你可能做得更好！1.1 引言引言4 设设x是是你你决决定定之之前前当当日日的的宝宝藏藏价价值值，设设y是是恶恶龙龙每每晚盗走的宝藏价值，并设晚盗走的宝藏价值，并设x9y 方方案案1：4天天计计算算确确定定地地址址，行行程程5天天，你你得得到到的的宝宝藏价值为：藏价值为：x-9y 方方案案2：3y付付给给精精
4、灵灵，行行程程5天天失失去去5y，你你得得到到的的宝藏价值为：宝藏价值为：x-8y 方方案案3：投投硬硬币币决决定定先先到到一一处处，失失败败后后到到另另一一处处(冒冒险方案险方案)一次成功所得：一次成功所得：x-5y，机会，机会1/2 二次成功所得：二次成功所得：x-10y，机会，机会1/21.1 引言引言期望赢利：期望赢利：x-7.5y52.意义意义 该故事告诉我们：当一个算法面临某种选择该故事告诉我们：当一个算法面临某种选择时，有时随机选择比耗时做最优选择更好，尤其时，有时随机选择比耗时做最优选择更好，尤其是当最优选择所花的时间大于随机选择的平均时是当最优选择所花的时间大于随机选择的平均
5、时间的时侯间的时侯 显然，概率算法只能是期望的时间更有效，显然，概率算法只能是期望的时间更有效，但它有可能遭受到最坏的可能性。但它有可能遭受到最坏的可能性。63.期望时间和平均时间的区别期望时间和平均时间的区别v确定算法的平均执行时间确定算法的平均执行时间 输入规模一定的所有输入实例是等概率出现时，算法输入规模一定的所有输入实例是等概率出现时，算法的平均执行时间。的平均执行时间。v概率算法的期望执行时间概率算法的期望执行时间 反复解同一个输入实例所花的平均执行时间。反复解同一个输入实例所花的平均执行时间。因此，对概率算法可以讨论如下两种期望时间因此，对概率算法可以讨论如下两种期望时间平均的期望
6、时间平均的期望时间：所有输入实例上平均的期望执行时：所有输入实例上平均的期望执行时间间最坏的期望时间最坏的期望时间：最坏的输入实例上的期望执行时间：最坏的输入实例上的期望执行时间74.例子例子快速排序中的随机划分快速排序中的随机划分要要求求学学生生写写一一算算法法，由由老老师师给给出出输输入入实实例例，按按运运行行时时间间打打分分，所所有有学学生生均均不不敢敢用用简简单单的的划划分分，运运行行时时间间在在1500-2600ms，三三个个学学生生用用概率的方法划分，运行时间平均为概率的方法划分，运行时间平均为300ms。8皇后问题皇后问题系系统统的的方方法法放放置置皇皇后后(回回溯溯法法)较较合
7、合适适，找找出出所所有有92个个解解 O(2n)，若若只只找找92个其中的任何一个解可在线性时间内完成个其中的任何一个解可在线性时间内完成O(n)。随机法：随机法：随机地放置若干皇后能够改进回溯法，特别是当随机地放置若干皇后能够改进回溯法，特别是当n较大时较大时判断大整数是否为素数判断大整数是否为素数确定算法无法在可行的时间内判断一个数百位十进制数是否素数，确定算法无法在可行的时间内判断一个数百位十进制数是否素数，否则密码就不安全。否则密码就不安全。概率算法将有所作为：若能接受一个任意小的错误的概率概率算法将有所作为：若能接受一个任意小的错误的概率85.概率算法的特点概率算法的特点 (1)不可
8、再现性不可再现性 在同一个输入实例上，每次执行结果不尽相同，例在同一个输入实例上，每次执行结果不尽相同，例如如N-皇后问题皇后问题概率算法运行不同次将会找到不同的正确解概率算法运行不同次将会找到不同的正确解找一给定合数的非平凡因子找一给定合数的非平凡因子每次运行的结果不尽相同，但确定算法每次运行结果必每次运行的结果不尽相同，但确定算法每次运行结果必定相同定相同 (2)分析困难分析困难 要求有概率论，统计学和数论的知识要求有概率论，统计学和数论的知识96.本章约定本章约定 随机函数随机函数uniform，随机随机，均匀均匀，独立独立设设a，b为实数，为实数，ab,uniform(a,b)返回返回
9、x，a x b 设设i，j为整数，为整数，ij,uniform(i,j)=k,i k j 设设X是非空有限集，是非空有限集，uniform(X)X 10例例1：设p是是一一个个素素数数，a是是一一个个整整数数满足足1a0 do if(j is odd)s sa mod p;a a2 mod p;j j div 2;return s;Draw(a,p)/在在X中随机取一元素中随机取一元素j uniform(1.p-1);return ModularExponent(a,j,p);/在在X中随机取一元素中随机取一元素12n伪随机数发生器伪随机数发生器在实用中不可能有真正的随机数发生器，多数情况在实
10、用中不可能有真正的随机数发生器，多数情况下是用伪随机数发生器代替。下是用伪随机数发生器代替。大多数伪随机数发生器是基于一对函数：大多数伪随机数发生器是基于一对函数：S:X X,这里这里X足够大，它是种子的值域足够大，它是种子的值域R:X Y,Y是伪随机数函数的值域是伪随机数函数的值域使用使用S获得种子序列：获得种子序列：x0=g,xi=S(xi-1),i0然后使用然后使用R R获得伪随机序列：获得伪随机序列：yi=R(xi),i 0该序列必然是周期性的，但只要该序列必然是周期性的，但只要S S和和R R选的合适，该选的合适，该周期长度会非常长。周期长度会非常长。TC中可用中可用rand()和和
11、srand(time),用用GNU C更好更好131.基本特征基本特征随机决策随机决策在同一实例上执行两次其结果可能不同在同一实例上执行两次其结果可能不同在同一实例上执行两次的时间亦可能不太相同在同一实例上执行两次的时间亦可能不太相同2.分类分类Numerical,Monte Carlo,Las Vegas,Sherwood.很多人将所有概率算法很多人将所有概率算法(尤其是数字的概率算法尤其是数字的概率算法)称为称为Monte Carlo算法算法1.2 概率算法的分类概率算法的分类14数字算法数字算法随机性被最早用于求数字问题的近似解随机性被最早用于求数字问题的近似解例如，求一个系统中队列的平
12、均长度的问题，确定算法很例如，求一个系统中队列的平均长度的问题，确定算法很难得到答案难得到答案概率算法获得的答案一般是近似的，但通常算法执行的时概率算法获得的答案一般是近似的，但通常算法执行的时间越长，精度就越高，误差就越小间越长，精度就越高，误差就越小使用的理由使用的理由现实世界中的问题在原理上可能就不存在精确解现实世界中的问题在原理上可能就不存在精确解例如，实验数据本身就是近似的，一个无理数在计算机例如，实验数据本身就是近似的，一个无理数在计算机中只能近似地表示中只能近似地表示精确解存在但无法在可行的时间内求得精确解存在但无法在可行的时间内求得有时答案是以置信区间的形式给出的有时答案是以置
13、信区间的形式给出的1.2 概率算法的分类概率算法的分类15Monte Carlo算法算法(MC算法算法)蒙蒙特特卡卡洛洛算算法法1945年年由由J.Von Neumann进进行行核核武武模模拟拟提提出出的的。它它是是以以概概率率和和统统计计的的理理论论与与方方法法为为基基础础的的一一种种数数值值计计算算方方法法，它它是是双双重重近近似似：一一是是用用概概率率模模型型模模拟拟近近似似的的数数值值计计算算，二二是是用用伪随机数模拟真正的随机变量的样本。伪随机数模拟真正的随机变量的样本。这里我们指的这里我们指的MC算法是：算法是：若若问问题题只只有有1个个正正确确的的解解，而而无无近近似解的可能时使
14、用似解的可能时使用MC算法算法例如，判定问题只有真或假两种可能性，没有近似解例如，判定问题只有真或假两种可能性，没有近似解 因式分解，我们不能说某数几乎是一个因子因式分解，我们不能说某数几乎是一个因子n特特点点：MC算算法法总总是是给给出出一一个个答答案案，但但该该答答案案未未必必正正确确，成成功功(即答案是正确的即答案是正确的)的概率正比于算法执行的时间的概率正比于算法执行的时间n缺点：缺点：一般不能有效地确定算法的答案是否正确一般不能有效地确定算法的答案是否正确1.2 概率算法的分类概率算法的分类16Las Vegas算法算法(LV算法算法)LV算法绝不返回错误的答案。算法绝不返回错误的答
15、案。n特特点点：获获得得的的答答案案必必定定正正确确，但但有有时时它它仍仍根根本本就就找找不不到答案到答案。和和MC算算法法一一样样，成成功功的的概概率率亦亦随随算算法法执执行行时时间间增增加加而而增增加加。无无论论输输入入何何种种实实例例，只只要要算算法法在在该该实实例例上上运运行行足足够的次数，则算法失败的概率就任意小。够的次数，则算法失败的概率就任意小。Sherwood算法算法Sherwood算法总是给出正确的答案。算法总是给出正确的答案。当当某某些些确确定定算算法法解解决决一一个个特特殊殊问问题题平平均均的的时时间间比比最最坏坏时时间间快快得得多多时时，我我们们可可以以使使用用Sher
16、wood算算法法来来减减少少，甚甚至是消除好的和坏的实例之间的差别至是消除好的和坏的实例之间的差别。1.2 概率算法的分类概率算法的分类17这类算法主要用于找到一个数字问题的近似解这类算法主要用于找到一个数字问题的近似解1.3.1 值计算值计算n实验：将实验：将n根飞镖随机投向一正方形的靶子，计算落入此正方根飞镖随机投向一正方形的靶子，计算落入此正方形的内切圆中的飞镖数目形的内切圆中的飞镖数目k。假定飞镖击中方形靶子任一点的概率相等假定飞镖击中方形靶子任一点的概率相等(用计算机模拟比任用计算机模拟比任一飞镖高手更能保证此假设成立一飞镖高手更能保证此假设成立)设圆的半径为设圆的半径为r，面积，面
17、积s1=r2,方靶面方靶面积s2=4r2由等概率假设可知落入圆中的飞镖和正方形内的飞镖平均比为：由等概率假设可知落入圆中的飞镖和正方形内的飞镖平均比为：由此知：由此知：1.3 数字概率算法数字概率算法181.求求近似值的算法近似值的算法为简单起见，只以上图的右上为简单起见，只以上图的右上1/4象限为样本象限为样本Darts(n)k 0;for i 1 to n do x uniform(0,1);y uniform(0,1);/随机产生点随机产生点(x,y)if(x2+y2 1)then k+;/圆内圆内return 4k/n;实验结果实验结果：=3.141592654n=1000万万:3.1
18、40740,3.142568(2位精确位精确)n=1亿:3.141691,3.141363(3位精确位精确)n=10亿:3.141527,3.141507(4位精确位精确)1.3.1 值计算值计算191.求求近似值的算法近似值的算法Ex.1 若将若将y uniform(0,1)改为改为 y x,则上则上述的算法估计的值是什么？述的算法估计的值是什么？1.3.1 值计算值计算20Monte Carlo积分积分(但不是指我们定义的但不是指我们定义的MC算法算法)n概率算法概率算法1设设f:0,1 0,1是一个连续函数，则由曲线是一个连续函数，则由曲线y=f(x),x轴轴,y轴和直线轴和直线x=1围
19、成的面积由下述积分给出：围成的面积由下述积分给出：向单位面积的正方形内投镖向单位面积的正方形内投镖n次，落入阴影部分的镖的次，落入阴影部分的镖的数目为数目为k，则，则 显然，只要显然，只要n足够大足够大 1.3.2 数字数字积分分(计算定算定积分的分的值)211.概率算法概率算法1HitorMiss(f,n)k 0;for i 1 to n do x uniform(0,1);y uniform(0,1);if y f(x)then k+;return k/n;Note:是是S/4的面积，的面积，=S,1.3.2 数字数字积分分(计算定算定积分的分的值)221.概率算法概率算法1Ex2.在机器
20、上用在机器上用 估计估计值，给出不出不同的同的n值及精度。及精度。Ex3.设a,b,c和和d是是实数，且数，且a b,c d,f:a,b c,d是一个是一个连续函数，写一概率算法函数，写一概率算法计算算积分：分：注意，函数的参数是注意，函数的参数是a,b,c,d,n和和f,其中其中f用函用函数指数指针实现，请选一一连续函数做函数做实验，并，并给出出实验结果。果。1.3.2 数字数字积分分(计算定算定积分的分的值)231.概率算法概率算法1*Ex4.设设,是是(0,1)之间的常数，证明：之间的常数，证明：若若I是是 的正确值，的正确值，h h是由是由HitorHissHitorHiss算法返回的
21、算法返回的值，则当值，则当n I(1-I)/2时有：时有：Prob|h-I|Tj;1.4.2 随机的随机的预处理理44例例2：离散对数计算：离散对数计算离散对数计算困难使其可用于密码算法，数字签名等离散对数计算困难使其可用于密码算法，数字签名等定义：设定义：设 a=gx mod p记记 logg,pa=x，称，称x为为a的的(以以g为底模除为底模除p)对数对数从从p，g，a计算称计算称x为离散对数问题。为离散对数问题。简单算法：简单算法：计算计算gx对所有的对所有的x，最多计算，最多计算0 x p-1 或或 1xp，实际上离散对数，实际上离散对数是是循环群。循环群。验证验证a=gx mod p
22、 是否成立。是否成立。dlog(g,a,p)/当这样的对数不存在时，算法返回当这样的对数不存在时，算法返回p x 0;y 1;do x+;y y*g;/计算计算y=gx while(a y mod p)and(x p);return x1.4.2 随机的随机的预处理理45问题：最坏问题：最坏O(p)循环次数难以预料循环次数难以预料当满足一定条件时平均循环当满足一定条件时平均循环p/2次次当当p=24位十进制数，循环位十进制数，循环1024次次千万亿次千万亿次/秒秒(1016次次/秒秒)大约算大约算1年年(108秒秒/年年)若若p是数百位十进制？随机选择都可能无法在可行的时间内求解。是数百位十进
23、制？随机选择都可能无法在可行的时间内求解。假设有一个平均时间性能很好，但最坏情况差的确定算法求假设有一个平均时间性能很好，但最坏情况差的确定算法求logp,ga，怎样用，怎样用Sherwood算法求解该问题？算法求解该问题？设设p=19,g=2当当a=14,6时，时，log2,1914=7,log2,196=14，与，与a的取值相关的取值相关当用当用dlog求求14的离散对数时，循环的离散对数时，循环7次，求次，求6的对数时要执行的对数时要执行14次，次，用用sherwood算法应该使得与算法应该使得与a无关，用随机预处理的方法计算无关，用随机预处理的方法计算logg,pa1.4.2 随机的随
24、机的预处理理46定理定理(见见p877,31.6)dlogRH(g,a p)/求求logg,pa,a=gx mod p，求，求x /Sherwood算法算法 r uniform(0.p-2);b ModularExponent(g,r,p);/求幂模求幂模b=gr mod p c ba mod p;/y logg,pc;/使用确定性算法求使用确定性算法求logp,gc,y=r+x return(y-r)mod(p-1);/求求xEx.分析分析dlogRH的工作原理，指出该算法相应的的工作原理，指出该算法相应的u和和v1.4.2 随机的随机的预处理理47随机预处理提供了一种加密计算的可能性随机预
25、处理提供了一种加密计算的可能性假定你想计算某个实例假定你想计算某个实例x，通过，通过f(x)计算，但你缺乏计算计算，但你缺乏计算能力或是缺乏有效算法，而别人有相应的计算能力，愿能力或是缺乏有效算法，而别人有相应的计算能力，愿意为你计算意为你计算(可能会收费可能会收费)，若你愿意别人帮你计算，但你，若你愿意别人帮你计算，但你不愿意泄露你的输入实例不愿意泄露你的输入实例x，你将如何做？，你将如何做？可将随机预处理使用到可将随机预处理使用到f的计算上：的计算上：使用函数使用函数u将将x加密为某一随机实例加密为某一随机实例y 将将y提交给提交给f计算出计算出f(y)的值的值 使用函数使用函数v转换为转
26、换为f(x)上述过程，他人除了知道你的实例大小外，不知道上述过程，他人除了知道你的实例大小外，不知道x的任的任何信息，因为何信息，因为u(x,r)的概率分布的概率分布(只要只要r是随机均匀选择的是随机均匀选择的)是独立于是独立于x的。的。1.4.2 随机的随机的预处理理48设两个数组设两个数组val1.n和和ptr1.n及及head构成一个有构成一个有序的静态链表：序的静态链表：valhead valptrhead valptrptrhead valptrn-1head例：例：1.4.3 搜索有序表搜索有序表49若若val1.n本身有序，可用折半查找找某个给定的本身有序，可用折半查找找某个给定
27、的key，时，时间为间为O(lgn)。但因此处理链式结构，故最坏时间是。但因此处理链式结构，故最坏时间是(n)(n)。尽管如此，我们能够找到一个确定性算法，平均时间为尽管如此，我们能够找到一个确定性算法，平均时间为 。相应的相应的SherwoodSherwood算法的期望时间是算法的期望时间是 ，它虽然并不比确，它虽然并不比确定性算法快，但他消除了最坏实例。定性算法快，但他消除了最坏实例。假定表中元素互不相同，且所求的关键字表中存在，则给定假定表中元素互不相同，且所求的关键字表中存在，则给定x x，我们是求下标，我们是求下标i i，使，使vali=x,这里这里1i n。任何实例可以有两个参数刻
28、画：任何实例可以有两个参数刻画：前前n n个整数的排列个整数的排列x x的的rank1.4.3 搜索有序表搜索有序表50设设Sn是所有是所有n!个排列的集合，设个排列的集合，设A是一个确定性算是一个确定性算法法 tA(n,k,)表示算法表示算法A的执行时间，此时间与被的执行时间，此时间与被查找元素的秩查找元素的秩k，以及，以及val的排序的排序相关。若相关。若A A是一是一个概率算法，则个概率算法，则tA(n,k,)表示算法的期望值。无表示算法的期望值。无论算法是确定的还是概率的，论算法是确定的还是概率的，wA(n)和和mA(n)表示最表示最坏时间和平均时间，因此有：坏时间和平均时间，因此有：
29、1.4.3 搜索有序表搜索有序表511.时间为时间为O(n)的确定算法的确定算法设设xvali且且x在表中，则从位置在表中，则从位置i开始查找开始查找x的算法为：的算法为：Search(x,i)/仍可改进仍可改进while x vali do i ptri;return i;在表在表val1.n中查找中查找x的算法为：的算法为：A(x)return Search(x,head);1.4.3 搜索有序表搜索有序表521.时间为时间为O(n)的确定算法的确定算法分析：分析：设设rank(x)=k,则：则：算法算法A在在n个元素的表中查找个元素的表中查找x所需的访问数组所需的访问数组元素的次数，显然
30、与元素的次数，显然与无关无关 算法算法A A最坏时的访问次数最坏时的访问次数 算法算法A A平均的访问次数平均的访问次数 1.4.3 搜索有序表搜索有序表532.时间为时间为O(n)的概率算法的概率算法D(x)i uniform(1.n);y vali;case x y:return Search(x,ptri);/case2 otherwise:return i;/x=y 1.4.3 搜索有序表搜索有序表542.时间为时间为O(n)的概率算法的概率算法性能分析：性能分析：设设rank(x)=k,rank(vali)=j(D访问数组次数访问数组次数)若若 k j,则则 ，属于，属于case2，
31、从第，从第j小元素搜索小元素搜索若若 k=j,则则 ，属于，属于case3 1.4.3 搜索有序表搜索有序表553.平均时间为平均时间为 的确定算法的确定算法B(x)/设设x在在val1.n中中i head;max vali;/max初值是表初值是表val中最小值中最小值for j i to do /在前在前 个数中找不大于个数中找不大于x /的最大整数的最大整数y相应下标相应下标i y valj;if max y x then i j;max y;/endforreturn Search(x,i);/从从y向后搜索向后搜索for循环的目的：找不超过循环的目的：找不超过x的最大整数的最大整数y
32、，使搜索从，使搜索从y开始，若将开始，若将val1.n中的中的n个整数看作是均匀随机分布的，则在个整数看作是均匀随机分布的，则在val1.l中求中求y值就相当于在值就相当于在n个整数中，随个整数中，随机地取机地取l个整数，求这个整数，求这l个整数中不大于个整数中不大于x的最大整数的最大整数y。1.4.3 搜索有序表搜索有序表563.平均时间为平均时间为 的确定算法的确定算法算法分析：算法分析：可用一个与可用一个与l和和n相关的随机变量来分析，更简单的分析如下：相关的随机变量来分析，更简单的分析如下：设设n个整数的排列满足：个整数的排列满足：a1 a2 0，更好的情况是，更好的情况是Obstin
33、ate(x)repeatLV(x,y,success);until success;return y;设设t(x)是算法是算法obstinate找到一个正确解的期望时间，则找到一个正确解的期望时间，则 若要最小化若要最小化t(x)，则需在则需在p(x),s(x)和和e(x)之间进行某种折衷，例如，若之间进行某种折衷，例如，若要较少失败的时间，则可降低成功的概率要较少失败的时间，则可降低成功的概率p(x)。1.5 Las Vegas 算法算法601.传统的回溯法传统的回溯法置当前行为第置当前行为第1行，当前列为第行，当前列为第1列，即列，即ij1;while i 8 do /当前行号当前行号 8
34、检查当前行：从当前列检查当前行：从当前列j起向后逐列试探，寻找安全列号；起向后逐列试探，寻找安全列号；if 找到安全列号找到安全列号 then 放置皇后，将列号记入栈中，并将下一行置为当前行，即放置皇后，将列号记入栈中，并将下一行置为当前行，即i+;j1;/当前列置为当前列置为1 else 退栈回溯到上一行，即退栈回溯到上一行，即i-；移去该行已已放置的皇后，以该皇后所在列的下一列作为当前移去该行已已放置的皇后，以该皇后所在列的下一列作为当前 列；列；1.5.1 8后后问题61611.5.1 8后后问题2.Las Vegas方法v向量try1.8中存放结果tryi表示第i个皇后放在（i，try
35、i)位置上vtry1.k称为k-promising是指：若k个皇后的位置(0k 8):(1,try1),(2,try2),(k,tryk)互相不攻击，则称try1.k是k-promising的.形式化：对 ，若 有 (式1)则：行冲突：无须考虑，因为第i个皇后放在第i行，故同一行不会有两皇后62621.5.1 8后后问题列冲突：若对任意不同的两行i、j，因为其列数之差不为0，故任意两皇后不可能在同一列上。135对角线冲突：和 冲突时有：即 。故任两皇后不会在135对角线上冲突。45对角线冲突：和 冲突时有：即tryi-tryj=i-j故任两皇后不会在45对角线上冲突。综上所述，式1成立时try
36、1.k是k-promising。显然，若k 1，则向量try1.k是k-promising的，对8后问题，解是8-promising的。63631.5.1 8后后问题算法：QueensLv(success)/贪心的LV算法，所有皇后都是随机放置/若Success=true，则try1.8包含8后问题的一个解。col,diag45,diag135；/列及两对角线集合初值为空k 0；/行号repeat /try1.k是k-promising，考虑放第k+1个皇后nb 0；/计数器，nb值为（k+1)th皇后的open位置总数for i i to 8 do /i是列号 if(i col)and(i-
37、k diag45)and(i+k diag135)then /列i对（k+1）th皇后可用，但不一定马上将其放在第i列 nb nb+1；if uniform(1.nb)=1 then/或许放在第i列 j i；/注意第一次uniform一定返回1，即j一定有值1 /endif /endfor64641.5.1 8后后问题if(nb 0)then/nb=0时，第k+1个皇后尚未放好，所有位置不安全。/在所有nb个open位置上，（k+1)th皇后选择位置j的概率为1/nb tryk+1 j；/放置（k+1)th个皇后 col col j；diag45 diag45 j-k；diag135 diag
38、135 j+k；kk+1；/try1.k+1是（k+1)-promisinguntil（nb=0）or（k=8）；/当前皇后找不到合适的位置或try是 /8-promising是结束。success （nb0）；65651.5.1 8后后问题v分析设p是成功的概率（一次成功）s：成功时搜索的结点的平均数。（一个皇后放好算是搜索树上的一个结点）e：失败时搜索的结点的平均数。显然s=q（空向量try算在内）p和e理论上难于计算，但实验用计算机可以计算出：p=0.1293e=6.971在重复上述算法，直至成功时(相当于obstinate的时间），所搜索的平均结点数：大大优于回溯法，回溯法约为114个
39、结点才能求出一个解。Ex.证明：当放置（k+1)th皇后时，若有多个位置是开放的,则算法QueensLV选中其中任一位置的概率相等。66661.5.1 8后后问题v改进上述LV算法过于消极：一旦失败，从头再来而回溯法又过于乐观：一旦放置某个皇后，就进行系统回退一步的策略，而这一步往往不一定有效。折中的方法会更好吗？一般情况下为此。先用LV方法随机地放置前若干个结点，例如k个。然后使用回溯法放置后若干个结点，但不考虑重放前k个结点。若前面的随机选择位置不好，可能使得后面的位置不成功，如若前两个皇后的位置是1、3。随机放置的皇后越多，则后续回溯阶段的平均时间就越少，失败的概率也就越大。67671.
40、5.1 8后后问题折中算法只需将QueensLV的最后两行改为：until nb=0 or k=stopVegas；if（nb0)then backtrace(k,col,diag45,diag135,success);else success false；stopVegas控制随机放置皇后的个数。68681.5.1 8后后问题改进后算法的实验室结果：纯回溯时间：40msstepVegas=2 or 3：10ms（平均）纯贪心LV：23ms（平均）结论：一半略少的皇后随机放置较好。StepVegaspset011141141139.6339.6320.87522.5339.6728.230.4
41、93113.4815.129.0140.261810.318.7935.150.16249.337.2946.9260.13579.056.9853.570.129396.9755.9380.129396.9753.9369691.5.1 8后后问题-问题1：为什么仅随机放一个皇后，其效果就会大大优于纯回溯方法？-问题2：预先随机选几个皇后放置为好？由于解缺乏规律性（至少在皇后数不等于4k+2，k为某整数时），故求出stepVegas的最优值较难，但是找到一个较好（不一定是最优）的stepVegas还是可以的。12皇后：StepVegaspset时间01262262125ms50.503933
42、.8847.2380.3937ms120.04651310.2222.11基本与纯回溯相同70701.5.1 8后后问题在Apple II机器上，20个皇后：确定性的回溯算法：找到第一个解的时间大于2个小时。概率算法，随机地放置前10个皇后：5分半钟找到36个不同的解。后者找一个接比前者大约快1000倍！Ex.写一算法，求n=1220时最优的StepVegas值。-Obstinate算法在何时无限循环？当问题不存在解时。对于n皇后，要求n=4，即问题至少有一个解存在时，Obstinate算法才有可能结束。71711.5.2 模模p平方根平方根1.定义1：设p是一个奇素数，若整数x1,p-1且存
43、在一个整数y，使则x称为模p的二次剩余（quadratic residue），若y 1,p-1，则y称为x模p的平方根。v例：63是55模103的平方根，55是模103的二次剩余。2.定义2：若整数 ，且z不是模p的二次剩余，则z是模p的非二次剩余。72721.5.2 模模p平方根平方根3.定理1：任何一个模p的二次剩余至少有两个不同的平方根。pf：设x是模p的二次剩余，y是x模p的平方根。因为故只要证 且 就可证明p-y是不同于y的x模p的另一个平方根。p是奇数，否则p是偶数。另一方面，73731.5.2 模模p平方根平方根4.定理2：任一模p的二次剩余至多有两个不同的平方根pf：设 a和b
44、是x模p的平方根。即 成立。若k=0，则a=b若k0，则ab不妨设ab.又 由Th31.7知即 即 ，也就是说任意两个不同的平方根，均只有b和(p-b)两种不同形式。74741.5.2 模模p平方根平方根5.定理3：1到p-1之间的整数恰有一半是模p的二次剩余（余数）。pf：由定理1和定理2知，任一模p的二次剩余恰有两个不同的平方根，即任取二次剩余 ，只有y和p-y这两个不同的平方根 ，在1,p-1中恰有(p-1)/2对不同的平方根，每对平方根对应的模p的余数必定在1,p-1中，即此区间上恰有(p-1)/2个模p的二次剩余6.定理4：对 ，p是任一奇素数，有且x是模p的二次剩余当且仅当pf：略
45、（可用费马定理）75751.5.2 模模p平方根平方根7.判定x是否为模p的二次剩余？只要利用定理4和计算方幂模 即可。8.已知p是奇素数，x是模p的二次剩余，如何计算x模p的两个平方根？n当 时，两平方根易求，分别是n当 时，没有有效的确定性算法，只能借助与Las Vegas算法。9.Las Vegas算法。用 表示x的两个平方根中较小的一个。nDef：模p乘法（类似于复数乘法），a，b，c，d0,p-176761.5.2 模模p平方根平方根v例：设由定理4可知，7是模53的二次剩余，求7模53的平方根。当省略模53符号是，计算过程如下：77771.5.2 模模p平方根平方根注：上例中，由定
46、理4知，是模53的二次非剩余。同样可知 亦是摸53的二次非剩余。78781.5.2 模模p平方根平方根n若计算知当 时，已知 和 中有一个是模p的二次剩余，而另一个不是二次剩余，会怎样呢？例如，假定 两等式相加得：两式相减的：79791.5.2 模模p平方根平方根n例：通过计算可知为了获得7的一个平方根，需要找唯一的一个证书y使得 ，。这可使用一个Euclid算法解决n算法：设x是模p的二次剩余，p是素数且 80801.5.2 模模p平方根平方根rootLV(x,p,y,success)/计算ya uniform(1.p-1);/我们并不知道a应取多少if then/可能性很小 success
47、 true；y a；else 计算e，d使得 if d=0 then success false；/无法求出 else/c=0 success true；计算y使得 /算法成功的概率0.5,接近0.5。故平均调用两次即可求得x的平方根。81811.5.3 整数的因数分解整数的因数分解设n是一个大于1的整数，因数分解问题是找到n的一个唯一分解：这里 是正整数，且 均为素数。若n是合数，则至少有一个非平凡的因数(不是1和n本身).n的因数分解问题，即为找n的非平凡因数(设n是一个合数),它由两部分构成：prime(n)判定n是否为素数，可由Monte Carlo算法确定。split(n)当n为分数
48、时，找n的一个非平凡的因数。82821.5.3 整数的因数分解整数的因数分解1.朴素的split算法split(n)/若n是素数,返回1，否则返回找到的n的最小非平凡因数for i2 to do if(n mod i)=0 then return i;/i2 return 1;/返回平凡因数83831.5.3 整数的因数分解整数的因数分解n性能分析：最坏情况。当n是一个中等规模的整数（如大约50位十进制整数）时，最坏情况的计算时间亦不可接受。n的位数 ，当m=50时，上述算法的时间约为无论是确定性的还是概率的，没有算法能够在多项式时间O(p(m)内分解n。Dixom的概率算法分解n的时间为No
49、te：无论k和b是何正常数，均有：84841.5.3 整数的因数分解整数的因数分解2.合数的二次剩余（模素数到模合数的推广）设n是任一正整数，整数 。若x和n互素，且存在一整数 使 ，则x称为是模n的二次剩余，y称为是模n的平方根。一个模p的二次剩余，当p为素数时，恰有两个不同的平方根，但p为合数，且至少有两个奇素数因子时，不再为真。例：,注意29应与35互素，才有可能是模35的二次剩余。n定理：若n=pq，p、q是两个互不相同的素数，则每一个模n的二次剩余恰有4个平方根。85851.5.3 整数的因数分解整数的因数分解 上节的测试x是否是模p的二次剩余及找x的平方根的方法是一个有效的算法（指
50、rootLV），当n是一个合数，且n的因子分解给定时，同样存在有效的算法。但n的因数分解未给定时，目前还没有有效算法测试x是否为二次剩余及找x的平方根。3.Dixon因数分解算法。基本思想，找两个与n互素的整数a和b，使 但 蕴含着 即 假定 ，则n的某一非平凡因子x满足：.n和a+b的最大公因子是n的一个非平凡因子。例如：86861.5.3 整数的因数分解整数的因数分解Dixon(n,x,success)/找合数n的某一非平凡因子xif n是偶数 then x2；success true；else for i 2 to do if 是整数 thenx ;success true;return