k(≤3)条渐次最短路径搜索算法的研究及其实现技术

目前针对“k(≤3)条渐次最短路径的问题”国际上尚无一种有效的解决方案,本文基于最短路径算法及背离路径的定义提出了一种递归计算方法,能够有效地解决某些实际问题中k条渐次最短路径的计算。对于算法中的环路问题,文中介绍了相应的方法予以消除。算法的复杂度分析及仿真实验表明本算法具有较好的性能。     

一个求解次短和渐次短路径的实用算法

求解第k短路径问题在决策支持系统和咨询系统中具有广泛的用途,本文基于Dijkstra算法,给出了一个求解次短路径和渐次短路径的算法,并且分析了算法的时间复杂度和空间复杂度。     

一个求解k短路径实用算法

求解k短路径问题在决策支持系统和咨询系统中具有广泛的用途,文章基于Dijkstra算法,给出了一个求解k短路径实用算法,并且分析了算法的时间复杂度和空间复杂度。     

复杂网络中最短K条路径问题的求解算法研究

以时间代价作为目标函数,针对复杂网络的优化问题进行研究,给出了目标评价函数模型的建立过程,提出了基于改进的A*算法求解复杂网络中最短K条路径问题的算法,并以城市交通为例,对算法进行了验证。实验结果表明所提出的算法可适用于一般多重图中最短K条路径问题的快速求解,具有广泛的应用价值。     

国际航线网络中K条最短路径算法改进与仿真

K条最短路径(KSP)问题是国际航线网络实际路径优化问题。通过对航线网络特征与K条最短路径算法的分析,研究了解决KSP问题的典型Yen算法。针对Yen算法求解候选路径占用大量运算时间的问题,提出一种改进Yen算法。改进Yen算法通过借助A*算法的启发式策略,减少了产生候选航线路径的时间,从而提高了算法的搜索效率并减小了算法搜索的规模。通过对国际航线网络实例的仿真,实验结果表明改进Yen算法能够快速求解国际航线网络中的KSP问题;同时,与Yen算法相比,运算效率提升了75.19%以上,能够为航线路径优化提供决策支持。     

求解k条最优路径问题的遗传算法

文章提出的任意两点间k条最优路径问题的遗传算法,采用节点的自然路径作为染色体编码,根据路径节点的连接实施染色体的交叉操作,将节点路径块作为染色体的变异基因块实施变异操作。算法结构简明,收敛速度快,可应用于求解大规模网络中的多条最优路径问题。     

前N条最短路径在网络中的应用

在Dijkstra算法基础上,提出基于双向搜索的前N条最短路径算法,给出了相应的数据结构和算法实现,同时针对网络的动态性,对静态算法作了适当的改进。     

最短路径搜索算法在交通系统上的应用

现有的交通出行服务系统在公众出行路线推荐方面,由于种种技术原因尚未真正满足广大群众的实际出行需要。通过对基于Dijkstra最短路径搜索算法的优化途径的分析,从算法本身和数据存储结构两个方面同时对此问题的解决方案进行了优化,提出了优化Dijkstra算法,并进行了必要的证明和适用条件论述。此方案应用到深圳市城市交通仿真系统中,取得了较为满意的效果,同时也给出了相关的测试数据。     

基于地理信息系统的最短路径搜索算法

最短路径问题（ＳＰ）是人工智能的一个活跃研究方向，也是交通网络分析系统的一个最基本问题，在理论和应用上有着广泛而深入的研究。本文从应用的角度，结合地理信息系统（ＧＩＳ）的特点，设计了一种新的数据存储结构，改进节点搜索方法，并建立一种简捷的估价函数，为进一步解决交通网络的综合分析打下了基础。     

一种新型最短路径搜索算法的研究

在深入分析Dijksdtra算法的基础上,考虑到图节点之间的拓扑关系以及Dijksdtra算法在计算节点权值时,与已着色节点不相关节点权值存在∞（即该节点不可见）,文章提出了盲目区域最短路径搜索算法,由分析可知计算量大为减少,算法更优。     

K优路径的一种求解算法与实现

