算法分析與設計課件：隨機算法

1、隨機算法 2021-9-222 of 158l定義：在算法中引入隨機因素, 即通過隨機數(shù)選擇算法的下一步操作。特點：簡單、快速一種平衡：隨機算法可以理解為在時間、空間和隨機三大計算資源中的平衡2021-9-223 of 158計算機產(chǎn)生隨機數(shù)的方法 d0=d dn=bdn-1+c an= dn % 655362021-9-224 of 1581、數(shù)值概率算法：用于數(shù)值問題的求解2、Sherwood算法一定能得到問題的正確解常見的四類隨機算法：2021-9-225 of 1583、Las Vegas算法或者得到正確的解，或者得不到解。 4、Monte Carlo算法一定能得到解，但是得到的解可能

2、不正確，然而這種概率是小的且有界的。常見的四類隨機算法：2021-9-226 of 158一種重要讓步策略： 傳統(tǒng)算法傳統(tǒng)算法: 以以100成功概率求解成功概率求解 確定的確定的 問題的最優(yōu)解問題的最優(yōu)解 近似算法近似算法: 一種對解質(zhì)量的讓步一種對解質(zhì)量的讓步算法算法 隨機算法隨機算法: 一種對求解成功概率和一種對求解成功概率和 非確定的非確定的 解質(zhì)量的讓步解質(zhì)量的讓步 智能算法智能算法: 遺傳算法、模擬退火法、遺傳算法、模擬退火法、 擬人擬物算法等擬人擬物算法等2021-9-227 of 158設有一半徑為設有一半徑為r的圓及其外切四邊形。向該正方形隨機地投擲的圓及其外切四邊形。向該正方

3、形隨機地投擲n個個點。設落入圓內(nèi)的點數(shù)為點。設落入圓內(nèi)的點數(shù)為k。由于所投入的點在正方形上均勻分布，。由于所投入的點在正方形上均勻分布，因而所投入的點落入圓內(nèi)的概率為因而所投入的點落入圓內(nèi)的概率為 。所以當。所以當n足夠大足夠大時，時，k與與n之比就逼近這一概率。從而之比就逼近這一概率。從而 。4422rrnk4double darts(int n) / 用隨機投點法計算值 int k=0; for (int i=1;i =n;i+) double x=Random(); double y=Random(); if (x*x+y*y)1是一個整數(shù)。關于整數(shù)n的因子分解問題是找出n的如下形式的惟

4、一分解式：其中，p1p2pk是k個素數(shù)，m1,m2,mk是k個正整數(shù)。如果n是一個合數(shù)，則n必有一個非平凡因子x，1xn，使得x可以整除n。給定一個合數(shù)n，求n的一個非平凡因子的問題稱為整數(shù)n的因子分割問題。kmkmmpppn2121int split(int n) int m = sqrt(double)n); for (int i=2; i=m; i+) if (n%i=0) return i; return 1; 事實上，算法split(n)是對范圍在1x的所有整數(shù)進行了試除而得到范圍在1x2的任一整數(shù)的因子分割。 2021-9-2213 of 158在開始時選取0n-1范圍內(nèi)的隨機數(shù)，

