本文關鍵詞： 回溯 并行計算 非阻塞通信　出處：《內(nèi)蒙古農(nóng)業(yè)大學》2012年碩士論文　論文類型：學位論文

【摘要】：并行計算擁有有強大的數(shù)值計算和處理數(shù)據(jù)的能力,在現(xiàn)實生活中有著廣泛的應用,如地震的預測和預報、石油的勘探、氣候的模擬、武器方面的設計、核武器系統(tǒng)的研究與模擬、航空和航天飛行器的設計、衛(wèi)星圖像的處理、天體和地球的科學、虛擬現(xiàn)實的系統(tǒng)和電影的動畫系統(tǒng)等。 棋盤支配問題開啟了圖的支配集問題的研究,直到1962年才由Berge和Ore出版的書中給出了一些最基本的數(shù)學定義。即使是最早的棋盤支配問題研究起來也是相當困難的,到目前來說許多問題大部分還沒有完全解決。這些懸而未決的問題在十九世紀七十年代促進了圖的支配集問題的研究,其中最有趣和最困難的就是皇后支配集問題。 并行計算的發(fā)展為解決圖論中的一些難題提供給了可能,圖論中的一些難題是可以借助并行計算機來得到解決。本文就是在最小皇后獨立支配集串行算法的基礎上提出了一個并行的算法,在集群這個平臺上實現(xiàn)了對最小皇后獨立支配集的并行計算。
[Abstract]:Parallel computing has powerful numerical computing and data processing ability, and has been widely used in real life, such as earthquake prediction and prediction, oil exploration, climate simulation, weapon design. Nuclear weapon system research and simulation, aerospace aircraft design, satellite image processing, celestial and Earth science, virtual reality system and movie animation system. The chessboard domination problem opens up the study of the dominating set problem of graphs. It was not until 1962 that some basic mathematical definitions were given in the books published by Berge and Ore. Even the earliest problems of chessboard domination were difficult to study. Up to now, most of the problems have not been solved completely. In 1870s, these outstanding problems promoted the study of the dominating set problem of graphs. One of the most interesting and difficult is the question of the Queen's domination set. The development of parallel computing makes it possible to solve some difficult problems in graph theory. Some difficult problems in graph theory can be solved by parallel computers. This paper proposes a parallel algorithm based on the serial algorithm of the minimal queen independent dominating set. On the platform of cluster, the parallel computation of the minimum queen independent dominating set is realized.
【學位授予單位】：內(nèi)蒙古農(nóng)業(yè)大學
【學位級別】：碩士
【學位授予年份】：2012
【分類號】：TP338.6;O157.5

【相似文獻】

相關期刊論文 前10條

1 張光鐸，，王正志;圖論中獨立支配集的最佳求解算法研究[J];國防科技大學學報;1995年02期

2 張劍英,周三明;與圖的支配性有關的不變量的若干不等式[J];華中理工大學學報;1996年11期

3 莫忠息;圖論中獨立支配集的求解問題并未解決[J];數(shù)學研究與評論;1999年01期

4 蔡延光 ,羅狄隱;樹的兩類m—路中心[J];湖北汽車工業(yè)學院學報;1992年01期

5 趙亞谷;關于圖的支配劃分的兩個猜測[J];數(shù)學研究與評論;1986年03期

6 路綱;周明天;唐勇;吳振強;裘國永;袁柳;;任意圖支配集精確算法回顧[J];計算機學報;2010年06期

7 蔡延光;圖的增廣支配數(shù)[J];湖北汽車工業(yè)學院學報;1999年01期

8 羅朝陽;曹香蘭;李虎;;一些特殊圖類的Kronecker乘積的參數(shù)[J];昌吉學院學報;2010年02期

9 王福軍,程建鋼,姚振漢;結構非線性動力分析顯式積分并行算法[J];清華大學學報(自然科學版);2002年04期

10 馮詩齊;用并行計算構建一個虛擬太空[J];世界科學;2002年10期

相關會議論文 前10條

1 齊進;葉文華;;三維激光燒蝕瑞利-泰勒不穩(wěn)定性并行計算[A];中國空氣動力學學會第十屆物理氣體動力學專業(yè)委員會會議論文集[C];2001年

