共查询到18条相似文献,搜索用时 171 毫秒
1.
针对单源最短路径Dijkstra 算法效率低的问题, 基于地理信息系统(GIS: Geographic Information System),提出距离均衡的社区分析网络分割方法。将GIS 中道路网络分割降解为距离均衡的社区网络, 再利用限制分层算法, 通过淘汰不太可能出现在最短路径上的节点, 限制GIS 中最短路径的搜索区域, 以降低算法的复杂度。实验结果表明, 优化后的算法可有效减少搜索节点数, 与经典算法相比, 其运行效率有所提高。 相似文献
2.
大规模网络最短路径算法的优化及实现 总被引:1,自引:0,他引:1
求解大规模复杂网络的最短路径问题由于其计算速度慢、需耗费的存储空间大,是与地理信息相关的应用系统经常遇到的瓶颈问题.在深入分析各种常用最短路径算法基础上,基于经典Dijkstra算法,从时间和空间优化角度,实现一种计算任意2点间最短路径的优化算法.初步实验表明,优化后的算法在处理大规模复杂网络的最短路径问题时比经典Dijkstra算法在计算时间上缩短了80%,在耗费的存储空间上减少了将近一倍. 相似文献
3.
城市应急指挥系统要求在事故发生时,计算出到出事地点的最佳路线的最短时间,其核心算法仍是最短路径算法.针对实际的城市道路网特点,对道路网络模型、道路拓扑结构和数据库结构进行构建.以优化的数据存储结构为切入点,在分析了经典的Dijkstra最短路径算法的计算速度瓶颈的基础上,提出了基于方向性的空间最优路径算法,使该算法具有更高的效率. 相似文献
4.
基于物流配送系统的运输路径分析及应用 总被引:1,自引:0,他引:1
物流配送系统中运输路径的优化研究对于节约物流成本、提高物流效率有着重要的意义。经典Dijkstra算法在求解最短网络中两点间最短路径时,需要计算大量与最短路径无关的结点间的路径。占用了大量计算机的内存。本文在此基础上提出了改进算法,该算法避免使用含有大量无穷值的关联矩阵,节省了内存,使之更适合处理带有拐向限制和包含大量结点信息的最短路径问题。 相似文献
5.
基于启发式策略的最短路径算法 总被引:6,自引:0,他引:6
在讨论经典Dijkstra算法和启发式策略算法(A^*,矩形算法等)的基础上,提出一种基于Dijkstra算法的动态方向限制搜索算法用于求解道路网络中两节点之间最短路径.该算法结合人类的搜索思路和动态灵活的处理方式,对最短路径算法的搜索策略进行改进,动态改变搜索限制区域,减少计算时间.该算法不仅可以单独提高计算最短路径的效率,而且与其他算法结合起来还可取得更好的效果.实际结果证明动态方向限制搜索算法比经典Dijkstra算法减少近50%的搜索节点数和搜索时间. 相似文献
6.
针对无人艇海上巡逻路径规划问题,提出了一种A~*算法与蚁群算法相结合进行最短巡逻路径优化的方法.在传统A~*算法的八角度搜索基础上,设计了一种多角度A~*算法以获得更短的两点之间可行路径,并以A~*算法搜索结果构建任意两个巡逻点之间的最短路径网络.结合最短路径网络建立多点巡逻路径规划问题的目标函数,利用蚁群算法进行求解以获得全局最优的巡逻路径.针对巡逻路径转折角较大的问题,提出了一种平滑算法以获得更符合实际航行需求的平滑路径.仿真结果表明:该方法有效地去除了冗余节点,缩短了路径长度,提高了路径平滑度,规划出了一条更优的无人艇巡逻路径. 相似文献
7.
为提升大规模网络全源最短路径的求解效率,基于重优化理论提出了一种快速的精确全源最短路径求解方法——RASP(reoptimization-based all-pairs shortest path)算法.分析了异源最短路径树间的相关性和差异性;在已知单源最短路径树的基础上,基于重优化理论实现了异源最短路径树间的高效转换,进而得出高效求解全源最短路径的RASP算法;理论证明RASP算法的时间复杂度为O(3n~2+2nm).实验测试表明:无论是在稀疏还是稠密网络上,RASP算法都能有效地超越Floyd算法、n次Dijkstra算法及其改进算法. 相似文献
8.
车辆导航系统的最基本功能是最短路径的搜索,车载导航是单源单目标的最短路径算法的重要应用之一.传统的Dijkstra算法是一种典型的单源最短路径算法,因为实际系统的实时要求,有必要改进Dijkstra算法.基于对时间和空间复杂度的分析,提出一种新型的Dijkstra改进算法,具有高效性.其改进分3个方面:采用邻接表作为道路网络拓扑的存储结构;利用二叉堆实现优先队列;根据节点的分布情况将搜索过程分为几个阶段,引入了动态限制搜索区域机制.最后在实际道路网络中的测试及仿真结果表明了改进算法的可行性和优越性. 相似文献
9.
10.
葛莉 《湖北民族学院学报(自然科学版)》2012,(3):278-280
针对路径规划问题,论述了道路层次划分模型和多尺度道路网数据库的建立,提出了构建多级道路网拓扑结构的方法,在研究道路网络特征上,通过建立道路网模型,综合各路段的权值,应用一种改进的Dijkstra算法对道路进行最短路径分析;并给出了道路网络中多源最优路径的选取问题,得到了所要解决的多源最优路径问题. 相似文献
11.
为了解决现有交通时变网络(网络中的路权为时间的函数)模型中计算所得的最短路不稳定的问题,构建符合首进首出原则的时变网络,进而将时变网络扩展为一系列静态网络,并在扩展的静态路网上应用A*算法求解时变最短路;同时,为满足用户多重喜好,借助道路延误风险分析,设计有约束的时变A*算法,在路径寻优过程中对高延误风险路段进行启发式规避,从而实现在绕行许可范围内有效减少延误风险的可靠路径的快速搜索。数值试验结果表明:本算法由于利用了离线计算的信息,大大增加了有约束的动态A*算法的效率;考虑了阻塞发生的可能性,提高了导航的准确性,减少了出行延误风险;该方法具有路径搜索速度快、可有效避开延误高风险路段的优点。 相似文献
12.
路网车流径路优化调整中的最短径路算法 总被引:1,自引:0,他引:1
目前铁路车流径路基本上都是按照路网的最短路径来安排的,首先一般都采用Dijkstra算法计算最短路径,然后参考相应区段的能力限制,对车流进行分配,对车流量超过能力的区段重新进行车流调整,这时需要重新计算新条件下两点间最短路径,一般仍采用Dijkstra算法重新计算两点最短路径,这大大地浪费了前期的计算最短路径的信息,增加了计算工作量,本文采用A*算法作为一种启发式算法,可以克服这一缺陷。 相似文献
13.
提出一种基于最短路径的QoS度量并行算法(QPAS)的两级并行算法。将多重链路网络按连接规则划分为若干网络分区,利用QPAS算法并行计算出每个分区内的QoS路由,并将路由结果发送给相应的分区处理器,最终由分区处理器调用最短路径并行算法计算出分区间代价最小路径。最后研究了路由更新频度。实验结果表明,基于QPAS的两级并行算法的时间复杂度更低,适用于有限节点网络的路由寻优。 相似文献
14.
公交网络最优路径的一种改进求解算法 总被引:3,自引:2,他引:3
通过对多种公交网络中求解最优路径算法的分析,提出了一种考虑公交线路票价变化,并以总行程时间最短与换乘次数最少相结合为原则的公交路径寻优新算法.同时对公交换乘中换乘点的选择、步行时间及等车时间作了较详细的分析.以一个算例对新算法的有效性进行了验证. 相似文献
15.
基于GIS的公交乘客出行路径选择模型 总被引:85,自引:0,他引:85
公交乘客出行路径选择模型是公交乘客信息系统的关键技术。本文通过对公交乘客出行心理的研究,结合地理信息系统(GIS)的特点,提出了以换乘次数最少为首要目标、出行距离最短为第二目标的基本GIS的公交乘客出行路径选择模型。为提高路径搜索效率,模型中提出了GIS方向估价函数的概念。在南京市实际公交网络上的试算结果表明该模型实用、高效。 相似文献
16.
在大型网络中两节点之间的最短路径常常不止一条,而且在带限制条件的路径选择等应用上,常常需要找出多条最优或近优的路径.一些经典的单源最短路径算法,如Dijkstra算法,能找出一条从起始点到目的点的最短路径,但并不能求解两点之间的所有最短路径.本文给出了最短路径子图的概念,用于存储图中两节点之间所有最短路径信息,能够节约存储空间.并给出了最短路径子图构造算法SPSG,其时间复杂度为O(n e),比同类算法时间复杂度更低.随机网络模型的仿真结果表明:SPSG算法效率更高. 相似文献
17.
带限制的网络是一类特殊的网络,如具有禁止通行限制信息的交通路网.由于此类网络的最短路径的求解是有后效性的,因此经典的Dijkstra算法等就无法用来解决此类问题.提出了一种路网带限制的交通网络最短路径建模方法.该方法将具有禁行限制的特殊网络转化成一个一般的网络模型,从而可用任一传统高效的算法完成对其最短路径的求解. 相似文献
18.
基于Mapinfo的最短路径混合搜索算法 总被引:3,自引:0,他引:3
在迪杰斯特拉(Dijkstra)算法的基础上,针对有较多节点和道路的大网络在求解最短路径时计算时间慢、扩展节点多的缺点,采用基于局部最优方向和A*算法的混合算法,利用局部最优方向法的结果,对A*算法的启发函数加以改造,可以减少扩展的节点数量,快速的找到一条最短路径.通过实验仿真证实了该算法的快速有效性. 相似文献