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

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

GIS网络分析城市道路寻优中的应用

针对城市道路网的特点,运用GIS网络分析功能,建立了基于路段连接的道路网络模型,并选择可达性作为道路权重对道路网进行了最短路径分析.同时对经典的Dijkstra算法加以改进,提出了求解道路网任意两点间最短路径的算法,该算法搜索速度快,具有较强的适用性.     

最短路径问题的DNA算法

最短路径问题是在一个带权图的两个顶点之间找出一条具有最小权和路径的问题,它是图论中一个经典的NP完全问题,用电子计算机需要指数级的时间内才能得到解决,本文基于分子生物技术并利用Adleman-Lipton模型给出最短路径问题的DNA算法,这个DNA算法理论上能在多项式的时间内解决这个NP完全问题。具体地对个城市的最短路径问题,首先将它视为一个具有顶点和边的图,并将顶点,边分别用DNA链编码表示,边的方向通过顶点的编码获得;再将这些DNA链投放在试管中进行生物化学反应,利用DNA计算的高效并行性,通过基本的生物实验操作最后得到最短路径问题的解,其过程的复杂度为O(n)。该算法的创新之处在于表示城市和路径的DNA链长度的设计以及在操作中巧妙的消除了路径途经城市数目不同的影响,能使我们在合理小的范围内寻找最短路径问题的解,较大地简化了问题的复杂度。     

基于多智能体系统仿真的最短路径规划

针对有向图最短路径问题,提出了通过多智能体系统仿真的方式求解有向图最短路径的方法.首先,把有向图中的节点、边都建模为智能体对象;其次,设计机器人智能体从源点沿有向边移动对节点实现遍历,利用机器人智能体的自我复制能力和边断开能力实现对节点的并行访问并保证任何节点最多被访问一次;最后,利用Anylogic开发多智能体最短路径仿真系统进行方法验证.仿真结果表明,多智能体最短路径仿真系统能快速找出有向图最短路径,算法时间复杂度与Bellman-Ford算法相同.     

罚转向网络最短路径研究

建立和研究了具有转向惩罚值的网络模型。在引入了罚转向网络符号及规则后，对所建立的罚转向网络模型的有关最短路径的性质进行了研究，提出了以标记法为基础的求解最短路径的算法，最后给出了应用该算法的一个简单实例。     

基于区分通道可用度保护的WDM环网设计

提出了区分通道可用度概念,并利用其为波分复用环网提供多样性保护.无保护连接可以重用保护连接的保护波长,如果前者的工作路由和后者的保护路由重叠,并且2个连接的工作通道不可用度之和不超过无保护连接的最大可接受不可用度.利用最短路径方法为每个连接寻找工作路由,利用M arkov模型计算通道不可用度,冗余不可用度越小的无保护连接越先分配保护波长.利用区分可用度方法可以在满足每个连接可用度要求的同时,减少环网所需的波长里程数.仿真结果表明,随着连接的可用度要求降低,环网使用的波长里程数减少,重用的波长里程数增加.     

改进的Dijkstra算法在动态路径引导中的实现

城市路径引导系统的一个非常重要的作用就是能动态预测车辆在某路段上的行驶时间,即动态的最短路径。在传统的最短路径预测方法中,往往不能体现出来动态的特点。通过对城市交通路网的建模,利用一种改进的Dijkstra算法可以较好地实现动态路径引导算法。     

Spark-GraphX框架下的大规模加权图最短路径查询

最短路径问题一直是计算机等学科的热点研究问题,常应用于社交网、交通网等诸多领域.图规模爆炸式的增长导致传统单机环境下的存储、查询已无法满足大规模图的处理需求.提出一种基于Spark-Graph X平台的大规模图最短路径查询方法(LSGSP-SG):首先利用经典算法对大规模图进行分割并标记,将割点的信息记录在文本文件中,然后利用大数据平台Spark的Graph X框架进行迭代式分布计算并进行各个计算机节点的消息通信及同步,最后返回最短路径查询结果.     

基于混合SA算法的智能汽车全局路径规划

针对目前智能汽车路径规划存在A~*算法规划的路径精度高却搜索耗时长、搜索耗时短但精度差的矛盾问题,提出了一种既保证搜索效率又可提高路径精度的混合连接SA算法.在原有连接方式的基础上,提出了一种新型的连接方式和S算法,设计了混合SA算法的切换机制,确保了SA算法可获取保证搜索效率的次优路径.进行了路径规划单一地图仿真试验,验证了SA算法在不同的单一环境地图中,重复规划的路径具有一致性、耗时具有一定局限性;同时进行了路径规划普适性仿真试验,对比分析了混合连接SA算法与四连接A~*算法的各项性能指标.结果表明:在全局工况下,SA算法相比于四连接A~*算法,在保证搜索耗时优势的同时,提高了规划路径精度,尤其是在低百分比障碍物地图下,效果更为明显.     

一个低代价最短路径树算法

为了对最短路径树SPT（Shortest Path Tree）进行代价优化，提出了路径驱动的思想，主要是生成SPT时通过路径节点共享的方式来优化其总体代价。基于这个思想进行搜索过程优化，设计了一个路径节点驱动的低代价最短路径树算法LCSPT（Low—cost Shortest Path Tree Algorithm），这个算法生成的组播树在保证最短路径的同时降低了整个树的总体代价。仿真实验表明：LCSPT算法不但能正确地构造最短路径树，而且其构造的SPT总体代价与其它同类算法相比得到了最大限度的优化。