随机算法.doc

1、Randomized Algorithms (随机算法) Probabilistic Algorithms (概率算法)起源可以追溯到 20 世纪 40 年代中叶。当时 Monte Carlo 在进行数值计算时，提出通过统计模拟或抽样得到问题的近似解，而且出现错误的概率随着实验次数的增多而显著地减少，即可以用时间/次数来换取求解正确性的提高。不过，Monte Carlo 方法很长时间没有引入到非数值算法中来。74 年，Michael Rabin（76 年 Turing 奖获得者, 哈佛教授, 以色列人）在瑞典讲演时指出：有些问题，如果不用随机化的方法而用确定性的算法，在可以忍受的时间内得不到所

2、需要的结果。e.g. Presburge 算术系统（其中只有加法）中的计算程序，即使只有 100 个符号，用每秒 1 万亿次运算的机器 1 万亿台、进行并行计算也需做 1 万亿年。但如果使用随机性的概念，可以很快得出结果，而出错率则微乎其微。74 年 Rabin 关于随机化算法的思想还不太成熟，76 年 Rabin 设计了一个判定素数的随机算法，该算法至今仍是随机算法的一个典范。随机算法在分布式计算、通信、信息检索、计算几何、密码学等许多领域都有着广泛的应用。最著名的是在公开密钥体系、RSA 算法方面的应用。用随机化方法解决问题之例：设有一函数表达式 f(x1,x2,xn)，要判断 f 在某一

3、区域 D 中是否恒为 0。如果 f 不能用数学方法进行形式上的化简（这在工程中是经常出现的） ，如何判断就很麻烦。如果我们随机地产生一个 n 维的坐标(r1，r 2， r n)D，代入 f 得 f(r1，r 2， r n)0，则可断定在区域 D 内 f 不恒为 0。如果 f(r1，r 2， r n)0，则有两种可能：1. 在区域 D 内 f0；2. 在区域 D 内 f0，得到上述结果只是巧合。如果我们对很多个随机产生的坐标进行测试，结果次次均为 0，则我们可以断言：f0 的概率是非常之小的。如上例所示，在随机算法中，我们不要求算法对所有可能的输入均正确计算，只要求出现错误的可能性小到可以忽略的

4、程度；另外我们也不要求对同一输入算法每次执行时给出相同的结果。我们所关心的是算法在执行时，是否能够产生真正随机的结果。有不少问题，目前只有效率很差的确定性求解算法， 但用随机算法去求解，可以（很快地）获得相当可信的结果。随机算法通常分为两大类：Las Vegas 算法、Monte Carlo 算法。Las Vegas 算法总是给出正确的结果，但在少数应用中，可能出现求不出解的情况。此时需再次调用算法进行计算，直到获得解为止。对于此类算法，主要是分析算法的时间复杂度的期望值，以及调用一次产生失败（求不出解）的概率。Mont Carlo 算法通常不能保证计算出的结果总是正确，一般只能断定所给解的正

5、确性不小于 p（ p1） 。2通过反复执行算法（即以增大算法的执行时间为代价） ，能够使发生错误的概率小到可以忽略的程度。由于每次执行的算法是独立的，故 k 次执行均发生错误的概率小于(1-p) k。对于判定问题（回答只能是“Yes”或“No” ） ，Monte Carlo 法又分为两类：1. 带双错的（two-sided error）: 回答”Yes”或”No”都有可能错。2. 带单错的（one-sided error）：只有一种回答可能错。Las Vegas 算法可以看成是单错概率为 0 的特殊的 Monte Carlo 算法。到底哪一种随机算法好？依赖于应用。在不允许发生错误的应用中（e

6、.g. 人造飞船、电网控制等） ，Monte Carlo 算法不可以使用；若允许小概率的出错，则 Monte Carlo 算法比 Las Vegas 算法要节省许多时间，是人们常常采用的方法。随机算法的优点：1、 对于某一给定的问题，随机算法所需的时间与空间复杂性，往往比当前已知的、最好的确定性算法要好。2、 目前为止设计出来的各种随机算法，无论是从理解上还是实现上，都是极为简单的。3、 随机算法避免了去构造最坏情况的例子。最坏情况虽有可能发生，但是它不依赖于某种固定的模式，只是由于“运气不好”才出现此种情况。Random Sampling 问题（Las Vegas 算法）设给定 n 个元素（

