資源描述：
《基于三維網(wǎng)格的最短路徑并行算法研究》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、第29卷第5期計(jì)算機(jī)工程與設(shè)計(jì)2008年3月Vol.29No.5ComputerEngineeringandDesignMar.2008基于三維網(wǎng)格的最短路徑并行算法研究武亮亮，鄭曉薇(遼寧師范大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，遼寧大連116029)摘要：針對(duì)三角網(wǎng)格模型，描述了一種求解最短路徑問(wèn)題的并行算法。該算法使用兩矩陣相乘思想，利用對(duì)鄰接矩陣的劃分實(shí)現(xiàn)算法的并行化，給出了輸出路徑值和打印路徑的過(guò)程分析。最后給出了該算法在機(jī)群環(huán)境下的實(shí)現(xiàn)，并聯(lián)系實(shí)際例圖，進(jìn)行了算法性能分析，驗(yàn)證了其具有很好的并行效率。關(guān)鍵詞：三角網(wǎng)格;最短路徑;矩陣相乘;并行;機(jī)群中圖法分類(lèi)號(hào)：TP39
2、1文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1000-7024(2008)05-1116-04Parallelalgorithmofshortestpathbasedon3DmashWULiang-liang,ZHENGXiao-wei(CollegeofComputerandInformationTechnology,LiaoningNormalUniversity,Dalian116029,China)Abstract：Inviewofthetrianglemashmodel,akindparallelalgorithmofshortestpathisdescribed.Thetho
3、ughtoftwomatricesmul-tiplicationandthedivisionofthematrixareusedtorealizethealgorithmparallel.Thevalueofoutputwayandtheprocessanalysisofprintingwayarecompleted.Finally,realizationofthisalgorithmintheclusterenvironmentisgivenwithactualillustration,thealgorithmperformanceanalysisispresente
4、d,anditisvalidatedthisalgorithmhavegoodparalleleffectiveness.Keywords：triangularmesh;shortestpath;matrixmultiplication;parallel;MPI0引言代得到的是任意兩個(gè)結(jié)點(diǎn)間邊的條數(shù)最多為k時(shí)的最短路徑。以最簡(jiǎn)單的三角網(wǎng)格模型為例，采用賦權(quán)鄰接矩陣的存儲(chǔ)結(jié)最短路徑問(wèn)題是最基本的網(wǎng)絡(luò)優(yōu)化問(wèn)題之一，在眾多研究構(gòu)，可如圖1所示。和應(yīng)用領(lǐng)域如計(jì)算機(jī)科學(xué)、計(jì)算機(jī)網(wǎng)絡(luò)與通信、ITS、GIS、控制與V決策等，都具有重要的意義。許多著名的Directx游戲也都采用該技術(shù)
5、，用于解決游戲地圖中的地形和障礙問(wèn)題。而近年來(lái)三角網(wǎng)格模型在幾何建模、計(jì)算機(jī)圖形學(xué)等領(lǐng)域的廣泛應(yīng)用，使VV得人們更關(guān)注于最短路徑問(wèn)題在三維網(wǎng)格模型上的研究。最短路徑問(wèn)題的經(jīng)典解法有Dijkstra算法和Floyd算法[2]，V由于由大量小三角平面片組成的三角網(wǎng)格細(xì)節(jié)特征豐富、容易獲得，而且在圖形顯示、快速原型制造、有限元分析等方面具圖1帶權(quán)有向三角網(wǎng)格模型G有明顯優(yōu)勢(shì)，所以涌現(xiàn)出了多種三角網(wǎng)格模型上的最短路徑算法[3-4]。這些算法按精度可分為精確算法和近似算法兩類(lèi)，每其初始鄰接矩陣為025一類(lèi)中都有幾種典型的最短路徑算法[6-7]。但這些算法大多是在求解方法和存儲(chǔ)結(jié)構(gòu)
6、上不斷提升，都是基于串行的。本文給A=02032出了求解最短路徑問(wèn)題的并行算法，巧妙使用數(shù)值算法中的矩20設(shè)pi,kj是從結(jié)點(diǎn)vi到vj的最短路徑，前提是路徑最多包含陣乘思想，在簡(jiǎn)化求解過(guò)程的同時(shí)，得到了很好的并行性能。1最短路徑算法并行化過(guò)程條邊；并設(shè)di,kj是pi,kj的長(zhǎng)度。若pi,kj的倒數(shù)第2個(gè)結(jié)點(diǎn)是vm，則有：pi,kj=pi,km1+(vm,vj)，又因?yàn)榻Y(jié)點(diǎn)到自身的最短路徑為0，于是得到下面的遞推式1.1矩陣相乘并行思想的引入使用矩陣相乘法的核心思想是通過(guò)n次迭代，第k次迭di,kj=min{di,km1+w(vm,vj)}1mn收稿日期：2007-0
7、4-23E-mail：yekal@163.com基金項(xiàng)目：遼寧省教育廳科研基金項(xiàng)目(05L209)。作者簡(jiǎn)介：武亮亮(1982－)，女，遼寧錦州人，碩士研究生，研究方向?yàn)椴⑿杏?jì)算；鄭曉薇(1957－)，女，遼寧大連人，教授，研究方向?yàn)椴⑿杏?jì)算、計(jì)算機(jī)決策支持系統(tǒng)等。－1116－設(shè)D(k)=(di,j)，則Dk(n-1)即為問(wèn)題的解。在上面的遞歸表達(dá)奇數(shù)號(hào)處理器先將子塊bi存于緩沖區(qū)buffer中，然后接受編號(hào)式中，如果把“×”操作改為“+”；將“”操作改為“min”，則形式在其后的處理器發(fā)送的子塊，最后再將緩沖區(qū)中的子塊b發(fā)上就等同于矩陣
