单元iv 非数值并行算法mpi编程实现.pdfVIP

单元IV非数值并行算法MPI编程实现

第十三章排序

第十四章串匹配

第十五章图论

第十六章组合优化

第十七章算几何

这一单元主要介绍典型的非数值并行算法的MPI编程实现，包括排序（第十

三章）、串匹配（第十四章）、图论（第十五章）、组合优化（第十六章）和算

儿何（第十七章）等。

本单元的第十三章介绍并行排序算法及其MPI编程实现，包括枚举排序、快

速排序和正则采样并行排序P（SRS）等；第十四章介绍并行串匹配算法及其MPI

编程实现，包括并行KMP串匹配、并行随机串匹配和并行近似串匹配等；第十五

章介绍图论并行算法及其MPI编程实现，包括使用矩阵乘求传递闭包、顶点倒塌

法求连通分量、Dijkstra单源最短路径算法和Sollin最小生成树算法等；第十

六章介绍组合优化算法及其MPI编程实现，包括八皇后问题、SAT问题、装箱问

题、背包问题和TSP问题等；第十七章介绍算机几何算法及其MPI编程实现，

包括包含问题、相交问题和凸壳问题等。

为了压缩篇幅，第十三章只给出了PSRS算法的MPI源程序，第十四章只给

出了KMP串匹配并行算法的MPI源程序，第十五章只给出了连通分量并行算法

的MPI源程序，第十六章只给出了八皇后问题并行算法的MPI源程序，其余者均

放在随书的光盘中，也可从中国科学技术大学国家高性能算中心合（肥）的网

站http://www.nhpcc.ustc.edu.cn下载。

第十三章排序

排序是数据处理中经常使用的一种重要运算，如何进行排序，特别是如何进行高效的排

序，是算机应用中的重要课题。排序的对象一般是一组记录组成的文件，而记录则是由若

干数据项组成，其中的一项可用来标志一个记录，称为关键字项，该数据项的值称为关键字。

所谓排序，就是要整理文件中的记录，使得它按关键字递增(或递减)的次序排列起来。若

给定的文件含有n个记录R｛”R2,…，RJ,它们的关键字分别为｛跖，IQ,…，Kn),

要把这n个记录重新排列成为R｛n，R2，…,Rj使得K｛“2Ki2A••，G｝(或K｛“W

Ki2W…WKiJ)。

本章主要介绍了枚举排序、快速排序、PSRS排序算法以及它们的MPI编程实现。

1.1枚举排序

1.1.1枚举排序及其串行算法

枚举排序(EnumerationSort)是一种最简单的排序算法，通常也称为秩排序(RankSort)。

该算法的具体思想是(假设按关键字递增排序)，对每一个待排序的元素统小于它的所有

元素的个数，从而得到该元素最终处于序列中的位置。假定待排序的n个数存在al]…an]

中。首先将al]与a⑵…a网比较,记录比其小的数的个数,令其为k,al]就被存入有序的

数组b川・・・bn]的bk+l]位置上;然后将a⑵与al],a3]…an]比较，记录比其小的数的个

数，此类推。这样的比较操作共n(n・l)次，所以串行秩排序的时间复杂度为。(产)。

算法13・1枚举排序串行算法

输入：al]--,an]

输出：bl]-bn]

Begin

fori=ltondo

(1)k=l

(2)