互联网络RCP（n）的最短路算法

RCP（n）是最近提出的一种新型互联网络拓扑结构,是由环、Petersen图和交叉立方体所组成的,具有短直径、良好的可扩展性和正则性以及较小的构造开销的性质,是一种具有良好拓扑性质的互联网络。针对RCP（n）上节点编码的特点,采用逐步分解编码,依次寻找路径的方法给出了寻找RCP（n）上任意两点间最短路的一个多项式算法,为RCP（n）上作进一步的路由算法、最优分组等通讯性能的研究提供了理论支持,因此具有一定的理论意义和应用价值。     

互联网络RCP(n)的路由算法

在对互联网络RCP（Ringed Crossed cube Petersen）拓扑结构研究的基础上,利用RCP（n）网络具有正则性,良好的可扩展性,以及具有比Q_n、HP（n）、RHP（n）网络更短的直径和更小的构造开销这些特性,给出了RCP（n）的单播路由算法和广播路由算法,并证明了RCP（n）比Q_n、HP（n）、RHP（n）网络具有更好的路由性能。     

一种实用的互联网络RPn(k)及其路由算法

基于环的简单扩展性和Petersen图的短直径,提出了一类新型互联网络RPn(k),研究了该互联网络的性质,它不但具有正则性和良好的可扩展性,还具有比RP(k)互联网络更短的网络直径、更好的可分组性以及更小的网络构造开销。最后,讨论了RPn(k)网络的路由问题,给出了点点路由算法,其通信效率为[k/2]+2n个时间步。在节点个数相同时,RPn(k)比RP(k)网络上的路由算法的通信效率有明显提高。     

一种实用的互联网络拓扑结构RPC(k)及路由算法

Pertersen图由于具有短直径和正则性等特性,在并行计算与分布式计算中具有良好的性能.基于环结构,提出了一种Pertersen图的新扩展方法,构造了互联网络RPC(k).分析了该互联网络的性质,它具有连接度小、网络直径短、拓扑结构简单以及易于扩展等特点.同时给出了RPC(k)优于二维Torus以及RP(k)互联网络的直径和节点可分组性的条件.最后,分别设计了RPC(k)上的单播路由、置换路由、广播路由和多对多路由,它们的通信效率分别为「k/2」+5,k+9,「k/2」+5和k+9.特别是随着k的增大,RPC(k)网络路由算法的通信效率近似于RP(k)网络上的时应算法通信效率的1/3倍.     

基于超立方体环连接的Petersen图互联网络研究

基于环的简单扩展性,Petersen图的短直径与超立方体互联网络中节点的高可连接性相结合,提出了一种新型互联网络RHP(n)(Ringed Hypercube Connected Petersen),并对其特性进行了研究．证明了RHP(n)网络不但具有正则性以及良好的可扩展性,同时还具有比Q、HP(n)网络更短的直径和更小的构造开销．另外,还基于RHP(n)网络分别给出了其上的单播和广播路由算法,证明了其通信效率分别为n-1和n-1．     

带权区间图的最短路算法

提出一个解带权区间图的最短路问题的O(nα(n))时间新算法，其中n是带权区间图中带权区间的个数，α(n)是单变量Ackerman函数的逆函数，它是一个增长速度比log n慢得多的函数，对于通常所见到的n，α(n)≤4．本文提出的新算法不仅在时间复杂性上比直接用Dijkstra算法解带权区间图的最短路问题有较大改进，而且算法设计思想简单，易于理解和实现．     

网络最短路问题的改进算法

本文着重研究著名的Dijkstra网络最短路算法的实现效率，提出算法实现的若干技巧，大大提高了Dijkstra最短路算法的适用性和时间空间效率。     

改进的进化算法解最短路问题

最短路问题是组合优化中的经典问题之一,对其设计有效的算法具有广泛的应用价值和重要的理论意义．为了减少对初始种群选取的限制,扩大种群的多样性,本文提出了一种新的杂交方式．根据一对染色体中不同位相同基因对的数目,设计了分类杂交．这种杂交不仅增加了种群的多样性,还避免了不可行解的出现．与杂交算子相对应设计了具有局部搜索功能的收缩—扩张式变异算子,使得本算法效率有了极大提高,并在理论上证明该算法以概率1收敛到全局最优解．最后的数值试验也表明此算法是十分有效的．     

最短路问题的Floyd加速算法与优化

