拉丁方的位序性及其并行枚舉算法研究.pdf

1、組合數(shù)學(xué)在計(jì)算機(jī)學(xué)科、智能學(xué)科以及信息學(xué)科有著廣泛而深入的應(yīng)用。拉丁方作為組合數(shù)學(xué)的重要研究對象也有著廣泛的應(yīng)用背景，已吸引許多學(xué)者的關(guān)注。然而，多年來，特定階數(shù)的拉丁方的存在性、如何枚舉等問題仍然沒有得到很好地解決。原因之一是計(jì)算量太大，以致在單機(jī)系統(tǒng)上不可能完成?！熬W(wǎng)絡(luò)即是計(jì)算”概念的產(chǎn)生標(biāo)志著，網(wǎng)絡(luò)可以為用戶提供一個(gè)友好而透明的分布式并行計(jì)算環(huán)境。而消息傳遞接口MPI(Message Passing Interface)編程模式的

2、提出，更極大地方便了用戶基于分布環(huán)境進(jìn)行并行編程。本文即基于上述兩個(gè)研究視角，試圖對拉丁方的位序性及其并行枚舉算法實(shí)現(xiàn)進(jìn)行研究。 論文針對拉丁方的構(gòu)成特點(diǎn)，即把拉丁方的每一行看成是從{1，2，…，n}集合中選擇n個(gè)元素的一個(gè)排列，把刀階拉丁方看成是從n!個(gè)排列元素構(gòu)成的集合中選擇n個(gè)元素的排列或組合，根據(jù)排列與組合具有詞典序的特點(diǎn)，研究分析了拉丁方的位序性；針對排列與組合的詞典序是連續(xù)并且有界的特點(diǎn)，提出了滿足拉丁方形成條件的矩

3、陣所對應(yīng)的詞典序也是有界的，進(jìn)而證明只要給定拉丁方的階數(shù)，即可以枚舉出所有的拉丁方。然而，由于拉丁方的計(jì)數(shù)范圍很大，可以說在單處理機(jī)環(huán)境下枚舉拉丁方計(jì)算上是不可行的，需研究并行計(jì)算環(huán)境下枚舉拉丁方的問題。MPI非常適合分布式計(jì)算環(huán)境下的并行編程，在高性能計(jì)算界已得到廣泛的使用。論文分析并給出了排列、組合、拉丁方與位序的轉(zhuǎn)換方法并給出了具體的串行算法實(shí)現(xiàn)與并行算法實(shí)現(xiàn)。介紹了MPI的數(shù)據(jù)類型與編程模型，對MPI通信子與通信方式進(jìn)行了分析。