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

【摘要】：并行計(jì)算擁有有強(qiáng)大的數(shù)值計(jì)算和處理數(shù)據(jù)的能力,在現(xiàn)實(shí)生活中有著廣泛的應(yīng)用,如地震的預(yù)測(cè)和預(yù)報(bào)、石油的勘探、氣候的模擬、武器方面的設(shè)計(jì)、核武器系統(tǒng)的研究與模擬、航空和航天飛行器的設(shè)計(jì)、衛(wèi)星圖像的處理、天體和地球的科學(xué)、虛擬現(xiàn)實(shí)的系統(tǒng)和電影的動(dòng)畫(huà)系統(tǒng)等。 棋盤支配問(wèn)題開(kāi)啟了圖的支配集問(wèn)題的研究,直到1962年才由Berge和Ore出版的書(shū)中給出了一些最基本的數(shù)學(xué)定義。即使是最早的棋盤支配問(wèn)題研究起來(lái)也是相當(dāng)困難的,到目前來(lái)說(shuō)許多問(wèn)題大部分還沒(méi)有完全解決。這些懸而未決的問(wèn)題在十九世紀(jì)七十年代促進(jìn)了圖的支配集問(wèn)題的研究,其中最有趣和最困難的就是皇后支配集問(wèn)題。 并行計(jì)算的發(fā)展為解決圖論中的一些難題提供給了可能,圖論中的一些難題是可以借助并行計(jì)算機(jī)來(lái)得到解決。本文就是在最小皇后獨(dú)立支配集串行算法的基礎(chǔ)上提出了一個(gè)并行的算法,在集群這個(gè)平臺(tái)上實(shí)現(xiàn)了對(duì)最小皇后獨(dú)立支配集的并行計(jì)算。
[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.
【學(xué)位授予單位】：內(nèi)蒙古農(nóng)業(yè)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2012
【分類號(hào)】：TP338.6;O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 張光鐸，，王正志;圖論中獨(dú)立支配集的最佳求解算法研究[J];國(guó)防科技大學(xué)學(xué)報(bào);1995年02期

2 張劍英,周三明;與圖的支配性有關(guān)的不變量的若干不等式[J];華中理工大學(xué)學(xué)報(bào);1996年11期

3 莫忠息;圖論中獨(dú)立支配集的求解問(wèn)題并未解決[J];數(shù)學(xué)研究與評(píng)論;1999年01期

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

5 趙亞谷;關(guān)于圖的支配劃分的兩個(gè)猜測(cè)[J];數(shù)學(xué)研究與評(píng)論;1986年03期

6 路綱;周明天;唐勇;吳振強(qiáng);裘國(guó)永;袁柳;;任意圖支配集精確算法回顧[J];計(jì)算機(jī)學(xué)報(bào);2010年06期

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

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

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

10 馮詩(shī)齊;用并行計(jì)算構(gòu)建一個(gè)虛擬太空[J];世界科學(xué);2002年10期

相關(guān)會(huì)議論文 前10條

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

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

3 張望;王輝;;個(gè)性化服務(wù)中的并行K-Means聚類算法[A];2007年全國(guó)開(kāi)放式分布與并行計(jì)算機(jī)學(xué)術(shù)會(huì)議論文集(下冊(cè))[C];2007年

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

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

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

7 左風(fēng)麗;莫?jiǎng)t堯;葉文華;;計(jì)算流體三維分裂格式的高效并行計(jì)算[A];中國(guó)工程物理研究院科技年報(bào)（2003）[C];2003年

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

9 杜志文;曾文華;;網(wǎng)格計(jì)算在文本分類中的應(yīng)用[A];2006年全國(guó)開(kāi)放式分布與并行計(jì)算機(jī)學(xué)術(shù)會(huì)議論文集（三）[C];2006年

10 耿江東;薛正輝;高本慶;;應(yīng)用并行GTD算法計(jì)算陣列天線近場(chǎng)受擾[A];第17屆全國(guó)電磁兼容學(xué)術(shù)會(huì)議論文集[C];2007年

相關(guān)重要報(bào)紙文章 前10條

1 江錫民;英特爾并行計(jì)算中心落戶無(wú)錫[N];新華日?qǐng)?bào);2009年

2 軼嘉;英特爾全球首個(gè)并行計(jì)算中心落戶無(wú)錫[N];人民郵電;2009年

3 劉琦;伯克利專家展望未來(lái)并行計(jì)算[N];中國(guó)計(jì)算機(jī)報(bào);2008年

4 均兒;通用計(jì)算核動(dòng)力[N];電腦報(bào);2009年

5 英特爾并行計(jì)算實(shí)驗(yàn)室研究員 TimothyMattson;并行計(jì)算:減少串行軟件[N];中國(guó)計(jì)算機(jī)報(bào);2007年

6 本報(bào)記者 馬文方;英特爾為何要牽頭并行計(jì)算[N];中國(guó)計(jì)算機(jī)報(bào);2009年

7 英特爾 趙軍(Jun Zhao);PC機(jī)并行計(jì)算革命尚未成功[N];中國(guó)計(jì)算機(jī)報(bào);2009年

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

9 劉霞;計(jì)算能力的提升需要一場(chǎng)革命[N];科技日?qǐng)?bào);2010年

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

相關(guān)博士學(xué)位論文 前10條

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

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

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

4 路綱;無(wú)線自組織網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)研究[D];電子科技大學(xué);2009年

5 陳軍;分布式存儲(chǔ)環(huán)境下并行計(jì)算可擴(kuò)展性的研究與應(yīng)用[D];中國(guó)人民解放軍國(guó)防科學(xué)技術(shù)大學(xué);2000年

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

7 陳曉春;基于并行計(jì)算的大渦模擬方法及其工程應(yīng)用基礎(chǔ)研究[D];西安建筑科技大學(xué);2004年

8 王開(kāi)健;基于特大增量步算法的網(wǎng)絡(luò)并行計(jì)算[D];清華大學(xué);2005年

9 尹欣;三維彈性問(wèn)題邊界元法并行計(jì)算及其工程應(yīng)用[D];清華大學(xué);2000年

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

相關(guān)碩士學(xué)位論文 前10條

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

2 王R

本文編號(hào)：1462577