MPI程序設(shè)計(jì)ch18

1、 Parallel Algorithms Chapter 18 Randomized Algorithms2022/7/16主要內(nèi)容18.1 引言 - 基本知識(shí) - 時(shí)間復(fù)雜性度量 - 設(shè)計(jì)方法18.2 低度頂點(diǎn)部分獨(dú)立集 - 串行算法 - 隨機(jī)并行算法18.5 多項(xiàng)式恒等的驗(yàn)證 - 基本技術(shù) - 矩陣乘積的驗(yàn)證2022/7/1618.1 引言18.1.1 基本知識(shí) 1.隨機(jī)算法的定義 - 定義: 是一個(gè)概率圖靈機(jī). 也就是在算法中引入隨機(jī)因素, 即通過(guò)隨機(jī)數(shù)選擇算法的下一步操作. - 三要素: 輸入實(shí)例、隨機(jī)源和停止準(zhǔn)則. - 特點(diǎn): 簡(jiǎn)單、快速和易于并行化. - 一種平衡: 隨機(jī)算法可以理

2、解為在時(shí)間、空間和隨機(jī)三大 計(jì)算資源中的平衡(Lu C.J. PhD Thesis 1999). - 重要文獻(xiàn) Motwani R. and Raghavan P., Randomized Algorithms. Cambridge University Press, New York, 19952022/7/1618.1 引言18.1.1 基本知識(shí) 2.背景和歷史 (1)重要方法 - Monte Carlo求定積分法 - 隨機(jī)k-選擇算法 - 隨機(jī)快排序 -素性判定的隨機(jī)算法 - 二階段隨機(jī)路由算法 (2)重要人物和工作 - de Leeuw等人提出了概率圖靈機(jī)(1955) - John G

3、ill的隨機(jī)算法復(fù)雜性理論(1977) - Rabin的數(shù)論和計(jì)算幾何領(lǐng)域的工作(1976) - Karp的算法概率分析方法(1985) - Shor的素因子分解量子算法(1994)2022/7/1618.1 引言18.1.1 基本知識(shí) 3.隨機(jī)算法的分類(lèi) - Las Vegas算法和Monte Carlo算法是常見(jiàn)的兩類(lèi)隨機(jī)算法。 - Las Vegas算法運(yùn)行結(jié)束時(shí)總能給出正確的解，但其運(yùn)行時(shí) 間每次有所不同。 - Monte Carlo算法可能得到不正確的結(jié)果，但這種概率是小 的且有界的。 2022/7/1618.1 引言18.1.1 基本知識(shí) 4.研究意義 - 求解問(wèn)題的一種重要讓步策

4、略 - 有效的隨機(jī)算法 - 實(shí)際可行的隨機(jī)算法 - 可轉(zhuǎn)化為確定算法 - 易于并行化 - 促進(jìn)智能計(jì)算的發(fā)展2022/7/1618.1 引言18.1.2 時(shí)間復(fù)雜性度量 1.運(yùn)行時(shí)間的期望和方差 (1)實(shí)例的運(yùn)行時(shí)間期望 對(duì)固定實(shí)例x, 設(shè)隨機(jī)算法A的運(yùn)行時(shí)間 是一個(gè)0,+)上的隨機(jī)變量, 定義隨機(jī)算法A在實(shí)例x上的運(yùn)行時(shí)間期望為 , 也稱(chēng)為隨機(jī)算法A在實(shí) 例x上的執(zhí)行時(shí)間. (2)算法的運(yùn)行時(shí)間期望 如果對(duì)一個(gè)規(guī)模為n問(wèn)題的所有實(shí)例是均勻選取的, 則定義各個(gè)實(shí)例上 的平均執(zhí)行時(shí)間為隨機(jī)算法在該問(wèn)題上的運(yùn)行時(shí)間期望, 記為T(mén)(n) 注: 類(lèi)似地可以定義方差. 2.隨機(jī)復(fù)雜度類(lèi)(參見(jiàn)Motwan

5、i R. and Raghavan P., Randomized Algorithms.) RP(Randomized Polynomial time), ZPP, PP, BPP etc.2022/7/1618.1 引言18.1.3 隨機(jī)算法的設(shè)計(jì)方法 1.挫敗對(duì)手(Foiling the Adversary) 將不同的算法組成算法群, 根據(jù)輸入實(shí)例的不同隨機(jī)地或有選擇地選取 不同的算法, 以使性能達(dá)到最佳. 2.隨機(jī)采樣(Random Sampling) 用“小”樣本群的信息, 指導(dǎo)整體的求解. 3.隨機(jī)搜索(Random Search) 是一種簡(jiǎn)單易行的方法, 可以從統(tǒng)計(jì)角度分析算法的平

