动态网络最短路径射线追踪算法中向后追踪方法的改进

动态网络最短路径射线追踪算法中的向后追踪方法能够解决线性走时插值算法(LTI)向后追踪过程不稳定的问题,但是其计算效率较低.综合利用节点次级源的位置信息以及波的传播规律,提出了改进方法,排除了动态网络最短路径射线追踪算法向后追踪过程中存在的大量冗余计算.数值算例表明,改进的向后追踪方法具有较高的计算效率,是动态网络最短路径射线追踪算法中向后追踪方法的几倍至几十倍;若将改进后的向后追踪方法应用于动态网络最短路径射线追踪改进算法,则该算法的计算效率将提高一倍左右.     

基于二叉树的有向双环网络的最短路径算法

定义了有向双环网络G(N;r,s)新的路由模型--二叉树模型,给出了O节点到二叉树模型任意一层节点的最短路径的路南策略.证明了有向双环网络的直径等于其二叉树的树高,研究了任意两节点之问的最短路径与其所在层及其相应位置的关系,给出有向双环网络任意两节点最短路径的算法.运用此算法,只需简单的算术运算和关系运算,就能快速求出任意两节点的最短路径.     

一种用于车辆最短路径规划的自适应遗传算法及其与Dijkstra和A*算法的比较

提出了一种自适应遗传算法,并成功应用于车辆最短路径规划算法中. 所采用的编码方式、交叉及变异算子等均针对最短路径规划问题而专门设计;同时,提出了一种新的交叉概率、变异概率在线自适应调整策略,以便提高遗传算法的搜索速度和搜索质量. 将该算法同Dijkstra算法、A*算法进行了仿真比较. 对五种不同情况的仿真研究结果表明:同Dijkstra算法相比,该自适应遗传算法可以减少搜索到最短路径的时间;同A*算法相比,该自适应遗传算法则可以搜索到更多的最短路径.     

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

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

基于遗传算法的离散时间动态网络最短路径求解

采用遗传算法来求解不满足先进先出原则的动态网络中的最短路径问题,并采用所提出的随机A*算法解决了利用遗传算法求解最短路径问题时的最大障碍--初始种群的产生.最后以广州市电子地图为基础随机产生了一个不满足先进先出原则的动态网络(包括20000个节点,40000条边和144个时间间隔).来对所提出的算法进行验证.试验结果表明,遗传算法适合求解非常态且不满足先进先出原则的动态网络中的路径诱导问题.     

无线传感器网络功率优化算法

无线传感器网络由许多电池能量有限的节点组成,该网络主要收集感知区域的信息.节点能量管理的优化对于延长网络寿命具有重要影响,如果每个节点直接向sink节点或基站发送信息,节点电池很快耗尽,网络也会失去作用.提出了动态路由的新方法以平衡节点能量开销,在Dijkstra最短路径算法和改进遗传算法的基础上,以功率有效性为首要原则,建立了网络拓扑.仿真结果接近最优解,达到节省能量的要求.     

A*算法与蚁群算法相结合的无人艇巡逻路径规划

针对无人艇海上巡逻路径规划问题,提出了一种A~*算法与蚁群算法相结合进行最短巡逻路径优化的方法.在传统A~*算法的八角度搜索基础上,设计了一种多角度A~*算法以获得更短的两点之间可行路径,并以A~*算法搜索结果构建任意两个巡逻点之间的最短路径网络.结合最短路径网络建立多点巡逻路径规划问题的目标函数,利用蚁群算法进行求解以获得全局最优的巡逻路径.针对巡逻路径转折角较大的问题,提出了一种平滑算法以获得更符合实际航行需求的平滑路径.仿真结果表明:该方法有效地去除了冗余节点,缩短了路径长度,提高了路径平滑度,规划出了一条更优的无人艇巡逻路径.     

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

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

无线传感器网络自适应拥塞控制的路由算法分析

无线传感器网络中节点的覆盖范围有限,因而采用多跳路由传输方式.无线自组网中的多跳路由是由普通节点协作完成的,选择不同的转发节点,会对网络的信息传输产生不同的影响.对不同路由(洪泛路由、最短路径等)算法下的网络自适应拥塞控制进行了分析,研究了不同路由算法下的网络性能和拥塞控制效果.根据节点跳数与缓存占用的关系,提出一种基于节点跳数和缓存占用的性能函数的改进最短路径算法,算法选取使性能函数值最小的节点作为转发节点.最后,通过实验比较了最短路径算法与改进路由算法的网络性能,发现改进路由算法相比最短路径算法,具有较好的网络性能和服务质量.     

基于多功能网的最短路径查询算法

在单一网络功能下节点间最短路径的研究基础上,提出基于多功能网的最短路径查询问题,给出一种基于贪心策略的查询算法来查询节点间在不同网络功能下的最短路径.利用多功能网对山东半岛城市群进行建模,分别查询城市群网络实现经济和信息两种不同功能时城市间的最短路径,并计算分析.研究结果表明,查询节点间在不同网络功能下的最短路径对于挖...