算法设计与分析概率算法经典讲解.ppt

《算法设计与分析概率算法经典讲解.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1第一部分概率算法2Ch.1绪论1.故事：想象自己是神化故事的主人公，你有一张不易懂的地图，上面描述了一处宝藏的藏宝地点。经分析你能确定最有可能的两个地点是藏宝地点，但二者相距甚远。假设你如果已到达其中一处，就立即知道该处是否为藏宝地点。你到达两处之一地点及从其中一处到另一处的距离是5天的行程。进一步假设有一条恶龙，每晚光顾宝藏并从中拿走一部分财宝。假设你取宝藏的方案有两种：§1.1引言3方案1.花4天的时间计算出准确的藏宝地点，然后出发寻宝，一旦出发不能重新计算方案2.有一个小精灵告诉你地图的秘密，但你必须付给他报酬，相当于

2、龙3晚上拿走的财宝Prob1.1.1若忽略可能的冒险和出发寻宝的代价，你是否接受小精灵的帮助？显然，应该接受小精灵的帮助，因为你只需给出3晚上被盗窃的财宝量，否则你将失去4晚被盗财宝量。但是，若冒险，你可能做得更好！§1.1引言4设x是你决定之前当日的宝藏价值，设y是恶龙每晚盗走的宝藏价值，并设x>9y方案1：4天计算确定地址，行程5天，你得到的宝藏价值为：x-9y方案2：3y付给精灵，行程5天失去5y，你得到的宝藏价值为：x-8y方案3：投硬币决定先到一处，失败后到另一处(冒险方案)一次成功所得：x-5y，机会1/2二次成功

3、所得：x-10y，机会1/2§1.1引言}期望赢利：x-7.5y52.意义该故事告诉我们：当一个算法面临某种选择时，有时随机选择比耗时做最优选择更好，尤其是当最优选择所花的时间大于随机选择的平均时间的时侯显然，概率算法只能是期望的时间更有效，但它有可能遭受到最坏的可能性。63.期望时间和平均时间的区别确定算法的平均执行时间输入规模一定的所有输入实例是等概率出现时，算法的平均执行时间。概率算法的期望执行时间反复解同一个输入实例所花的平均执行时间。因此，对概率算法可以讨论如下两种期望时间平均的期望时间：所有输入实例上平均的期望执行

4、时间最坏的期望时间：最坏的输入实例上的期望执行时间74.例子快速排序中的随机划分要求学生写一算法，由老师给出输入实例，按运行时间打分，大部分学生均不敢用简单的划分，运行时间在1500-2600ms，三个学生用概率的方法划分，运行时间平均为300ms。8皇后问题系统的方法放置皇后(回溯法)较合适，找出所有92个解O(2n)，若只找92个其中的任何一个解可在线性时间内完成O(n)。随机法：随机地放置若干皇后能够改进回溯法，特别是当n较大时判断大整数是否为素数确定算法无法在可行的时间内判断一个数百位十进制数是否素数，否则密码就不安全

5、。概率算法将有所作为：若能接受一个任意小的错误的概率85.概率算法的特点(1)不可再现性在同一个输入实例上，每次执行结果不尽相同，例如N-皇后问题概率算法运行不同次将会找到不同的正确解找一给定合数的非平凡因子每次运行的结果不尽相同，但确定算法每次运行结果必定相同(2)分析困难要求有概率论，统计学和数论的知识96.约定随机函数uniform：随机，均匀，独立设a，b为实数，a

6、∈X10例1：设p是一个素数，a是一个整数满足1≤a

7、j≥1}的势，即i=

8、X

9、。例如，2模除31的指数等于5：25mod31=1,X={21mod31,22mod31,23mod31,24mod31,25mod31};5模除31的指数是3，即53mod31=1,3模除31的指数是30。由费马(Fermat)定理(ap-1≡1(modp))可知，a模p的指数总是恰好整除p-1.例如，设p=31，若a=2，则30÷5=6；若a

10、=5，则30÷3=10。因此，X中的j至多为p-1，由此可得一种在X中随机，均匀和独立地取一个元素的算法。11ModularExponent(a,j,p){//求方幂模s=ajmodp,注意先求aj可能会溢出s←1;whilej>0do{if(jisodd)s←s·amodp;a←a2modp;j←jdiv2;}returns;}Draw(a,p){//在X中随机取一元素j←uniform(1..p-1);returnModularExponent(a,j,p);//在X中随机取一元素}12伪随机数发生器在实用中不可能有真正的

11、随机数发生器，多数情况下是用伪随机数发生器代替。大多数伪随机数发生器是基于一对函数：S:X→X,这里X足够大，它是种子的值域R:X→Y,Y是伪随机数函数的值域使用S获得种子序列：x0=g,xi=S(xi-1),i>0然后使用R获得伪随机序列：yi=R(xi),i≥0该序列必然