6、均性能, 如果將搜 索限制在有解或有較多解的區(qū)域, 可以大大提到搜索的成功概率. 4.指紋技術(shù)(Fingerprinting) 利用指紋信息可以大大減少對(duì)象識(shí)別的工作量. 通過(guò)隨機(jī)映射的取指方 法, Karp和Rabin得到了一個(gè)快速的串匹配隨機(jī)算法. 5.輸入隨機(jī)重組(Input Randomization) 對(duì)輸入實(shí)例進(jìn)行隨機(jī)重組之后, 可以改進(jìn)算法的平均性能. 2022/7/1618.1 引言18.1.3 隨機(jī)算法的設(shè)計(jì)方法 6.負(fù)載平衡(Load Balancing) 在并行與分布計(jì)算、網(wǎng)絡(luò)通訊等問(wèn)題中, 使用隨機(jī)選擇技術(shù)可以達(dá)到任 務(wù)的負(fù)載平衡和網(wǎng)絡(luò)通訊的平衡. 7.快速混合Mark

7、ov鏈(Rapidly Mixing Markov Chain) 使用該方法可以解決大空間中的均勻抽樣問(wèn)題. 8.孤立和破對(duì)稱(chēng)技術(shù)(Isolation and Symmetry Breaking) 使用該技術(shù)可以解決處理的并行性, 避免分布式系統(tǒng)的死鎖等問(wèn)題. 如: 圖著色算法, 部分獨(dú)立集問(wèn)題 9.概率存在性證明(Probabilistic Methods and Existence Proofs) 如果隨機(jī)選取的物體具有某種特性的概率大于0, 則具有該特性的物體一 定存在. 10.消除隨機(jī)性(Derandomization) 許多優(yōu)秀的確定性算法是由隨機(jī)算法轉(zhuǎn)換而來(lái)的.2022/7/161

8、8.1 引言18.1.4 隨機(jī)算法舉例: Quick Sort, Min Cut 1. Quick Sort(1)傳統(tǒng)的快排序算法 -總是取第一個(gè)元素作為劃分元； -算法的最壞運(yùn)行時(shí)間是O(n2) ，平均時(shí)間是O(nlogn) ； -因此存在一些輸入實(shí)例，使得算法達(dá)到最壞運(yùn)行時(shí)間， 如：降序的序列；(2)隨機(jī)快排序算法 -隨機(jī)選擇一個(gè)元素作為劃分元； -任何一個(gè)輸入的期望時(shí)間是O(nlogn)； -是一個(gè)Las Vegas算法； 2022/7/1618.1 引言 2. Min Cut(1)最小截問(wèn)題定義： 給定一個(gè)無(wú)向圖G(V,E)，找一個(gè)截(V1,V2)使得V1和V2間的連邊數(shù)最小。(2)該

9、問(wèn)題可以用確定性算法（max-flow min-cut algorithm）在O(n2) 時(shí)間內(nèi)完成。(3)隨機(jī)算法 隨機(jī)選一條邊，將兩頂點(diǎn)合一并除去頂點(diǎn)上的環(huán)； 直到圖中只剩下兩個(gè)頂點(diǎn)； 返回剩下兩頂點(diǎn)間的連邊數(shù)； (4)示例：#cut=2 15423541, 234, 51, 234, 51, 2, 32022/7/1618.1 引言 2. Min Cut(5)出錯(cuò)概率 重復(fù)k次出錯(cuò)概率為(6)本算法是一個(gè)Monte Carlo型算法.2022/7/1618.1 引言18.1.5 相關(guān)概率知識(shí) - 數(shù)學(xué)期望和方差 - Markov和Chebyshev不等式 - Chernoff不等式 設(shè)X

10、i是n個(gè)獨(dú)立的Bernoulli隨機(jī)變量, 對(duì)于1in, EXi=pi, 0pi1, 2022/7/16主要內(nèi)容18.1 引言 - 基本知識(shí) - 時(shí)間復(fù)雜性度量 - 設(shè)計(jì)方法18.2 低度頂點(diǎn)部分獨(dú)立集 - 串行算法 - 隨機(jī)并行算法18.5 多項(xiàng)式恒等的驗(yàn)證 - 基本技術(shù) - 矩陣乘積的驗(yàn)證2022/7/1618.2 低度頂點(diǎn)部分獨(dú)立集18.2.1 串行算法 1.問(wèn)題定義: 設(shè)G(V,E)是一個(gè)平面圖. 頂點(diǎn)集合稱(chēng)為低度頂點(diǎn)部分獨(dú)立集, 滿(mǎn)足以下三個(gè)條件: (1)對(duì) , deg(v)d常數(shù); (2)集合X獨(dú)立，即X中的任何兩頂點(diǎn)都不相鄰; (3)X的大小滿(mǎn)足|X|c|v|，c為某個(gè)正常數(shù).

11、2.引理18.1: 設(shè)G(V,E)是一個(gè)至少有三個(gè)頂點(diǎn)的平面圖, 則|E|3|V|-6. 3.串行算法 - 定理18.6 對(duì)任何平面圖G(V,E), 可以在線(xiàn)性時(shí)間內(nèi)構(gòu)造出低度頂點(diǎn)部 分獨(dú)立集. - 算法: 取 , d=6; 由Vd構(gòu)造獨(dú)立集: 反復(fù)取 加入到X中, 每次移去Vd中與v相連 的頂點(diǎn), 直至Vd空; X就是所求;2022/7/1618.2 低度頂點(diǎn)部分獨(dú)立集18.2.2 并行算法 1.算法描述(算法18.2) 輸入: 平面圖G(V,E)的邊表 輸出: 低度頂點(diǎn)獨(dú)立集X=vV| label(v)=1 begin (1)Par-do: 標(biāo)出低度頂點(diǎn)Vd(deg(v)=6); (2)P

