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

1、1第一部分第一部分概率算法概率算法2Ch.1 绪论绪论1. 故事：故事：想象自己是神化故事的主人公，你想象自己是神化故事的主人公，你有一张不易懂的地图，上面描述了一处宝有一张不易懂的地图，上面描述了一处宝藏的藏宝地点。经分析你能确定最有可能藏的藏宝地点。经分析你能确定最有可能的两个地点是藏宝地点，但二者相距甚远。的两个地点是藏宝地点，但二者相距甚远。假设你如果已到达其中一处，就立即知道假设你如果已到达其中一处，就立即知道该处是否为藏宝地点。你到达两处之一地该处是否为藏宝地点。你到达两处之一地点及从其中一处到另一处的距离是点及从其中一处到另一处的距离是5天的天的行程。进一步假设有一条恶龙，每晚光

2、顾行程。进一步假设有一条恶龙，每晚光顾宝藏并从中拿走一部分财宝。假设你取宝宝藏并从中拿走一部分财宝。假设你取宝藏的方案有两种：藏的方案有两种：1.1 引言引言3 方案方案1. 花花4天的时间计算出准确的藏宝地点，然天的时间计算出准确的藏宝地点，然后出发寻宝，一旦出发不能重新计算后出发寻宝，一旦出发不能重新计算 方案方案2. 有一个小精灵告诉你地图的秘密，但你有一个小精灵告诉你地图的秘密，但你必须付给他报酬，相当于龙必须付给他报酬，相当于龙3晚上拿走的财宝晚上拿走的财宝 Prob 1.1.1 若忽略可能的冒险和出发寻宝的代若忽略可能的冒险和出发寻宝的代价，你是否接受小精灵的帮助？价，你是否接受小

3、精灵的帮助？ 显然，应该接受小精灵的帮助，因为你只需显然，应该接受小精灵的帮助，因为你只需给出给出3晚上被盗窃的财宝量，否则你将失去晚上被盗窃的财宝量，否则你将失去4晚被晚被盗财宝量。盗财宝量。 但是，但是，若冒险，你可能做得更好！若冒险，你可能做得更好！1.1 引言引言4 设设x是你决定之前当日的宝藏价值，设是你决定之前当日的宝藏价值，设y是恶龙每是恶龙每晚盗走的宝藏价值，并设晚盗走的宝藏价值，并设x9y 方案方案1：4天计算确定地址，行程天计算确定地址，行程5天，你得到的宝天，你得到的宝藏价值为：藏价值为：x-9y 方案方案2：3y付给精灵，行程付给精灵，行程5天失去天失去5y，你得到的，

4、你得到的宝藏价值为：宝藏价值为：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,

9、b) 返回返回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选的合适，该选的合适，该周期

11、长度会非常长。周期长度会非常长。TC中可用中可用rand()和和srand(time), 用用GNU C更好更好131. 基本特征基本特征随机决策随机决策在同一实例上执行两次其结果可能不同在同一实例上执行两次其结果可能不同在同一实例上执行两次的时间亦可能不太相同在同一实例上执行两次的时间亦可能不太相同2. 分类分类Numerical, Monte Carlo, Las Vegas, Sherwood.很多人将所有概率算法很多人将所有概率算法(尤其是数字的概率算法尤其是数字的概率算法)称为称为Monte Carlo算法算法1.2 概率算法的分类概率算法的分类14 数字算法数字算法随机性被最早用于

12、求数字问题的近似解随机性被最早用于求数字问题的近似解例如，求一个系统中队列的平均长度的问题，确定算例如，求一个系统中队列的平均长度的问题，确定算法很难得到答案法很难得到答案l 概率算法获得的答案一般是近似的，但通常算法执行概率算法获得的答案一般是近似的，但通常算法执行的时间越长，精度就越高，误差就越小的时间越长，精度就越高，误差就越小l 使用的理由使用的理由 现实世界中的问题在原理上可能就不存在精确解现实世界中的问题在原理上可能就不存在精确解例如，实验数据本身就是近似的，一个无理数在计例如，实验数据本身就是近似的，一个无理数在计算机中只能近似地表示算机中只能近似地表示 精确解存在但无法在可行的