7、为简单起见，设为 1，2，n） ，要求从 n 个数中随机地选取 m 个数（mn） 。可以用一个长为 n 的布尔数组 B 来标识 i 是否被选中，初始时均表为“未选中” 。然后随机产生1，n之间的一个整数 i，若 Bi为“未选中” ，则将 i 加入被选中队列，同时把 Bi标识为“已选中” ，反复执行直到 m 个不同的数全部被选出为止。该算法有两个问题：1、 n 和 m 很接近时(例 n1000，m960)，产生最后几个随机数的时间可能很长（有 95以上的可能性是已选中的数） 。改进：当 m 时，先去产生 n-m（ ）个随机数，22然后再取剩下的 m 个数作为选出的数。2、当 n 与 m 相比大很

8、多时（例：nm 2） ，布尔数组 B 对空间浪费很多。改进：用一个允许冲突的、长为 m 的散列表，来存放产生的随机数。产生一个数后，看其是否在散列表中：若不在则将其加入，若已在则抛弃该数，再去产生下一个数。作业：设 nm 2，用散列表以外的数据结构来代替布尔数组 B。上述随机算法的分析：设随机变量 X 表示扔硬币时，第一次碰到“正面朝上”的情况时，已经试过的次数。X=k 意味着前 k-1 次均向下，第 k 次向上。设 p 为正面朝上概率，q=1-p 为背面朝上概率，其概率表示为：PrX=k= （几何分布）101kpq（前 k-1 次均向下，第 k 次向上）按求离散期望值的方法 E(X)= =1

9、PrkX11kkpq（连续情况积分） 。令 s= ，则 s-sq= = 1kq0iiq故 s= = 。于是根据定义有 E(X)=p*s= 。2)1(qpp1（另：考虑离散与连续情况之间的关系）设 pj是这样的概率：在 j-1 个数已经选出的前提下，当前随机产生的数是以前尚未选过的数的概率，则有pj= = 。于是 qj = 1- pj = ，即 qj为：nj)1(nj1n1当前随机产生的数是以前选过的 j-1 个数之一的概率。设随机变量 Xj（1jm）表示：在 j-1 个数已经选出后，再去找出第 j 个数（与前 j-1 个数不同）时，所需要产生的整数个数。则与前述的 X 类似，X j服从几何分布

10、：PrXj=k=pjqjk-1（k1,q j=1-pj） ，于是有 E(Xj)= = 。jp11jn设 Y 表示从 n 个数中选出 m 个数时（m ） ，2n所需产生的整数个数的总和的随机变量，则有 Y=X1X 2X 3X m。由于随机变量的线性可加性有 E(Y)=E(X1)E(X 2)E(X m)= jjn1=n（ - ）njj1jj1=n（ ）-（ ） ）A2Bmn121在数学基础部分曾证明用积分法可得 1enlog)1(nj elog故有 An1 ，及 B（nm1） ，于是 E(Y)n（n + 1 - （n-m+1） ）n（n + 1 - （n-m） ） n（n + 1 - （ ） ）

11、（m ）2n= n（n + 1 - n + 2）= n2e1.69n由于算法的时间复杂度 T(n)正比于算法产生整数的个数总和 Y，所以，T(n)的数学期望值与 E(Y)成常数比，即有 T(n)=(n)（数学期望值） 。找第 k 小元素的随机算法（Las Vegas 算法）：在 n 个数中随机的找一个数 Ai=x, 然后将其余 n-1 个数与 x 比较，分别放入三个数组中：S1（元素均x）, S 2（元素均=x）, S 3（元素均x） 。 若|S 1|k 则调用 Select(k,S1)；若|S 1| k但（|S 1|+|S2|）k，则第 k 小元素就是 x；否则就有（|S 1|+|S2|）

12、k，此时调用 Select(k-|S1|-|S2|,S3)。定理：若以等概率方法在 n 个数中随机取数，则该算法用到的比较次数的期望值不超过 4n。（假定 n 个数互不相同，如果有相同的数的话，落在 S2中的可能性会更大，比较次数的期望值会更小一些。 ）证：设 C(n)是输入规模为 n 时，算法中所用到的比较次数的期望值。并设取到任一个数的概率相同。假定用上述算法取到的数 x 是第 j 小的数（j = 1，2，n） 。若 jk，则需要调用 Select(k,S1)。|S 1|= j-1（因为取到的 x 是第 j 小的数） ，调用 Select(k,S1)的比较次数的期望值为 C(j-1)。若

13、j=k，则直接返回第 j 个元素，无需继续进行比较。若 jk，则需要调用 Select(k-j,S3) （j=|S 1|+|S2|） 。|S 3| = n-j，本次调用的比较次数的期望值是 C(n-j)。由于取 j 为 1，2，n 的概率相同，故有C(n) = n+ 11)()(kjkj jnC(其中的 n 是：获得 S1, S2, S3所需比较次数)=n+ )1()1 kiCki =n+ 1)nkinki由于 C(i)是非减函数（在 ij 时，总有 C(i)C(j)，（ ） 在 k=n/2 时取得最大值。11nkinki C（证明留作作业）归纳法基础：n=1 时无需比较，显然有 C(n)4n