求解最优路径的算法已经比较成熟,但国内外求解K优路径的算法还未见到。在作战指挥中,通常需要人们能够根据战场情况提供部队行动路线的多个方案供指挥员决策。针对这一军事需求,论文提出了一种求解K优路径的算法,给出了相应的数据结构和算法实现,同时从实现的角度对Dijkstra算法进行了改进。     

求带单一限制条件的单源多权最短路径的一个算法

给出了带单一 限制条件的单源多权最短路径问题的一个算法，并证明此算法是正确的；该算法中借用了C语言的特点，设计了一些独特的数据结构，这使得该算法设计和实现非常简单.     

带限制条件的多权最短路径近似算法

带限制条件的多权最短路径问题具有广泛的用途。该文针对有向图，给出了一个带一个限制条件的多权最短路径的近似算法并且分析了它的时间复杂度。     

带模糊权值的最短路问题及启发式算法

研究网络链路权值是三角型模糊数时的最短路问题,建立模糊线性整数优化模型。通过引入目标函数的正、负理想点和隶属度概念,将模糊优化问题转化为确定系数的单目标优化问题,并给出求解算法。该算法通过调整反映决策者意图的目标函数权系数,得到决策者的满意解。对14个节点的实例网络进行仿真,经过6步就能得到令决策者满意的解,表明了模型和算法的有效性。     

带均匀分布权值的最短路问题

最短路问题是网络设计中的一个基本问题,当前研究工作都基于边的权值是确定的这一假设。论文研究边的权值是一区间数时的最短路问题,利用优化理论,建立了目标函数系数在区间上均匀分布的模糊线性整数规划模型。通过引入正、负理想点概念,将模型转化为具有确定系数的单目标优化问题,给出了求解算法,并证明了算法的时间复杂性是多项式时间的。仿真实例说明了模型和算法的有效性。     

基于ITS的加速最短路径搜索算法研究

文章从路径搜索的基本原理入手,首先介绍了经典Dijkstra最短路径搜索算法,分析比较了基于堆结构和基数堆结构的Dijkstra算法的搜索效率,从而提出了采用多层地图和分级搜索技术来实现对最短路径搜索空间的控制策略和算法,结合湛江市区电子地图进行对比实验,该算法有效地解决了最短路径搜索效率的问题。     

VC环境下遗传算法在网络最短路径优化中的设计与实现

针对网络最短路径的有效智能求解,设计了智能算法——遗传算法在基于Visual C++6.0平台下对网络最短路径问题的实现方案,阐明了遗传算法在求解网络最短路径问题中包括编码、种群生成和遗传算子的具体步骤。通过实验,验证了设计方法的可行性和有效性,同时,该方法具有一定的理论意义和现实价值。     

基于递归算法的最短跳数路径的RSS测距算法

多跳无线传感网络中的多类应用均需要准确的定位算法.为了降低定位成本,常采用基于接收信号强度(RSS,received signal strength)测距,为此,提出基于递归算法的最短跳数路径的RSS测距算法RFSPR(recursive function shortest path-based ranging).RFSPR算法首先利用递归函数搜索源节点与目的节点间所有具有最短跳数的路径,然后通过RSS测量这些最短路径的距离,最终将所有最短路径距离的平均值作为源节点与目的节点间距离的估计值.最后,将RFSPR算法与现存的同类算法进行了对比分析.实验结果表明RFSPR算法具有更低的测距误差.     

改进蚁群算法在机器人路径规划上的研究

基于蚁群算法在路径规划过程中出现收敛速度慢、易陷入局部最优,且在复杂环境下的寻优能力弱等缺陷,提出了一种适用于机器人路径规划的改进蚁群算法.在预规划路径基础上建立初始信息素矩阵,避免算法前期盲目搜索,提高搜索速度;将改进蚁群算法和A*算法进行有机融合,进一步提高蚁群算法搜索方向性和收敛速度.制定信息素更新规则时引入拐点...     

Dijkstra最短路径算法分析与改进

Dijkstra算法是计算最短路径的经典算法,在对该算法分析的基础上,对其进行了优化和改进。其一是对数据存储方式进行了改进,其二是对辅助向量采用堆排序改进。通过优化降低了内存消耗,搜索效率明显提高。