一种基于Dijkstra算法的三角网格地表模型算法

对二维地表模型运用Dijkstra算法求解最短路径时,为了减少计算量,需要对模型进行简化后,才开始进行Dijkstra算法的求解,所以结果并不符合实际地表情况。不在模型上进行任何简化,而是直接在模型上划分三角网格来处理最原始的模型。然后用基于Dijkstra算法和矢量夹角的三角网格地表模型算法求解最短路径。通过此算法完成了一个实例的最短路径求解。结果表明,采用文中算法所得到的结果符合Dijkstra算法求得的路径和实际情况,而复杂度并没有因为未简化模型而大幅上升,并且算法具有效率高、复杂度低、稳定性好等优点。     

适用于大规模网络的全源最短路径重优化算法——RASP算法

为提升大规模网络全源最短路径的求解效率,基于重优化理论提出了一种快速的精确全源最短路径求解方法——RASP(reoptimization-based all-pairs shortest path)算法.分析了异源最短路径树间的相关性和差异性;在已知单源最短路径树的基础上,基于重优化理论实现了异源最短路径树间的高效转换,进而得出高效求解全源最短路径的RASP算法;理论证明RASP算法的时间复杂度为O(3n~2+2nm).实验测试表明:无论是在稀疏还是稠密网络上,RASP算法都能有效地超越Floyd算法、n次Dijkstra算法及其改进算法.     

基于模拟退火算法的曲面最短路径求解

通过对路径的节点序列内在关联性的分析，提出了适合曲面最短路径问题的邻域结构，使整段路径的优化问题能够通过局部得以实现，将模拟退火算法的框架引入路径寻优中，提出了解决曲面最短路径的随机搜索算法。最后给出了数值仿真实例。     

曲面均匀网格轮式行进生成法

提出一种新的曲面有限元网格生成方法,将曲面边界离散相邻节点连接构造线段序列,并从序列中的线段出发,以线段的空间位置为依据,构造圆,再利用该圆在曲面上布点筛选求取网格节点,生成单元,使节点一单元一线段交替生成,该方法实现了曲面均匀网格的自动生成,网格质量良好,适用于不同形式的曲面,具有很大程度的通用性,有利于解决有限元分析建模的瓶颈之一——曲面网格自动生成问题。     

角度约束路径法的网格曲面兴趣区域边界快速交互选取

提出角度约束路径法,快速获取三角网格曲面上任意两顶点间一条由网格边所组成的路径.该算法是一个从起始点开始不断向前传播的过程,计算量仅与两顶点间的曲面区域有关,故算法的时间复杂度(O(n))优于Dijkstra算法(O(n log n)).试验结果表明:角度约束路径法的执行快速、有效;基于该方法可实现三角网格曲面兴趣区域边界的快速交互选取.     

基于k-臂分子求解最短路径的DNA计算模型

为有效求解最短路径问题, 避免传统算法计算量大、 求解时间长的问题, 充分发挥DNA(Deoxyribo Nuclec Acid)计算的并行性在求解复杂计算问题的优势, 提出一种基于k-臂分子和粘贴计算求解最短路径问题的DNA计算模型, 阐述了顶点、边及权值的编码方案, 描述了求解最短路径的DNA算法, 经验证, 该模型对求解最短路径问题是有效的。     

基于最小生成树算法求解图的单源最短路径的研究

对《基于Kruskal算法的最短路径算法研究》一文中提出的方法进行探讨,通过构造实例论证了Kruskal算法并不能直接用于求解有向带权图的单源最短路径问题,并综合性地对基于最小生成树算法求解图的单源最短路径问题进行分析,通过构造实例最终得出最小生成树算法不适用于求解图的单源最短路径问题的结论.     

基于最小生成树算法求解图的单源最短路径的研究

