资源描述：
《基于三维网格的最短路径并行算法研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第29卷第5期计算机工程与设计2008年3月Vol.29No.5ComputerEngineeringandDesignMar.2008基于三维网格的最短路径并行算法研究武亮亮，郑晓薇(辽宁师范大学计算机与信息技术学院，辽宁大连116029)摘要：针对三角网格模型，描述了一种求解最短路径问题的并行算法。该算法使用两矩阵相乘思想，利用对邻接矩阵的划分实现算法的并行化，给出了输出路径值和打印路径的过程分析。最后给出了该算法在机群环境下的实现，并联系实际例图，进行了算法性能分析，验证了其具有很好的并行效率。关键词：三角网格;最短路径;矩阵相乘;并行;机群中图法分类号：TP39
2、1文献标识码：A文章编号：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引言代得到的是任意两个结点间边的条数最多为k时的最短路径。以最简单的三角网格模型为例，采用赋权邻接矩阵的存储结最短路径问题是最基本的网络优化问题之一，在众多研究构，可如图1所示。和应用领域如计算机科学、计算机网络与通信、ITS、GIS、控制与V决策等，都具有重要的意义。许多著名的Directx游戏也都采用该技术
5、，用于解决游戏地图中的地形和障碍问题。而近年来三角网格模型在几何建模、计算机图形学等领域的广泛应用，使VV得人们更关注于最短路径问题在三维网格模型上的研究。最短路径问题的经典解法有Dijkstra算法和Floyd算法[2]，V由于由大量小三角平面片组成的三角网格细节特征丰富、容易获得，而且在图形显示、快速原型制造、有限元分析等方面具图1带权有向三角网格模型G有明显优势，所以涌现出了多种三角网格模型上的最短路径算法[3-4]。这些算法按精度可分为精确算法和近似算法两类，每其初始邻接矩阵为025一类中都有几种典型的最短路径算法[6-7]。但这些算法大多是在求解方法和存储结构
6、上不断提升，都是基于串行的。本文给A=02032出了求解最短路径问题的并行算法，巧妙使用数值算法中的矩20设pi,kj是从结点vi到vj的最短路径，前提是路径最多包含阵乘思想，在简化求解过程的同时，得到了很好的并行性能。1最短路径算法并行化过程条边；并设di,kj是pi,kj的长度。若pi,kj的倒数第2个结点是vm，则有：pi,kj=pi,km1+(vm,vj)，又因为结点到自身的最短路径为0，于是得到下面的递推式1.1矩阵相乘并行思想的引入使用矩阵相乘法的核心思想是通过n次迭代，第k次迭di,kj=min{di,km1+w(vm,vj)}1mn收稿日期：2007-0
7、4-23E-mail：yekal@163.com基金项目：辽宁省教育厅科研基金项目(05L209)。作者简介：武亮亮(1982－)，女，辽宁锦州人，硕士研究生，研究方向为并行计算；郑晓薇(1957－)，女，辽宁大连人，教授，研究方向为并行计算、计算机决策支持系统等。－1116－设D(k)=(di,j)，则Dk(n-1)即为问题的解。在上面的递归表达奇数号处理器先将子块bi存于缓冲区buffer中，然后接受编号式中，如果把“×”操作改为“+”；将“”操作改为“min”，则形式在其后的处理器发送的子块，最后再将缓冲区中的子块b发上就等同于矩阵
