[科普中國(guó)]-分布式選擇算法

概念

分布式選擇算法是由通信鏈接的多個(gè)場(chǎng)點(diǎn)或節(jié)點(diǎn)協(xié)同完成某項(xiàng)任務(wù)的算法。在分布式選擇算法中，假定記錄元素都是分布在若干場(chǎng)點(diǎn)的局部存儲(chǔ)器中，各場(chǎng)點(diǎn)間可以任意形式的互聯(lián)網(wǎng)絡(luò)連接。一組進(jìn)程的通信都經(jīng)由固定的一組交換信息的通道C。通道的雙方都約定在一個(gè)發(fā)送、另一個(gè)接收的規(guī)程上。令是一通信網(wǎng)絡(luò)，其中是一組進(jìn)程，是一組通道，輸入數(shù)據(jù)分布在各個(gè)進(jìn)程中，因此分布式算法就是相對(duì)于和對(duì)問題的求解。

通常所稱的選擇算法有兩種，一是隨機(jī)選擇1，二是確定選擇算法。前者平均復(fù)雜度為線性的，最壞復(fù)雜度為二次的；后者最壞復(fù)雜度為線性的。此兩種算法具有很多共同之處，差別僅在于劃分元素的選取方式不同，一個(gè)是隨機(jī)選取，另一個(gè)是按某一確定方式選取，從而分別名為隨機(jī)選擇和確定選擇。

工作原理隨機(jī)k-選擇算法**（1）順序隨機(jī)k-選擇算法**

令是元素的集合，欲從中選取第k個(gè)元素，則隨機(jī)k-選擇算法可描述如下：

1、如果|B|=1，則返回此元素；否則執(zhí)行以下各步；

2、隨機(jī)從B中挑選一個(gè)元素m（以下稱其為劃分元素）；

3、將B劃分成是三個(gè)子集BL，BE，BG，它們分別包含的那些元素。

4、遞歸調(diào)用本算法，以求出B'中的第k'個(gè)元素。

（2）分布式隨機(jī)k-選擇算法

Shrira等人于1983年曾將上述順序隨機(jī)k-選擇算法轉(zhuǎn)換成為分布式隨機(jī)k-選擇算法。另是元素集合，是場(chǎng)點(diǎn)集合可直截了當(dāng)?shù)剞D(zhuǎn)換成分布式算法，對(duì)于遞歸部分只要由根節(jié)點(diǎn)協(xié)調(diào)好遞歸的入口和出口即可。

確定k-選擇算法**（1）順序確定k-選擇算法**

1、如果|B|比較小（例如不大于50個(gè)元素），則可使用排序的方法求得第k個(gè)元素；否則執(zhí)行以下各步；

2、將B按5個(gè)一組進(jìn)行分組（至多有一組包含少于5個(gè)元素，稱此組為零頭）；

3、采用排序法求每組的中值，從而形成中值集合M；

4、自身遞歸調(diào)用，求集合M之中值m。

（2）分布式確定k-選擇算法

協(xié)調(diào)遞歸的入口和出口均在根部完成。根節(jié)點(diǎn)分布計(jì)算現(xiàn)有的活躍元素，如果所剩的不多，則根節(jié)點(diǎn)通知所有其他進(jìn)程將這些元素發(fā)送至根節(jié)點(diǎn)，然后由其求出第k個(gè)元素；如果仍有很多活躍元素，則根節(jié)點(diǎn)通知所有其他進(jìn)程，于是它們都遞歸地調(diào)用局部的程序。1