5、然后遞歸地由產(chǎn)生無窮序列對于i=2k，以及2kj2k+1，算法計算出xj-xi與n的最大公因子d=gcd(xj-xi，n)。如果d是n的非平凡因子，則實現(xiàn)對n的一次分割，算法輸出n的因子d。nxxiimod) 1(21,21kxxxvoid pollard(int n) / 求整數(shù)n因子分割的拉斯維加斯算法 int i=1,k=2; int x=random(1, n); y=x; / 隨機整數(shù) while (i1) & (dn/2時，稱元素x為數(shù)組T的主元素。l majority(int t,int n) 隨機產(chǎn)生整數(shù)i； int x=ti; int k=0; for(int j=1;jn/

6、2); 2021-9-2215 of 158主元素問題lmajority2返回true的概率是p+(1-p)p=1-(1-p)23/4l majority2(int t,int n) if (majority(t,n) return true;else return majority(t,n); 2021-9-2216 of 158主元素問題2021-9-2217 of 158l最小截問題定義： 給定一個無向圖G(V,E)，找一個截(V1,V2)使得V1和V2間的連邊數(shù)最小。2021-9-2218 of 158l隨機算法 隨機選一條邊，將兩頂點合一并除去頂點上的環(huán)； 直到圖中只剩下兩個頂點；

7、返回剩下兩頂點間的連邊數(shù)；l重復版本 重復執(zhí)行算法k次，取返回連邊數(shù)最小數(shù)作為解。2021-9-2219 of 158l示例：#cut=215423541, 234, 51, 234, 51, 2, 3l出錯概率 重復k次出錯概率為)1(2) 1(21nnkkenn本算法是一個本算法是一個Monte Carlo型算法型算法2021-9-2220 of 158l 素數(shù)測試素數(shù)測試定理定理1 1 FermatFermat小定理小定理 如果如果n n為素數(shù)，則對所有小于為素數(shù)，則對所有小于n n的正整數(shù)的正整數(shù)a a有有 a an-1n-1 1(mod n)1(mod n)檢測檢測2 2n-1n-1

8、 1(mod n)1(mod n)。是，輸出。是，輸出“素數(shù)素數(shù)”；否則輸出；否則輸出“合數(shù)合數(shù)”。2021-9-2221 of 158算法算法Ptest1(n)Ptest1(n)輸入：奇整數(shù)輸入：奇整數(shù)n,n5n,n5輸出：輸出： “ “prime” prime” 或者或者 “ “composite” composite” 1. if ExpMod(2,n-1,n) =1 then return prime1. if ExpMod(2,n-1,n) =1 then return prime2. else return composite 2. else return composite 算法

9、算法Ptest1Ptest1只對只對a=2a=2進行測試進行測試, ,如果如果n n為合數(shù)且為合數(shù)且Ptest1Ptest1輸出為輸出為“素數(shù)素數(shù)”，則稱，則稱n n為基為基2 2偽素數(shù)。偽素數(shù)。 341341滿足上述條件，但是滿足上述條件，但是341341是合數(shù)是合數(shù). .2021-9-2222 of 158改進方法是隨機選取改進方法是隨機選取2-n-22-n-2中的數(shù)做為中的數(shù)做為a a，再進行測試，再進行測試. . 取取a=3a=3，3 3340340(mod 341)(mod 341) 5656，341341不是素數(shù)不是素數(shù). . 算法算法Ptest2(n)Ptest2(n) 1. a

10、 1. aRandom(2,n-2)Random(2,n-2) 2. if Expmod(a,n-1,n)=1 then return prime 2. if Expmod(a,n-1,n)=1 then return prime 3. else return composite 3. else return composite2021-9-2223 of 158對所有與對所有與n n互素的正整數(shù)互素的正整數(shù)a a，都滿足上述條件的，都滿足上述條件的合數(shù)合數(shù)n n稱為稱為Carmichael Carmichael 數(shù)，如數(shù)，如561561，11051105，17291729，24652465等

11、。等。CarmichaelCarmichael數(shù)非常少，小于數(shù)非常少，小于10108 8的只有的只有255255個。個。 如果如果n n為合數(shù)，但不是為合數(shù)，但不是CarmichaelCarmichael數(shù)，算法數(shù)，算法Ptest2 Ptest2 測試測試n n為合數(shù)的概率至少為為合數(shù)的概率至少為1/2. 1/2. 但是這但是這個算法不能解決個算法不能解決 CarmichaelCarmichael數(shù)的問題。數(shù)的問題。2021-9-2224 of 158定理定理2 2 如果如果n n為素數(shù)，則方程為素數(shù)，則方程x x2 2 1(mod n)1(mod n)的的根只有兩個，即根只有兩個，即x=1x

12、=1，x=-1x=-1（或（或x=n-1x=n-1）。）。證明證明 x x2 2(mod n)(mod n) 1 1 x x2 2-1-1 0(modn)0(modn) (x+1)(x-1) (x+1)(x-1) 0(modn)0(modn) x+1 x+1 0 0或或 x-1x-1 0 0 x=n-1 x=n-1或或 x=x=1 12021-9-2225 of 158稱稱x x1 1的根為非平凡的。根據(jù)定理的根為非平凡的。根據(jù)定理2 2，如果方程，如果方程有非平凡的根，則有非平凡的根，則n n為合數(shù)。例如為合數(shù)。例如: : x x2 2(mod 5)(mod 5) 1 1 x=1 x=1或或

13、x=4x=4 x x2 2(mod 12)(mod 12) 1 1 x=1 x=1 或或x=11x=11或或x=5x=5或或x=7x=75 5和和7 7是非平凡的根。是非平凡的根。設設n n為素數(shù)，存在為素數(shù)，存在q,mq,m使得使得n-1=2n-1=2q qm, (qm, (q 1)1)。序列。序列 )(mod),.,(mod),(mod),(mod242nanananammmmq的最后一項為的最后一項為a an-1n-1(mod n), (mod n), 而且每一項是前面一項的而且每一項是前面一項的平方。對于任意平方。對于任意k k（k=0,1,k=0,1,q-1q-1）, , 判斷判斷)(mod2namk是否為是否為1 1和和n-1n-12021-9-2226 of 158Instant Insanity游戲游戲 針對的是四個立方體。立方體針對的是四個立方體。立方體六個面中的每一個都涂有紅六個面中的每一個都涂有紅(R)(