Floyd算法是求解网络中任意两点之间最短路的高效算法,文章给出了在不含负回路的网络中Floyd加速算法及优化方法,并构造了求解最短路径的序号矩阵。算法分析和计算实例表明,优化后的Floyd加速算法迭代速度快,计算量大大减少,路径寻找简单、直观。     

基于Floyd算法的多重最短路问题的改进算法

路径分析是网络分析最基本的问题,其核心是对最短路径的求解。Floyd算法是一种求取最短路的经典算法。分析发现,两点间可能存在多条权重相同的最短路径,而这一点Floyd算法没有涉及。以无向联通图为研究对象,设计了基于Floyd求解多重等价最短路算法,并分析计算了一个实际算例。计算结果表明,基于Floyd的多重等价最短路算法可以有效解决多重等价最短路问题。     

基于遗传算法的最短路径问题求解

详细分析了求解最短路径的遗传算法的构成要素,提出一种新的交叉变异算法,通过仿真实验论证了求解过程是合理而有效的,同时给出了算法的主要性能参数,并对其进行了分析。     

动态交通网络中最优路径查找算法*

在真实交通网络中,可能出现某高速公路在某一时刻内通过的车辆过多,从而改变了该时刻道路的即时速度,这就需要对道路的交通流量进行监控。针对这一问题,通过建立交通网络的速度模式库,根据道路可达速度的变化更新速度模式。基于A*算法与速度模式库,提出针对动态交通网络的最短路径查询算法。采用真实数据集对算法进行测试,结果表明,应用该方法能够有效地解决在速度模式发生变化的情况下最优路径的查找,使交通网络中的最优路径查询更为准确有效。     

基于MapX最短路径搜索算法研究

在深入分析现有最短路径搜索算法和MapX空间特性的基础上,提出了一种基于MapX的局部最短路径搜索算法.该算法依据最短路径沿起点、终点连线方向可能性最大的特征,在小矩形范围内搜索,避免了因道路"振荡"而产生结果失真的问题,减少了搜索的节点数目,降低了搜索规模.实验结果表明,该算法搜索速度快,道路网络结构越复杂,其运行效率越高,具有很强的实用性.     

一种基于层次图模型的最优路径算法

论述了一种新的基于层次图的最优路径算法,即将一个平面图划分若干子图,子图抽象为一个高层图。最短路径的计算首先在高层图中进行,缩小了最优路径的查找范围,降低了最优路径计算的时间开销。     

基于GIS的救护车辆最短路径算法

基于地理信息系统(GIS) 台,利用经典的单源最短路径算法--Dijkstra算法,对其进行了最小堆结构和邻接表存储模型优化.程序仿真结果表明,优化后的结果比经典算法在时间复杂度和空间复杂度上都有所降低,在救护车辆最短路径选择中有一定的实际价值.     

Shortest hop multipath algorithm for wireless sensor networks

Shortest hop or distance path is one of the most common methods used for relaying messages in a wide variety of networks. It provides an efficient message relaying to destination in terms of energy and time. There are many algorithms for constructing shortest hop or distance path. However, according to our knowledge, no algorithm for constructing a shortest hop multipath for wireless sensor networks (WSNs) has yet been proposed in the literature. In this paper, we propose a novel distributed shortest hop multipath algorithm for WSNs in order to generate energy efficient paths for data dissemination or routing. The proposed algorithm generates shortest hop braided multipath to be used for fault-tolerance or load-balancing. It guarantees the BFS tree and generates near optimal paths in O(V.D+V) message complexity and O(D²) time complexity regarding the communication costs towards the sink after termination of algorithm.     

栅格数据模型中附有条件的最短路径算法

将附有条件的最短路径概括为点约束、边约束和属性约束的最短路径问题。以栅格数据模型为图或网络描述方式,基于贪心算法思想,提出栅格数据模型中附有条件的最短路径算法。最后,通过实例进行了算法测试,结果表明栅格数据模型中附有条件的最短路径算法是完全可行和有效的。     

一种基于转向限制的城市交通网最短路径算法

针对城市交通网导航的实际需要,提出了有向加权图的模型,图中顶点不仅包括路口,还包括起点和终点,并对Dijkstra算法进行改进,提出了一种基于转向限制的城市交通网最短路径算法,通过加入虚拟顶点,从而适应转向限制的条件。实验表明了该算法的正确性。