共查询到18条相似文献,搜索用时 46 毫秒
1.
随着网络规模的不断增大,经典算法(如Dijkstra等)效率越来越低.针对这一问题,研究者们提出了许多近似搜索算法,但如何既能提高搜索效率又能保持准确性一直是一大难点.本文根据复杂网络的结构特性引入区域划分,同时改进树分解的构造,将图构造成一棵树进行搜索,得到了一个新的适合于复杂网络的最短路径近似算法.此外通过实例验证,该算法不仅在一定程度上降低了计算复杂性,而且保持了较高的近似准确性. 相似文献
2.
适合复杂网络分析的最短路径近似算法 总被引:3,自引:0,他引:3
基于互联网抽取的社会网络往往具有较大的规模,这对社会网络分析算法的性能提出了更高的要求.许多网络性质的度量都依赖于最短路径信息,社会网络等现实网络往往表现出"无标度"等复杂网络特征,这些特征指示了现实网络中最短路径的分布规律.基于现实网络的拓扑特征,提出了一种适合于复杂网络的最短路径近似算法,利用通过局部中心节点的一条路径近似最短路径,该算法能够方便地用于需要最短路径信息的社会网络性质的估算,为复杂网络的近似分析提供了一种新的思路.在各种生成网络与现实网络上的实验结果表明,该算法在复杂网络上能够大幅降低计算复杂性并保持较高的近似准确性. 相似文献
3.
在Dijkstra算法基础上,提出基于双向搜索的前N条最短路径算法,给出了相应的数据结构和算法实现,同时针对网络的动态性,对静态算法作了适当的改进。 相似文献
4.
公交车网络的最短路径算法及实现 总被引:3,自引:0,他引:3
最短路径问题是图论研究中的一个经典算法问题.旨在寻找图中任意两结点之间的最短路径。一般在交通道路网络中最短路径问题就是单纯地求解两点问的最短路径。为了保证实用性,公交车网络的最短路径算法以转车次数最少为首要目的。文中借鉴广度优先搜索的思路来求解最短路径,即逐个找出经过起点站和终点站的车次以及这些车次沿途可转的车次。首先说明了算法的计算机实现方法,再举例详细说明其过程,最后指出此算法的扩充用途。 相似文献
5.
6.
最短路径问题是图论研究中的一个经典算法问题,旨在寻找图中任意两结点之间的最短路径.一般在交通道路网络中最短路径问题就是单纯地求解两点间的最短路径.为了保证实用性,公交车网络的最短路径算法以转车次数最少为首要目的.文中借鉴广度优先搜索的思路来求解最短路径,即逐个找出经过起点站和终点站的车次以及这些车次沿途可转的车次.首先说明了算法的计算机实现方法,再举例详细说明其过程,最后指出此算法的扩充用途. 相似文献
7.
张明伟 《计算机光盘软件与应用》2010,(12)
Dijkstra算法是经典的求解单源静态最短路径问题的理论基础,但是在实际应用中存在一些不足之处,影响了算法的效率.本文首先介绍了Dijkstra算法,分析了该算法的优点与缺点,并在此基础上提出求解最短路径在数据存储和搜索上的一种改进算法. 相似文献
8.
提出一种更新移动目标最短路径树的近似算法来避免重新生成整棵路径树。算法使用了局部图的思想,使每次迭代更新尽量少的节点来减少代价。实验证明算法具有良好的效率、近似度和可伸缩性。分析了如何调整算法,以便在近似度和效率之间实现平衡。 相似文献
9.
10.
11.
庄明 《小型微型计算机系统》2008,29(6):1062-1065
提出在深度优先搜索过程中采用标记当前搜索位置离起始点最短距离方法,有效地实现了求解复杂网络的单源最短路径问题.通过对运算效率的分析,表明该算法通过优化改进可以达到理想的运算效率;模拟了不同规模的含障碍网络(182~13770个节点),其单源最短路径的求解运算平均效率为O(kV)(其中k≤18,V为路节点数),等同于用改进后的最优Djkstra算法求解效率O(mlogn).报告了一个具有现实应用价值和更具潜在研究价值的深度优先搜索智能算法. 相似文献
12.
13.
作为图论中的基本操作之一,最短路径查询已被广泛应用于路径规划、GPS导航和个性化推荐等基于道路网的相关应用中.针对道路网中在线最短路径查询所面临的计算成本高、查询速度慢等问题,现有方案通常采用缓存技术来优化其性能.考虑到道路网的边权重具有频繁变化的特性,现有工作未能有效地实现缓存数据的快速更新,忽略了缓存数据的时效性,从而导致缓存命中率不高.鉴于此,首先提出一种新的缓存存储结构,能够有效平衡最短路径的整体查询速度与缓存数据更新速度之间的关系;其次,结合路径共享能力及路径多样性设计了新的缓存存储策略,优化缓存收益,继而提高缓存命中率;最后,提出基于缓存的时变最短路径查询(cache-based time-varying shortest path query, CTSPQ)算法.在真实数据集上的实验结果验证了CTSPQ算法的有效性和可扩展性. 相似文献
14.
基于混沌神经网络的最短路径路由算法 总被引:4,自引:0,他引:4
飞速发展的计算机网络对路由算法的反应速度提出了更高的要求.神经网络作为一种新的组合优化计算工具。在网络路由方面的应用得到较大关注.与传统的采用串行执行方式的算法相比,神经网络路由算法以其固有的并行执行方式,以及潜在的硬件实施能力,将成为这一领域的有力竞争者.由此提出了一种基于混沌神经网络的最短路径路由算法.仿真结果表明,该算法能有效克服Hopfield神经网络易陷入局部最优解的缺点,并且在收敛速度方面有了很大改进. 相似文献
15.
时间依赖的网络中最小时间路径算法 总被引:37,自引:3,他引:37
时间依赖的网络与传统网络模型相比更具有现实意义,具有广泛的应用领域,交通网络和通信网络可以抽象为时间依赖的网络模型,当模型中弧的工度是时间依赖的变量,最短路径问题的求解变得非常困难,早期的研究者通过具体的网络实例认识到传统最短路径算法在这种情况下是不正确的,因此给出限制性条件使得传统最短路径算法是有效的。该文从最短路径算法的理论基础入手,从理论上证明了传统最短路径算法,如Dijkstra算法和标号设置算法,在时间依赖的网络上不能有效地求解最短路径问题,并且,在没有任何限制性条件下,给出了时间依赖的网络模型,理论基础,求解最小时间路径的优化条件和SPTDN算法,从理论上证明了SPTDN算法的正确性,算法的实验结果是正确的,最后给出了时间依赖的网络应用实例。 相似文献
16.
17.
最短路径分析是GIS网络分析的基础。传统的最短路径算法中,比较经典的算法是Dijkstra算法。由于地理信息系统中的数据具有不确定性、数据量庞大等特点,因此采用传统的Dijkstra算法进行最短路径分析就不适应。为此本文分析了传统网络中的最短路径算法-Dijkstra算法在时变权值网络结构中的局限性,给出了一种适应于时变权值网络的最短路径算法,并且利用改进的邻接表作为存储结构对算法进行了优化。 相似文献
18.
低代价最短路径树是一种广泛使用的多播树.它能够在保证传送时延最小的同时尽量降低带宽消耗.在DDSP(destination-driven shortest path)算法的基础上,通过改进节点的搜索过程,提出了快速低代价最短路径树算法FLSPT(fast loW-coSt shortest path tree).该算法构造的最短路径树与DDSP算法构造的树具有相同的性能,但其时间复杂度低于DDSP算法.随机网络模型的仿真结果表明,FLSPT算法效率更高. 相似文献