13、时间内求得精确解存在但无法在可行的时间内求得有时答案是以置信区间的形式给出的有时答案是以置信区间的形式给出的1.2 概率算法的分类概率算法的分类15 Monte Carlo算法算法 (MC算法算法)蒙特卡洛算法蒙特卡洛算法1945年由年由J. Von Neumann进行核武模拟提出进行核武模拟提出的。它是以概率和统计的理论与方法为基础的一种数值计算的。它是以概率和统计的理论与方法为基础的一种数值计算方法，它是双重近似：一是用概率模型模拟近似的数值计算，方法，它是双重近似：一是用概率模型模拟近似的数值计算，二是用伪随机数模拟真正的随机变量的样本。二是用伪随机数模拟真正的随机变量的样本。这里我们指

14、的这里我们指的MC算法是：算法是： 若问题只有若问题只有1个正确的解，而无近个正确的解，而无近似解的可能时使用似解的可能时使用MC算法算法例如，判定问题只有真或假两种可能性，没有近似解例如，判定问题只有真或假两种可能性，没有近似解 因式分解，我们不能说某数几乎是一个因子因式分解，我们不能说某数几乎是一个因子n 特点：特点：MC算法总是给出一个答案算法总是给出一个答案，但该答案未必正确，但该答案未必正确，成成功功(即答案是正确的即答案是正确的)的概率正比于算法执行的时间的概率正比于算法执行的时间n 缺点：缺点：一般不能有效地确定算法的答案是否正确一般不能有效地确定算法的答案是否正确1.2 概率算

15、法的分类概率算法的分类16 Las Vegas算法算法 (LV算法算法)LV算法绝不返回错误的答案。算法绝不返回错误的答案。n 特点：特点：获得的答案必定正确获得的答案必定正确，但有时它仍，但有时它仍根本就找不根本就找不到答案到答案。 和和MC算法一样，成功的概率亦随算法执行时间增加而增算法一样，成功的概率亦随算法执行时间增加而增加。无论输入何种实例，只要算法在该实例上运行足够加。无论输入何种实例，只要算法在该实例上运行足够的次数，则算法失败的概率就任意小。的次数，则算法失败的概率就任意小。 Sherwood算法算法Sherwood算法总是给出正确的答案。算法总是给出正确的答案。当某些确定算法

16、解决一个特殊问题平均的时间比最坏时当某些确定算法解决一个特殊问题平均的时间比最坏时间快得多时，我们可以使用间快得多时，我们可以使用Sherwood算法来算法来减少，甚减少，甚至是消除好的和坏的实例之间的差别至是消除好的和坏的实例之间的差别。1.2 概率算法的分类概率算法的分类17这类算法主要用于找到一个数字问题的近似解这类算法主要用于找到一个数字问题的近似解2.1 值计算值计算n实验：将实验：将n根飞镖随机投向一正方形的靶子，计算落入此正方根飞镖随机投向一正方形的靶子，计算落入此正方形的内切圆中的飞镖数目形的内切圆中的飞镖数目k。假定飞镖击中方形靶子任一点的概率相等假定飞镖击中方形靶子任一点的

17、概率相等(用计算机模拟比任用计算机模拟比任一飞镖高手更能保证此假设成立一飞镖高手更能保证此假设成立)设圆的半径为设圆的半径为r，面积，面积s1= r2； 方靶面积方靶面积s2=4r2由等概率假设可知落入圆中的飞镖和正方形内的飞镖平均比为：由等概率假设可知落入圆中的飞镖和正方形内的飞镖平均比为：由此知：由此知： Ch.2 数字概率算法数字概率算法2244krnr4 /4nk n k18n求求近似值的算法近似值的算法为简单起见，只以上图的右上为简单起见，只以上图的右上1/4象限为样本象限为样本Darts (n) k 0;for i 1 to n do x uniform(0, 1);y unifo

18、rm(0, 1); / 随机产生点随机产生点(x,y)if (x2 + y2 1) then k+; /圆内圆内return 4k/n;实验结果实验结果： =3.141592654n = 1000万万: 3.140740, 3.142568 (2位精确位精确)n = 1亿亿: 3.141691, 3.141363 (3位精确位精确)n = 10亿亿: 3.141527, 3.141507 (4位精确位精确)2.1 值计算值计算19求求近似值的算法近似值的算法Ex.1 若将若将y uniform(0, 1) 改为改为 y x, 则上则上述的算法估计的值是什么？述的算法估计的值是什么？2.1 值计

