[科普中国]-分布式选择算法

概念

分布式选择算法是由通信链接的多个场点或节点协同完成某项任务的算法。在分布式选择算法中，假定记录元素都是分布在若干场点的局部存储器中，各场点间可以任意形式的互联网络连接。一组进程的通信都经由固定的一组交换信息的通道C。通道的双方都约定在一个发送、另一个接收的规程上。令是一通信网络，其中是一组进程，是一组通道，输入数据分布在各个进程中，因此分布式算法就是相对于和对问题的求解。

通常所称的选择算法有两种，一是随机选择1，二是确定选择算法。前者平均复杂度为线性的，最坏复杂度为二次的；后者最坏复杂度为线性的。此两种算法具有很多共同之处，差别仅在于划分元素的选取方式不同，一个是随机选取，另一个是按某一确定方式选取，从而分别名为随机选择和确定选择。

工作原理随机k-选择算法**（1）顺序随机k-选择算法**

令是元素的集合，欲从中选取第k个元素，则随机k-选择算法可描述如下：

1、如果|B|=1，则返回此元素；否则执行以下各步；

2、随机从B中挑选一个元素m（以下称其为划分元素）；

3、将B划分成是三个子集BL，BE，BG，它们分别包含的那些元素。

4、递归调用本算法，以求出B'中的第k'个元素。

（2）分布式随机k-选择算法

Shrira等人于1983年曾将上述顺序随机k-选择算法转换成为分布式随机k-选择算法。另是元素集合，是场点集合可直截了当地转换成分布式算法，对于递归部分只要由根节点协调好递归的入口和出口即可。

确定k-选择算法**（1）顺序确定k-选择算法**

1、如果|B|比较小（例如不大于50个元素），则可使用排序的方法求得第k个元素；否则执行以下各步；

2、将B按5个一组进行分组（至多有一组包含少于5个元素，称此组为零头）；

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

4、自身递归调用，求集合M之中值m。

（2）分布式确定k-选择算法

协调递归的入口和出口均在根部完成。根节点分布计算现有的活跃元素，如果所剩的不多，则根节点通知所有其他进程将这些元素发送至根节点，然后由其求出第k个元素；如果仍有很多活跃元素，则根节点通知所有其他进程，于是它们都递归地调用局部的程序。1