对《基于Kruskal算法的最短路径算法研究》一文中提出的方法进行探讨,通过构造实例论证了Kruskal算法并不能直接用于求解有向带权图的单源最短路径问题,并综合性地对基于最小生成树算法求解图的单源最短路径问题进行分析,通过构造实例最终得出最小生成树算法不适用于求解图的单源最短路径问题的结论.     

基于气泡吸附的自由曲面三角形网格生成方法

为了满足自由曲面网格结构对网格均匀性的要求,提出了一种自由曲面的三角形网格自动生成方法——空间气泡法.首先,按一定规则在曲面上布置适量的网格点;然后,将网格点模拟为大小相同的弹性气泡,引入气泡间的相互作用力,得到各气泡的运动控制方程,并利用Velocity-Verlet算法求得气泡系统的平衡状态;接着,通过求气泡中心点的三维Voronoi图与曲面的交线得到曲面上的Voronoi图;最后,对曲面Voronoi图做对偶变化并删去冗余边,得到曲面上的Delaunay图,即所求的三角形网格.算例表明:该方法自动化程度高,适用范围广,生成的网格规整、均匀,为网格结构的设计提供了便利.     

基于极小代数赋权有向图最短路径求解算法

应用极小代数给出了求解简单有向赋权图最短路径问题的代数算法.该算法基于赋权有向图的直接距离矩阵A,在极小代数意义下计算k步最短路径距离矩阵Ak和最短路径距离矩阵A+,并依此确定出赋权有向图的最短路径以及最少步数最短路径.与Dijkstra算法相比较,所提出的代数算法求解路径规划问题能够较快地得到特定的最短路径及其长度.     

多面体面上任意两点间最短路径算法

提出计算多面体面上任意两点之间最短路径的算法:近似算法、最短路径或近似最短路径算法.近似算法的思想是采用将折线不断嵌入三角形串上的方法,而另2个算法则是通过特定法线寻找三角形串,而且将这些三角形旋转到同一平面上,从而得到最短路径.前者的时间复杂性为O(n),而后者的时间复杂性分别是O(n2)及低于O(2nn2).     

道路网络中最短路径的算法与实现

最短路径算法是地理信息科学与计算机科学等领域的研究热点。本文从网络分析的理论基础及拓扑性质出发，提出了一种适于最短路径算法的空间数据组织方式。结合道路网络的特点，在构造邻接结点矩阵来表达网络结构的基础上，运用优化的迪杰斯特拉(Dijkstra)最短路径算法，在电子地图环境下实现了道路网络中任意两结点间最短路径的快速解算与刷新。     

一种最短路径分析优化算法的实现

在对地理信息系统中最短路径分析的实现方案和现有各种最短路径分析算法进行分析、研究的基础上,提出了“优化Dijkstra算法”。该方法使Dijkstra算法的搜索方向明显趋向于目标结点,减少了算法中遍历的结点数,从而提高了搜索速度。总结出两个Dijkstra算法的优化途径：对搜索到的临时标记结点按照最短路径值排序;减小结点的搜索范围即减少永久标记结点的数量。     

稀疏网络的Floyd动态优化算法

通过对Floyd算法进行研究,提出了一种新的求取任意两点间最短路径的算法:Floyd动态优化算法.该算法通过引入插入数组、可达数组以及可发数组,使得算法在求解最短路径前自动修改能够最小化路径的节点,剔除一些无用的节点,最小化语句执行的次数.算法分析表明,新算法在稀疏网络中比Floyd算法在性能上有较大的提高.     

基于相似度测量法的模糊最短路径问题

提供了一种基于相似度测量法处理模糊最短路径问题的算法,通过计算各路径的相似度找到模糊最短路径长度,并获得相应的模糊最短路径.     

基于遗传算法的汽车式移动机器人路径规划方法

对文题进行了数学描述，提出了一种基于遗传算法的汽车式移动机器人最短距离路径规划新方法，探索了解决非完整系统路径规划问题的新途径．利用经改装的遥控汽车模型进行了路径规划实验，取得了令人满意的实验结果