19、算值计算20Monte Carlo积分积分(但不是指我们定义的但不是指我们定义的MC算法算法)1、概率算法概率算法1设设f: 0, 1 0, 1是一个连续函数，则由曲线是一个连续函数，则由曲线y=f(x), x轴轴, y轴和直线轴和直线x=1围成的面积由下述积分给出：围成的面积由下述积分给出：向单位面积的正方形内投镖向单位面积的正方形内投镖n次，落入阴影部分的镖的次，落入阴影部分的镖的数目为数目为k，则，则显然，只要显然，只要n足够大足够大2.2 数字积分数字积分 (计算定积分的值计算定积分的值)10( )Sf x dx/1kSSk nn/Sk n 211.概率算法概率算法1HitorMiss

20、 (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, 2.2 数字积分数字积分 (计算定积分的值计算定积分的值)1201x dx12041x dx221. 概率算法概率算法1Ex2. 在机器上用在机器上用 估计估计值，给出不值，给出不同的同的n值及精度。值及精度。Ex3. 设设a, b, c和和d是实数，且是实数，且a b, c d, f:a, b c, d是一个连续函数，写一概率算法计是一个连续函数，写一概率算法计算积分：

21、算积分：注意，函数的参数是注意，函数的参数是a, b, c, d, n和和f, 其中其中f用函用函数指针实现，请选一连续函数做实验，并给出数指针实现，请选一连续函数做实验，并给出实验结果。实验结果。2.2 数字积分数字积分 (计算定积分的值计算定积分的值)12041x dx( )baf x dx231.概率算法概率算法1*Ex4. 设设,是是(0,1)之间的常数，证明：之间的常数，证明：若若I是是 的正确值，的正确值，h h是由是由HitorMissHitorMiss算法返回的算法返回的值，则当值，则当n I(1-I)/2时有：时有：Prob|h-I| 1 上述的意义告诉我们：上述的意义告诉我

22、们：Prob|h-I| , 即：当即：当n I(1-I)/ 2时，算法的计算结果的绝对误差超过时，算法的计算结果的绝对误差超过的概率不超的概率不超过过，因此我们根据给定，因此我们根据给定和和可以确定算法迭代的次数可以确定算法迭代的次数解此问题时可用切比雪夫不等式，将解此问题时可用切比雪夫不等式，将I看作是数学期望。看作是数学期望。2.2 数字积分数字积分 (计算定积分的值计算定积分的值)10( )f x dx22(1)11(1)44IInII 242.概率算法概率算法2更有效的概率算法是：更有效的概率算法是： 在积分区间上随机均匀地产生点，求在积分区间上随机均匀地产生点，求出这些点上的函数值的

23、算术平均值，再乘以区间的宽度：出这些点上的函数值的算术平均值，再乘以区间的宽度：Crude (f, n, a, b) sum 0;for i 1 to n do x uniform(a, b);sum sum + f(x);return (b-a)sum/n;2.2 数字积分数字积分 (计算定积分的值计算定积分的值)11( )()( ),nbiiaif x dxbaf xaxbn252. 概率算法概率算法2用用HitorMiss和和Crude运行三次的结果为：运行三次的结果为：假定假定 和和 存在，由算法求得的估算存在，由算法求得的估算值的方差反比于点数值的方差反比于点数n。当。当n足够大时，

24、估计的分足够大时，估计的分布近似为正态分布。布近似为正态分布。对于给定的迭代次数对于给定的迭代次数n，Crude算法的方差不会大算法的方差不会大于于HitorMiss的方差。但不能说，的方差。但不能说，Crude算法总是算法总是优于优于HitorMiss。因为后者在给定的时间内能迭代。因为后者在给定的时间内能迭代的次数更多。例如，计算的次数更多。例如，计算值时，值时，Crude需计算需计算平方根，而用投镖算法平方根，而用投镖算法darts时无需计算平方根。时无需计算平方根。2.2 数字积分数字积分 (计算定积分的值计算定积分的值)3.141855, 3.141422, 3.14143413.1

25、41662,3.141486, 3.141527hitncrude亿( )baf x dx2( )bafx dx263.确定的算法确定的算法梯形算法梯形算法将区间分为将区间分为n-1个子区间，每个子区间内的长度为个子区间，每个子区间内的长度为，Trapezoid (f, n, a, b) / 假设假设 n 2delta (b-a)/(n-1);sum (f(a) + f(b)/2;for x a+delta step delta to b delta dosum sum + f(x)return sum delta;2.2 数字积分数字积分 (计算定积分的值计算定积分的值)f(a)f(b)=f

26、 af a 22积分值( ( + )+ ( +)+.+)273. 确定的算法确定的算法 当当n=100, =3.140399 当当n=1,000, =3.141555 当当n=10,000, =3.141586 当当n=100,000, =3.141593一般地，在同样的精度下，梯形算法的迭代次数少于一般地，在同样的精度下，梯形算法的迭代次数少于MC积分，但是积分，但是 有时确定型积分算法求不出解：有时确定型积分算法求不出解：例如，例如， f(x)=sin2(100)! x)， 。 但是用梯形算法时，当但是用梯形算法时，当2 n101时，返回值是时，返回值是0。若用若用MC积分则不会发生该类问

27、题，或虽然发生，但概率小积分则不会发生该类问题，或虽然发生，但概率小得多。得多。2.2 数字积分数字积分 (计算定积分的值计算定积分的值)101( )2f x dx 28 多重积分多重积分 在确定算法中，为了达到一定的精度，采样点的在确定算法中，为了达到一定的精度，采样点的数目随着积分维数成指数增长，例如，一维积分若有数目随着积分维数成指数增长，例如，一维积分若有100个点可达到一定的精度，则二维积分可能要计算个点可达到一定的精度，则二维积分可能要计算1002个点才能达到同样的精度，三维积分则需计算个点才能达到同样的精度，三维积分则需计算1003个点。个点。(系统的方法系统的方法) 但概率算法

28、对维数的敏感度不大，仅是每次迭代但概率算法对维数的敏感度不大，仅是每次迭代中计算的量稍增一点，实际上，中计算的量稍增一点，实际上，MC积分特别适合用积分特别适合用于计算于计算4或更高维数的定积分。或更高维数的定积分。 若要提高精度，则可用混合技术：部分采用系统若要提高精度，则可用混合技术：部分采用系统的方法，部分采用概率的方法的方法，部分采用概率的方法2.2 数字积分数字积分 (计算定积分的值计算定积分的值)29 上一节可以认为，数字概率算法被用来近似上一节可以认为，数字概率算法被用来近似一个实数，本节可用它们来估计一个整数值。例一个实数，本节可用它们来估计一个整数值。例如，设如，设X为为有限

29、集，若要求有限集，若要求X的势的势|X|，则当，则当X较大较大时，枚举显然不现实。时，枚举显然不现实。1. 问题：随机选出问题：随机选出25人，你是否愿意赌其中至少有人，你是否愿意赌其中至少有两个人生日相同吗？直觉告诉我们，一般人都不两个人生日相同吗？直觉告诉我们，一般人都不愿意赌其成立，但实际上成立的概率大于愿意赌其成立，但实际上成立的概率大于50%。2.3 概率计数概率计数30 一般地，从一般地，从n个对象中选出个对象中选出k个互不相同的对象，若考虑个互不相同的对象，若考虑 选择的次序，则不同的选择有选择的次序，则不同的选择有 种；若允许重复选取种；若允许重复选取同同 一对象，则不同的选法

30、共有一对象，则不同的选法共有 种。种。 因此，从因此，从n个对象个对象(允许同一对象重复取多次允许同一对象重复取多次)中随机均中随机均匀地选择出的匀地选择出的k个对象互不相同的概率是：个对象互不相同的概率是： ，注意，注意a，b和和b，a是不同的取法。由此可知，上述问题中，是不同的取法。由此可知，上述问题中，25个人生个人生日互不相同的概率是：日互不相同的概率是：这里假设：不考虑润年，一年中人的生日是均匀分布的。这里假设：不考虑润年，一年中人的生日是均匀分布的。2.3 概率计数概率计数!()!nnkkn!()!knnkn25365!365,25340!365nk31由由Stirling公式知：

31、公式知：可得可得 假定假定 Tj;3.2 随机的预处理随机的预处理51例例2 2：离散对数计算：离散对数计算l离散对数计算困难使其可用于密码算法，数字签名等离散对数计算困难使其可用于密码算法，数字签名等l定义：设定义：设 a=gx mod p，记，记 logg,pa=x，称，称x为为a的的(以以g为底模除为底模除p)对数。对数。 从从p，g，a计算计算x称为称为离散对数离散对数问题。问题。l简单算法简单算法 计算计算gx对所有的对所有的x，最多计算，最多计算0 x p-1 或或 1xp，因为实际，因为实际上离散对数上离散对数是循环群；是循环群； 验证验证a=gx mod p 是否成立。是否成立

32、。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 x2,7xlog3x32 mod7例无解，不存在使52l问题：最坏问题：最坏O(p)循环次数难以预料，当满足一定条件时平均循环循环次数难以预料，当满足一定条件时平均循环p/2次次当当p=24位十进制数，循环位十进制数，循环1024次，千万亿次次，千万亿次/秒秒 (1016次次/秒秒) 大约算大约算1年年(108秒秒/年年)若若p是数百位十进制？随机选择都可

33、能无法在可行的时间内求解。是数百位十进制？随机选择都可能无法在可行的时间内求解。l假设有一个平均时间性能很好，但最坏情况差的确定算法求假设有一个平均时间性能很好，但最坏情况差的确定算法求logg,pa，怎样用怎样用Sherwood算法求解该问题？算法求解该问题？设设p=19, g=2当当a=14, 6时，时，log2,1914 = 7, log2,196=14，即用，即用dlog求求14和和6的离散的离散对数时，分别要循环对数时，分别要循环7和和14次，执行时间与次，执行时间与a的取值相关。的取值相关。 用用sherwood算法应该使得与算法应该使得与a无关，用随机预处理的方法计算无关，用随机

34、预处理的方法计算logg,pa例例2 2：离散对数计算：离散对数计算53l 定理定理(见见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; /(gr modp)(gxmodp)modp=gr+xmodp=c y logg,pc; / 使用确定性算法求使用确定性算法求logp,gc, y=r+x return (y-r) mod (p-1); / 求

35、求xEx. 分析分析dlogRH的工作原理，指出该算法相应的的工作原理，指出该算法相应的u和和v3.2 随机的预处理随机的预处理,log(mod)(loglog)mod(1)log(mod)for 02g pg pg prg pstpstpgprrp54l 随机预处理提供了一种加密计算的可能性随机预处理提供了一种加密计算的可能性 假定你想计算某个实例假定你想计算某个实例x，通过，通过f(x)计算，但你缺乏计算，但你缺乏计算能力或是缺乏有效算法，而别人有相应的计算能力，计算能力或是缺乏有效算法，而别人有相应的计算能力，愿意为你计算愿意为你计算(可能会收费可能会收费)，若你愿意别人帮你计算，若你愿

36、意别人帮你计算，但你不愿意泄露你的输入实例但你不愿意泄露你的输入实例x，你将如何做？，你将如何做？可将随机预处理使用到可将随机预处理使用到f的计算上：的计算上： 使用函数使用函数u将将x加密为某一随机实例加密为某一随机实例y 将将y提交给提交给f计算出计算出f(y)的值的值 使用函数使用函数v转换为转换为f(x) 上述过程，他人除了知道你的实例大小外，不知道上述过程，他人除了知道你的实例大小外，不知道x的任何信息，因为的任何信息，因为u(x,r)的概率分布的概率分布(只要只要r是随机均匀是随机均匀选择的选择的)是独立于是独立于x的。的。3.2 随机的预处理随机的预处理55 设两个数组设两个数组

37、val1.n和和ptr1.n及及head构成一构成一个有序的静态链表：个有序的静态链表：valhead valptrhead valptrptrhead valptrn-1head例：例：3.3 搜索有序表搜索有序表:ptri给个关键标非关键即关键出出下下一一字字的的下下if vali最if vali最大大字字0 if vali是0 if vali是最最大大字字 i 1 2 3 4 5 6 7vali 2 3 13 1 5 21 8ptri 2 5 6 1 7 0 3rank 2 3 6 1 4 7 5head=4 有序表：有序表：1，2，3，5，8，13，21 56n 折半查找：折半查找：

38、若若val1.n本身有序，可用折半查找找某本身有序，可用折半查找找某个给定的个给定的key，时间为，时间为O(lgn)。n 顺序查找：顺序查找：但此表为链式结构，故最坏时间是但此表为链式结构，故最坏时间是(n)(n)。尽管如此，我们能够找到一个确定性算法，平均时间尽管如此，我们能够找到一个确定性算法，平均时间为为 。 相应的相应的SherwoodSherwood算法的期望时间是算法的期望时间是 ，它虽，它虽然并不比确定性算法快，但他消除了最坏实例。然并不比确定性算法快，但他消除了最坏实例。 假定表中元素互不相同，且所求的关键字在表中假定表中元素互不相同，且所求的关键字在表中存在，则给定存在，则

39、给定x x，我们是求下标，我们是求下标i i，使，使vali=x, 这里这里1i n。任何实例可以由两个参数刻画：任何实例可以由两个参数刻画： 前前n n个整数的排列个整数的排列 x x的的rank3.3 搜索有序表搜索有序表()On()On57设设Sn是所有是所有n!个排列的集合，设个排列的集合，设A是一个确定性算法是一个确定性算法 tA(n, k, )表示算法表示算法A的执行时间，此时间与被查的执行时间，此时间与被查找元素的秩找元素的秩k，以及，以及val的排列的排列相关。若相关。若A A是一个概是一个概率算法，则率算法，则tA(n, k, )表示算法的期望值。无论算法表示算法的期望值。无

40、论算法是确定的还是概率的，是确定的还是概率的，wA(n)和和mA(n)分别表示最坏分别表示最坏时间和平均时间，因此有：时间和平均时间，因此有： 3.3 搜索有序表搜索有序表1( )max ( , , )|1 1( )( , , )!11,2,.,1/!nAnnAASknw nt n kkn andSm ntn kn nknnSn的概率是，在 中每个排列的概率是581. 时间为时间为O(n)的确定算法的确定算法n 算法算法设设xvali且且x在表中，则从位置在表中，则从位置i开始查找开始查找x的算法为的算法为Search(x, i) /仍可改进仍可改进while x vali do i ptri

41、;return i;在表在表val1.n中查找中查找x的算法为：的算法为：A(x) return Search(x, head);3.3 搜索有序表搜索有序表59n 性能分析性能分析设设rank(x)=k, 则：则： 算法算法A在在n个元素的表中查找个元素的表中查找x所需的访问数组所需的访问数组元素的次数，元素的次数，显然与显然与无关无关 算法算法A A最坏时的访问次数最坏时的访问次数 算法算法A A平均的访问次数平均的访问次数 3.3 搜索有序表搜索有序表( , )Atn kw ( )Anm ( )An1,1, ,( , ),( ),1,2,.,11( )( , )2( )( )AAnAAk

42、nNkn tn kknNknwnnnNknnmntn knT nO n 若时为最坏情况，此时设的概率相等，则综上所述，602.时间为时间为O(n)的概率算法的概率算法n算法算法 D(x) i uniform(1.n);y vali;case x y: return Search(x, ptri); / case2 otherwise: return i; / case3， x = y3.3 搜索有序表搜索有序表61n性能分析性能分析(D访问数组次数访问数组次数) 一般情况一般情况 设设rank(x)=k, rank(vali)=j 若若 k j, 则则 ，属于，属于case2，从，从jth最小

43、元之后搜索最小元之后搜索若若 k = j, 则则 ，属于，属于case3 最坏情况最坏情况3.3 搜索有序表搜索有序表( , ) Dtn kk( , )-Dtn kkj( , )0Dtn kDDnN,w (n)?j 1,knSearchn-1w (n)n 1 当时，执行次数为， 62 平均情况平均情况3.3 搜索有序表搜索有序表121111121,( )?11,2,.,1,2,.,11( )( , )()1(1)(1)()11()22333 DjnnnnDDjkjkkjnjnN mnjnknnmntn kkkjnnnj jnjnjnnnn及的概率均为显然平均时间性能优于确定算法633.平均时间

44、为平均时间为 的确定算法的确定算法n算法算法B(x) /设设x在在val1.n中中i head;max vali; / max初值是表初值是表val中最小值中最小值for j 1 to do / 在在val的前的前 个数中找不大于个数中找不大于x y val j ; / 的最大整数的最大整数y相应的下标相应的下标i if max y x then i j; max y; /endif / endforreturn Search(x, i); / 从从y开始继续搜索开始继续搜索3.3 搜索有序表搜索有序表()Onnn64n性能分析性能分析 for循环的目的：找不超过循环的目的：找不超过x的最大整

45、数的最大整数y，使搜索从，使搜索从y开开始，若将始，若将val1.n中的中的n个整数看作是均匀随机分布的，则个整数看作是均匀随机分布的，则在在val1.L中求中求y值就相当于在值就相当于在n个整数中，随机地取个整数中，随机地取L个整个整数，求这数，求这L个整数中不大于个整数中不大于x的最大整数的最大整数y。 可用一个与可用一个与L和和n相关的随机变量来分析，更简单的分析相关的随机变量来分析，更简单的分析如下：如下：设设n个整数的排列满足：个整数的排列满足：a1 a2 0，更，更好的情况是：好的情况是：Ch.4 Las Vegas 算法算法0,( )p x常数69Obstinate(x) rep

46、eatLV(x, y, success);until success;return y; 设设t(x)是算法是算法obstinate找到一个正确解的期望时间，则找到一个正确解的期望时间，则 若要最小化若要最小化t(x)，则需在，则需在p(x), s(x)和和e(x)之间进行某种折衷，之间进行某种折衷，例如，若要减少失败的时间，则可降低成功的概率例如，若要减少失败的时间，则可降低成功的概率p(x)。Ch.4 Las Vegas 算法算法( )( ) ( )(1( )( ( )( )LV1( )( )( )( )( )t xp x s xp xe xt xLVp xt xs xe xp x成功的概

47、率失败的概率701. 传统的回溯法传统的回溯法4.1 8后问题后问题12341234iji+j 135度度对对角角线线：同同一一条条对对角角线线上上的的元元素素的的行行列列号号之之和和相相等等 i-j或或j-i 45度度对对角角线线：同同一一条条对对角角线线上上的的元元素素的的行行列列号号之之差差相相等等 71置当前行为第置当前行为第1行，当前列为第行，当前列为第1列，即列，即ij1;while i 8 do / 当前行号当前行号 8检查当前行：从当前列检查当前行：从当前列j起向后逐列试探，寻找安全列号；起向后逐列试探，寻找安全列号；if 找到安全列号找到安全列号 then 放置皇后，将列号记

48、入栈，并将下一行置为当前行放置皇后，将列号记入栈，并将下一行置为当前行(i+); j1; /当前列置为当前列置为1 else 退栈回溯到上一行，即退栈回溯到上一行，即i-； 移去该行已放置的皇后，以该皇后所在列的下一列作为当移去该行已放置的皇后，以该皇后所在列的下一列作为当 前列；前列；4.1 8后问题后问题72724.1 8后问题后问题2.Las Vegas方法方法v向量向量try1.8中存放结果中存放结果tryi表示第表示第i个皇后放在（个皇后放在（i，tryi)位置上位置上vtry1.k称为称为k-promising是指：是指：若若k个皇后的位置个皇后的位置(0k 8): (1,try1

49、), (2,try2), , (k,tryk)互相不攻击，则称互相不攻击，则称try1.k是是k-promising的的.形式化：对形式化：对 ，若，若 有有 (式式1)若式若式1成立，则：成立，则： 无行冲突：无行冲突：无须考虑，因为第无须考虑，因为第i个皇后放在第个皇后放在第i行，故行，故同一行不会有两皇后同一行不会有两皇后,1, i jkijtryi-tryj i-j,0,j-i73734.1 8后问题后问题 无列冲突：无列冲突：若对任意不同的两行若对任意不同的两行i、j，因为其列数，因为其列数之差不为之差不为0，故任意两皇后不可能在同一列上。，故任意两皇后不可能在同一列上。 135对角

50、线无冲突：对角线无冲突： 和和 冲突时有：冲突时有： 即即 故任两皇后不会在故任两皇后不会在135对角线上冲突。对角线上冲突。 45对角线无冲突：对角线无冲突： 和和 冲突时有：冲突时有：即即tryi-tryj=i-j故任两皇后不会在故任两皇后不会在45对角线上冲突。对角线上冲突。综上所述，式综上所述，式1成立时成立时try1.k是是k-promising。显然，若显然，若k 1，则向量，则向量try1.k是是k-promising的，对的，对8后问题，解是后问题，解是8-promising的。的。v 算法算法, i try ia i try ijtry j , j try ja try it

51、ry jji, i try ia, j try ja i try ij try j 7474 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

52、 i 1 to 8 do /i是列号是列号 if (i col) and (i-k-1 diag45) and (i+k+1 diag135) then /列列i对（对（k+1）th皇后可用，但不一定马上将其放在第皇后可用，但不一定马上将其放在第i列列 nb nb+1； if uniform(1.nb)=1 then /或许放在第或许放在第i列列 j i；/注意第一次注意第一次uniform一定返回一定返回1，即，即j一定有值一定有值1 /endif /endfor，在在nb个安全的位置上随机选择个安全的位置上随机选择1个位置个位置j放置之放置之75754.1 8后问题后问题if(nb 0)

53、then /nb=0时无安全位置，第时无安全位置，第k+1个皇后尚未放好个皇后尚未放好/在所有在所有nb个安全位置上，个安全位置上，(k+1)th皇后选择位置皇后选择位置j的概率为的概率为1/nb kk+1；/try1.k+1是是(k+1)-promising tryk j；/放置放置(k+1)th个皇后个皇后 col col j ； diag45 diag45 j-k ； diag135 diag135 j+k ； /endif until （nb=0）or（k=8）；）；/当前皇后找不到合适的位置或当前皇后找不到合适的位置或try是是 / 8-promising时结束。时结束。 succe

54、ss （nb0）；）；76764.1 8后问题后问题v 分析分析设设p是成功的概率（一次成功）是成功的概率（一次成功） s：成功时搜索的结点的平均数：成功时搜索的结点的平均数(1个皇后放好算是搜索树上的个皇后放好算是搜索树上的1个结点个结点) e：失败时搜索的结点的平均数。：失败时搜索的结点的平均数。显然显然s=9（空向量（空向量try算在内）算在内）, p和和e理论上难于计算，但实验用计算机可以计算出：理论上难于计算，但实验用计算机可以计算出：p=0.1293e=6.971在重复上述算法，直至成功时在重复上述算法，直至成功时(相当于相当于obstinate的时间），所搜索的的时间），所搜索的

55、平均结点数：平均结点数：大大优于回溯法，回溯法约为大大优于回溯法，回溯法约为114个结点才能求出一个解。个结点才能求出一个解。Ex.证明：当放置（证明：当放置（k+1)th皇后时，若有多个位置是开放的皇后时，若有多个位置是开放的,则算法则算法QueensLV选中其中任一位置的概率相等。选中其中任一位置的概率相等。(1) /55.927.tsp e p 77774.1 8后问题后问题v 问题及改进问题及改进 消极：消极：LV算法过于消极，一旦失败，从头再来算法过于消极，一旦失败，从头再来 乐观：乐观：回溯法过于乐观，一旦放置某个皇后失败，就进回溯法过于乐观，一旦放置某个皇后失败，就进行系统回退一

56、步的策略，而这一步往往不一定有效。行系统回退一步的策略，而这一步往往不一定有效。 折中：折中：会更好吗？一般情况下为此。会更好吗？一般情况下为此。先用先用LV方法随机地放置前若干个结点，例如方法随机地放置前若干个结点，例如k个。个。然后使用回溯法放置后若干个结点，但不考虑重放前然后使用回溯法放置后若干个结点，但不考虑重放前k个结个结点。点。若前面的随机选择位置不好，可能使得后面的位置不成功，若前面的随机选择位置不好，可能使得后面的位置不成功，如若前两个皇后的位置是如若前两个皇后的位置是1、3。随机放置的皇后越多，则后续回溯阶段的平均时间就越少，随机放置的皇后越多，则后续回溯阶段的平均时间就越少

57、，失败的概率也就越大。失败的概率也就越大。78784.1 8后问题后问题改进算法改进算法 折中算法只需将折中算法只需将QueensLV的最后两行改为：的最后两行改为：until nb = 0 or k = stepVegas；if （nb0)then /已随机放好已随机放好stopVegas个皇后个皇后 backtrace (k, col, diag45, diag135,success);else success false；stepVegas控制随机放置皇后的个数，如何选择？控制随机放置皇后的个数，如何选择？ 改进算法的试验结果：改进算法的试验结果：7979纯回溯时间：纯回溯时间：40ms

58、stepVegas=2 or 3：10ms（平均）（平均）纯贪心纯贪心LV：23ms（平均）（平均）结论：一半略少的皇后随机放置较好。结论：一半略少的皇后随机放置较好。StepVegasStepVegasp ps se et t0 01 11141141141141 11 139.6339.6339.6339.632 20.8750.87522.5322.5339.6739.6728.2028.203 30.49310.493113.4813.4815.1015.1029.0129.014 40.26180.261810.3110.318.798.7935.1035.105 50.16240.

59、16249.339.337.297.2946.9246.926 60.13570.13579.059.056.986.9853.5053.507 70.12930.12939 96.976.9755.9355.938 80.12930.12939 96.976.9753.9353.93搜索的平均节点数完全回溯完全随机80804.1 8后问题后问题-问题1：为什么仅随机放一个皇后，其效果就会大大优于纯回溯方法？81814.1 8后问题后问题-问题2：预先随机选几个皇后放置为好？由于解缺乏规律性（至少在皇后数不等于4k+2，k为某整数时），故求出stepVegas的最优值较难，但是找到一个较好（不

60、一定是最优）的stepVegas还是可以的。12皇后：StepVegasStepVegasp ps se et t时间时间0 01 1262262262262125ms125ms5 50.50390.503933.8833.8847.2347.2380.3980.3937ms37ms12120.04650.0465131310.210.2222.11222.11基本与纯回溯相同基本与纯回溯相同82824.1 8后问题后问题在在Apple II机器上，机器上，20个皇后：个皇后： 确定性的回溯算法：找到第一个解的时间大于确定性的回溯算法：找到第一个解的时间大于2个个小时。小时。 概率算法，随机地