12、ar-do: 隨機(jī)等概率分配所有vVd以標(biāo)號(hào)0或1; /破對(duì)稱(chēng)技術(shù) (3)Par-do: 剔除不滿(mǎn)足獨(dú)立性的標(biāo)號(hào)為1的頂點(diǎn); (4)剩下的標(biāo)號(hào)為1的低度頂點(diǎn)集就是所求的X; end 2022/7/1618.2 低度頂點(diǎn)部分獨(dú)立集18.2.2 并行算法 2.算法分析 (1)算法的正確性 定理18.7 算法18.2產(chǎn)生的X=vV| label(v)=1就是一個(gè)低度頂點(diǎn)集, 使得 Pr|X|ne-n, 其中和為常數(shù), n是頂點(diǎn)數(shù). 證: 我們知道算法18.2產(chǎn)生的X滿(mǎn)足低度頂點(diǎn)集的前兩個(gè)條件, 現(xiàn)在只要證明 條件3高概率成立, 即Pr|X|ne-n, 其中和為常數(shù), n是頂點(diǎn)數(shù). 考慮一個(gè)特殊的低度

13、頂點(diǎn)子集VV6, 這里V中的任意兩頂點(diǎn)之間的距 離至少為3, 下面只要證明|VX|以高概率滿(mǎn)足條件3. V這樣構(gòu)造: 先任取v1V6, 刪去V6中與v1距離小于2的頂點(diǎn), 可知至多 刪去36個(gè)頂點(diǎn), 再?gòu)腣6的剩余頂點(diǎn)中任取v2, 刪去V6中與v2距離小于2的頂點(diǎn), 可知至多刪去36個(gè)頂點(diǎn), 直至V6為空. V=v1,v2,. 因此, |V|(1/37)|V6|(1/37)(n/7)=cn c=1/259 (|Vd|c0|V|, c0=(d-5)/(d+1) 2022/7/1618.2 低度頂點(diǎn)部分獨(dú)立集18.2.2 并行算法 2.算法分析 (1)算法的正確性 定理18.7的證明(續(xù)): 由于

14、V中頂點(diǎn)的距離至少大于等于3, 可知隨機(jī)變量Xi相互獨(dú)立. 從X的生成過(guò)程知: EXi=PrviX(1/2)7 至此證明了條件3高概率成立. (2)算法時(shí)間: O(1), 使用了O(n)次運(yùn)算.2022/7/16主要內(nèi)容18.1 引言 - 基本知識(shí) - 時(shí)間復(fù)雜性度量 - 設(shè)計(jì)方法18.2 低度頂點(diǎn)部分獨(dú)立集 - 串行算法 - 隨機(jī)并行算法18.5 多項(xiàng)式恒等的驗(yàn)證 - 基本技術(shù) - 矩陣乘積的驗(yàn)證2022/7/1618.5 多項(xiàng)式恒等的驗(yàn)證18.5.1基本技術(shù) 1.原理 - 定理18.13 設(shè)p(x1,x2,xn)是域F上的多項(xiàng)式, 且p(x1,x2,xn)非恒等零, 若I是F的任意有限子集

15、, 則In中有p(x1,x2,xn)的零元素?cái)?shù)目|I|n-1deg(p), 其中deg(p)是多項(xiàng)式的階. - 系18.3 令p(x1,x2,xn)0, 則隨機(jī)元組(y1,y2,yn)In是p(x1,x2,xn)的 零元素的概率deg(p)/|I|. 2.測(cè)試多項(xiàng)式p(x1,x2,xn)是否恒為零的方法 先選擇有限子集IF, 使|I|2deg(p); 隨機(jī)選擇vIn, 計(jì)算p(x1,x2,xn)|v; 如果p(x1,x2,xn)|v為零, 則p0;否則p不恒為零; 注: 該方法的錯(cuò)誤概率1/2, 重復(fù)k次的錯(cuò)誤概率(1/2)k2022/7/1618.5 多項(xiàng)式恒等的驗(yàn)證18.5.2 矩陣乘積的驗(yàn)證 1.問(wèn)題: AnnBnn=Cnn ? 2.確定并行算法: 需要O(logn)時(shí)間, 進(jìn)行了n3次乘積, 如DNS算法; 3.隨機(jī)并行算法 (1)原理 - 引理18.7 設(shè)u為域F上的n維非零向量, 隨機(jī)選擇v0,1n, 則 i=1nuivi=0的概率1/2 - 定理18.14 隨機(jī)產(chǎn)生v0,1n, 如果A(Bv)=Cv, 則AB=C; 否則ABC; 出錯(cuò)的概率至多為1/2. 證: 當(dāng)AB=C時(shí), 結(jié)論總是正確的; 當(dāng)ABC時(shí), 存在下標(biāo)j, 使AB和C的第j行是不同的. 設(shè)u