14、 。归纳法假设：设 nn 时，有 C(n)4n 。由于 C(n)是在 k= n/2 时取得最大值，于是有 C(n)n+1212)()(ni nic（注意式中的 均应为n/2，下同）n+ )4(112nii（由归纳法假设，nn 时，有 C(n)4n ）n+ )8(12i（n 为奇数时 n- n/2+1= n/2，故此时两和式相等）=n+ = n+ (n*(n-1)/2 - n/2*( n/2-1)/2)(1nii 8 n+ (本式中的 不向上取整)= 4n-2)2(8n2n由于每个元素至少被比较一次，所以 C(n)n，随机化 Select 算法的比较次数期望值有：nC(n) 4n。Sherwoo

15、d 随机化方法（属 Las Vegas 算法）如果某个问题已经有了一个平均性质较好的确定性算法，但是该算法在最坏情况下效率不高，此时引入一个随机数发生器（通常是服从均匀分布，根据问题需要也可以是其他的分布） ，将一个确定性算法改成一个随机算法，使得对于任何输入实例，该算法在概率意义下都有很好的性能（e.g. Select, Quicksort 等） 。如果算法（所给的确定性算法）无法直接使用 Sherwood 方法，则可以采用随机预处理的方法，使得输入对象服从均匀分布（或其他分布） ，然后再用确定性算法对其进行处理。所得效果在概率意义下与 Sherwood 型算法相同。Testing Stri

16、ng Equality（Monte Carlo 算法）设 A 处有一个长字符串 x（e.g. 长度为 106） ，B 处也有一个长字符串 y，A 将 x 发给 B，由 B 判断是否有 x=y。算法：首先由 A 发一个 x 的长度给 B，若长度不等，则 xy。若长度相等，则采用“取指纹”的方法：A 对 x 进行处理，取出 x 的“指纹” ，然后将 x 的“指纹” 发给 B，由 B 检查 x 的“指纹”是否等于 y 的“指纹” 。若取 k 次“指纹” （每次取法不同） ，每次两者结果均相同，则认为 x 与 y 是相等的。随着 k 的增大，误判率可趋于 0。常用的指纹：令 I(x)是 x 的编码，取

17、 Ip(x) I(x) (mod p)作为 x 的指纹。这里的 p 是一个小于 M 的素数，M 可根据具体需要调整，本例中取 M=2n2。由于 0Ip(x)p，Ip(x)的二进制传输长度不超过 log2 p 位。设 n 是 I(x)的二进制表示的长度，则有 I(x)2 n。由于 pM=2n 2，故有 log2plog 2(2n2)+1=O(log2n)。传输的长度可以大大的缩短。例：设 I(x)是 106位二进制的数，即 n=106，则 M=210122 40.8631Ip(x)的位数不超过 41 位，传输一次可节省约 2.5 万倍。 根据下面所做的分析，可知错判率小于 。610如果取 5 种

18、不同的 p（即 k=5）求出“指纹”再传输、检查 5 次，则传输量可节省 5,000 倍。此时错判率小于 。301错判率分析：B 接到指纹 Ip(x)后与 Ip(y)比较，如果 Ip(x)Ip(y)，当然有 xy。如果 Ip(x)=Ip(y)而 xy，则称此种情况为一个误匹配。 问题是：误匹配的概率有多大？若我们总是随机地去取一个小于 M 的素数 p，则对于给定的 x 和 y，Prfailure =（使得 Ip(x)=Ip(y)但 xy 的素数 p(pM的个数（小于 M 的素数的总个数） 。小于 M 的素数总共有多少？数论定理 1：设(n)是小于 n 的素数个数，则(n) ，nelog误差率不

19、超过 6%。例: n=500 1000 10 4 105 106 107 (n)=95 168 1229 9592 78498 664579 108 1095761445 50847478M=2n 2，Prfailure的分母(M) = = =Melog)2(lne neelog2lnelog2el2Prfailure的分子 使得 Ip(x)=Ip(y)的素数 p(pM)的个数=能够整除I(x)-I(y)的素数 p(pM)的个数（ab (mod p) iff p 整除a-b）数论定理 2：如果 a2 n， （只要 n 不是太小）则能够整除 a 的素数个数不超过(n)个。 I(x)-I(y)ma

20、xI(x),I(y)2 n-1，能够整除I(x)-I(y)的素数个数不超过(n)。而满足 pM 的素数则更少，当 n7 时，有 2n22 n。Prfailure(n) / (M) = 。nelog/21即误匹配的概率小于 。1当 n 很大时，误匹配的概率很小。设 xy，如果取 k 个不同的小于 2n2的素数来求 Ip(x)和 Ip(y)，由于具有独立性的事件同时发生的概率满足乘法原理，故 k 次试验均有 Ip(x)=Ip(y)但 xy（误匹配）的概率小于 。kn1当 n 较大、且重复了 k 次试验时，误匹配的概率趋于 0。Pattern Matching（Monte Carlo 算法）给定两个

21、字符串：X=x 1,xn，Y=y 1,ym，看 Y 是否为 X 的子串？（即 Y 是否为 X 中的一段。 ）该问题可用 KMP 算法在 O(m+n)时间里获得正确结果，（还可用 Rabin-Karp 算法、Boyer-Moore 算法等）但算法相对比较繁琐，函数计算比较复杂。考虑随机算法（用 brute-force 思想）记 X(j)=xjxj1 xj+m-1（从 X 的第 j 位开始、长度与 Y 一样的子串） ，从起始位置 j=1 开始到 j=n-m+1，算法不是去逐一比较 X(j)与 Y，而仅逐一比较 X(j)的指纹 Ip(X(j)与 Y 的指纹 Ip(Y)。由于 Ip(X(j+1)可以很

22、方便地根据 Ip(X(j)计算出来，故算法可以很快完成。不失一般性,设 xi(1in) 和 yj(1jm)0,1，即 X, Y 都是 0-1 串。Ip(X(j+1) = (xj+1xj+m)(mod p)=(2(xj+1xj+m-1)+xj+m)(mod p)=(2(xj+1xj+m-1)+2mxj-2mxj+xj+m)(mod p)=(2(xjxj+1xj+m-1)-2mxj+xj+m)(mod p)（(xy+z)(mod p)=(x(y mod p)+z)(mod p)）=(2 ( (xjxj+1xj+m-1)mod p )-2mxj+xj+m)(mod p)=(2*Ip(X(j)- xj

23、+xj+m)(mod p) ()W)od2(Ip(X(j+1)可以利用 Ip(X(j)及()式方便地计算出来。算法：1、随机取一个小于 M 的素数 p，置 j1；2、算 Ip(Y)、Ip(X(1)及 Wp(=2m mod p)；3、While jn-m+1 doif Ip(X(j)=Ip(Y) then return j /X(j)极有可能等于 Y/else使用()式计算出 Ip(X(j+1)；j 增 14、 return 0; /X 肯定没有子串等于 Y/时间复杂度：Y、X(1)、2 m均只有 m 位（二进制数） ，故计算 Ip(Y)、Ip(X(1)及 2m mod p 的时间不超过 O(m

24、)次运算。Ip(X(j+1)的计算：由于 2*Ip(X(j)只需要在 Ip(X(j)后加个 0；当 xj为 1 时，第二部分 Wp*xj就是 Wp，当 xj为 0 时该部分为 0；x j+m或为 0 或为 1，然后进行加减法（O(1)时间）就可得到2*Ip(X(j)- xj+xj+m。但此式还要对 p 取模。pm)od2(由于 02*Ip(X(j)2p-2，0 xjp-1，0x j+m1，因此Wp)(2*Ip(X(j)- xj+xj+m的值在-(p-1), 2p-1之间。pm)od2故实际计算时，若上式是负值，则加上 p 后即得 Ip(X(j+1)；若为非负，则看其是否小于 p，小于 p 则已

25、得 Ip(X(j+1)；若大于等于 p，则减去 p 后即得 Ip(X(j+1)。故 Ip(X(j+1)的计算只需用 O(1)时间。由于循环最多执行 n-m+1 次，故这部分的时间复杂度为 O(n)。于是，总的时间复杂性为 O(m+n)。失败的概率：当 YX(j)，但 Ip(Y)=Ip(X(j)时产生失败。Ip(Y)=Ip(X(j) 当且仅当 p 能整除|Y-X(j)|。当 p 能整除|Y-X(j)|时，p 当然也能整除|Y-X(1)| |Y-X(2)|Y-X(j)|Y-X(n-m+1)|（p 素数，反之也成立） ，由于|Y-X(j)|不超过 m 个二进制位，|Y-X(j)|2 m。|Y-X(1

26、)| |Y-X(2)|Y-X(n-m+1)| (2 m)n-m+12 mn。由数论定理 2(如果 a2 n，则能够整除 a 的素数个数不超过(n)个)，能整除|Y-X(1)| |Y-X(2)|Y-X(n-m+1)|的素数个数不超过(mn)个。于是Prfailure=(Y 不含在 X 中、但 p(pM)能够整除|Y-X(1)| |Y-X(2)|Y-X(j)|Y-X(n-m+1)|的素数的个数)/小于 M 的素数的个数(mn)/ (M) = (mn)/ (2mn 2) （取 M=2mn2）(mn/log e(mn)/(2mn2/loge(2mn2)= loge(2mn2)/2n loge(mn)(

27、m2 时有)log e(mn)2)/2n loge(mn)=1/n即失败的概率不会超过 X 的长度分之一。当 m=n 时，问题退化为判定两个字符串是否相等的问题。本算法可以转成 Las Vegas 算法：当 Ip(Y)=Ip(X(j)时，不直接 return j，而去比较 Y 和 X(j), 即在 return j 之前加一个判断看 Y 和 X(j)是否相等，相等则 return j ，否则继续执行循环。这样，如果有子串 X(j)与 Y 相匹配，该算法总能给出正确的位置（即算法出错的概率为 0） 。在最坏情况下算法执行 O(mn)时间，而 p 能整除|I(Y)-I(X(j)|概率的不超过 ，故

28、n1算法的时间复杂性的期望值不超过 。)(1)()(nmOmO 能 够 整 除 时不 能 整 除 时 作业：分别用 KMP、Monte Carlo 和 Las Vegas 算法编制 3 个程序，随机生成不小于 5000 对的、长度不等的 01 串 X 和 Y（三个程序生成相同的串） ，然后统计算法的执行时间、Monte Carlo 算法出错的比率，并根据运行结果对三种算法进行深入的比较。注意，先利用本题下方所给素数实现上述算法，学完素数判定算法之后，将该算法编程，产生一定数量的大素数并用数组保存起来，以供上述随机算法使用（素数判定算法写在上述随机算法之外） 。素数（每种情况给 7 个数）（250 以内 ） 211 223 227 229 233 239 241（500 以内 ）461 463 467 479 487 491 499（1000 以内）953 967 971 977 983 991 997（5000 以内）4957 4967 4969 4973 4987 4993 4999（10000 以内）9923 9929 9931 9941 9949 9967 9973（100000 以上）100003 100019 100043 100049 100057 100069 100103