MPI程序設計ch18

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

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

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

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

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

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

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

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

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

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

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

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

13、頂點子集VV6, 這里V中的任意兩頂點之間的距 離至少為3, 下面只要證明|VX|以高概率滿足條件3. V這樣構(gòu)造: 先任取v1V6, 刪去V6中與v1距離小于2的頂點, 可知至多 刪去36個頂點, 再從V6的剩余頂點中任取v2, 刪去V6中與v2距離小于2的頂點, 可知至多刪去36個頂點, 直至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 低度頂點部分獨立集18.2.2 并行算法 2.算法分析 (1)算法的正確性 定理18.7的證明(續(xù)): 由于

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

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