2 范曉檣;李樺;田正雨;;超聲速/高超聲速飛行器復雜流場大規(guī)模并行數(shù)值仿真[A];計算流體力學研究進展——第十二屆全國計算流體力學會議論文集[C];2004年

3 張望;王輝;;個性化服務中的并行K-Means聚類算法[A];2007年全國開放式分布與并行計算機學術會議論文集(下冊)[C];2007年

4 叢鵬;;MPI并行計算實現(xiàn)工業(yè)CT圖像重建[A];2004年CT和三維成像學術年會論文集[C];2004年

5 丁國昊;羅凱;李偉;李樺;;乘波飛行器氣動特性數(shù)值模擬與并行計算[A];第三屆高超聲速科技學術會議會議文集[C];2010年

6 唐維軍;張景琳;蔚喜軍;;三維流體界面不穩(wěn)定性的并行計算[A];中國工程物理研究院科技年報（2000）[C];2000年

7 左風麗;莫則堯;葉文華;;計算流體三維分裂格式的高效并行計算[A];中國工程物理研究院科技年報（2003）[C];2003年

8 羅文彩;陳小前;;并行計算的多方法優(yōu)化協(xié)作[A];第二十四屆中國控制會議論文集（上冊）[C];2005年

9 杜志文;曾文華;;網(wǎng)格計算在文本分類中的應用[A];2006年全國開放式分布與并行計算機學術會議論文集（三）[C];2006年

10 耿江東;薛正輝;高本慶;;應用并行GTD算法計算陣列天線近場受擾[A];第17屆全國電磁兼容學術會議論文集[C];2007年

相關重要報紙文章 前10條

1 江錫民;英特爾并行計算中心落戶無錫[N];新華日報;2009年

2 軼嘉;英特爾全球首個并行計算中心落戶無錫[N];人民郵電;2009年

3 劉琦;伯克利專家展望未來并行計算[N];中國計算機報;2008年

4 均兒;通用計算核動力[N];電腦報;2009年

5 英特爾并行計算實驗室研究員 TimothyMattson;并行計算:減少串行軟件[N];中國計算機報;2007年

6 本報記者 馬文方;英特爾為何要牽頭并行計算[N];中國計算機報;2009年

7 英特爾 趙軍(Jun Zhao);PC機并行計算革命尚未成功[N];中國計算機報;2009年

8 ;并行計算成PC產(chǎn)業(yè)發(fā)展瓶頸[N];人民郵電;2008年

9 劉霞;計算能力的提升需要一場革命[N];科技日報;2010年

10 向東;讓并購增值：一切取決于管理[N];江蘇經(jīng)濟報;2005年

相關博士學位論文 前10條

1 于瑞云;無線傳感器網(wǎng)絡中面向數(shù)據(jù)采集的支配集算法與策略研究[D];東北大學;2009年

2 駱偉忠;無線網(wǎng)絡中若干NP-難問題的參數(shù)算法[D];中南大學;2012年

3 施韋;移動Ad Hoc網(wǎng)絡中連通支配集若干關鍵問題的研究[D];浙江大學;2007年

4 路綱;無線自組織網(wǎng)絡拓撲結構研究[D];電子科技大學;2009年

5 陳軍;分布式存儲環(huán)境下并行計算可擴展性的研究與應用[D];中國人民解放軍國防科學技術大學;2000年

6 閻新芳;無線Ad hoc網(wǎng)絡分層路由問題研究[D];天津大學;2005年

7 陳曉春;基于并行計算的大渦模擬方法及其工程應用基礎研究[D];西安建筑科技大學;2004年

8 王開健;基于特大增量步算法的網(wǎng)絡并行計算[D];清華大學;2005年

9 尹欣;三維彈性問題邊界元法并行計算及其工程應用[D];清華大學;2000年

10 張理論;面向氣象預報數(shù)值模式的高效并行計算研究[D];中國人民解放軍國防科學技術大學;2002年

相關碩士學位論文 前10條

1 馬俊清;并行計算在計算最小皇后獨立支配集的研究[D];內(nèi)蒙古農(nóng)業(yè)大學;2012年

2 王R

本文編號：1462577