共查询到17条相似文献,搜索用时 62 毫秒
1.
公交车网络的最短路径算法及实现 总被引:3,自引:0,他引:3
最短路径问题是图论研究中的一个经典算法问题.旨在寻找图中任意两结点之间的最短路径。一般在交通道路网络中最短路径问题就是单纯地求解两点问的最短路径。为了保证实用性,公交车网络的最短路径算法以转车次数最少为首要目的。文中借鉴广度优先搜索的思路来求解最短路径,即逐个找出经过起点站和终点站的车次以及这些车次沿途可转的车次。首先说明了算法的计算机实现方法,再举例详细说明其过程,最后指出此算法的扩充用途。 相似文献
2.
通过理论分析,结合实际应用,在GIS节点数很大的数字地形图中,从完备性、最优性、时间复杂度、空间复杂度几种性能问题实例分析,较系统地总结出深度优先搜索(DFS)、广度优先搜索(BFS)、双向广度优先搜索(DBFS)、A★算法四种算法代价及优缺点. 相似文献
3.
一种基于动态负载均衡的路由算法 总被引:1,自引:0,他引:1
传统IGP仅基于最短路径算法来为数据流选择传输通路,对数据流的需求以及网络资源的动态变化未加以考虑,因此不具备均衡网络负载的能力。文中通过分析IGP的局限性,提出基于动态负载均衡的DLB-OSPF路由算法。该算法依据数据流的带宽需求和网络资源的使用状况来进行路由选择,并通过有效手段将数据流更合理地分配到能满足传输需求的链路上。经过示例分析表明,该算法不仅能减少网络拥塞,并且提高了网络资源利用率。 相似文献
4.
迷宫最短路径问题新算法 总被引:1,自引:0,他引:1
提出了求解迷宫最短路径问题的新算法,该算法抛弃了经典算法(深度优先搜索和广度优先搜索)中繁杂低效的递归、回溯思想。通过合理的变换,将原问题转化为迷宫路径深度图的生成问题。最后对算法进行了严谨的分析和实例测试,显示出该算法易于理解、易于编程、时间空间复杂度低等优点。 相似文献
5.
最短路径问题是图论研究中的一个经典算法问题,旨在寻找图中任意两结点之间的最短路径.一般在交通道路网络中最短路径问题就是单纯地求解两点间的最短路径.为了保证实用性,公交车网络的最短路径算法以转车次数最少为首要目的.文中借鉴广度优先搜索的思路来求解最短路径,即逐个找出经过起点站和终点站的车次以及这些车次沿途可转的车次.首先说明了算法的计算机实现方法,再举例详细说明其过程,最后指出此算法的扩充用途. 相似文献
6.
姚婕 《计算机技术与发展》2005,15(1)
传统IGP仅基于最短路径算法来为数据流选择传输通路,对数据流的需求以及网络资源的动态变化未加以考虑,因此不具备均衡网络负载的能力.文中通过分析IGP的局限性,提出基于动态负载均衡的DLB-OSPF路由算法.该算法依据数据流的带宽需求和网络资源的使用状况来进行路由选择,并通过有效手段将数据流更合理地分配到能满足传输需求的链路上.经过示例分析表明,该算法不仅能减少网络拥塞,并且提高了网络资源利用率. 相似文献
7.
8.
针对节点负载不均衡和数据传输距离的问题,提出一种适用于异构网络的基于负载均衡和最短路径的分布式成簇算法DUBP(distributed and unequal clustering algorithm based on load balance and shortest path)。DUBP首先基于节点的能耗因子对网络动态分区,以均衡负载;然后结合网络拓扑结构和图论,利用Floyd算法求出节点间的最短距离作为路径因子;最后以节点的能量因子和路径因子作为辅助参数来竞争簇头,以避免低能量节点担任簇头,节省传输能耗。仿真表明,DUBP算法能显著延长网络寿命,有良好的适应性和能效性。 相似文献
9.
10.
11.
12.
13.
低代价最短路径树是一种广泛使用的多播树.它能够在保证传送时延最小的同时尽量降低带宽消耗.在DDSP(destination-driven shortest path)算法的基础上,通过改进节点的搜索过程,提出了快速低代价最短路径树算法FLSPT(fast loW-coSt shortest path tree).该算法构造的最短路径树与DDSP算法构造的树具有相同的性能,但其时间复杂度低于DDSP算法.随机网络模型的仿真结果表明,FLSPT算法效率更高. 相似文献
14.
针对目前大规模应用场景下多AGV运行路网的局部拥塞防止和负载均衡问题,提出了使用负载均衡改进的A*算法进行路径规划的方法。在计算AGV运行代价时,摒弃了传统A*算法只考虑单一运行路程的评价函数,引入了运行路程结合区域负载作为新评价函数的方式。在几乎不增大运行路程的前提下,实现了AGV运行路网的区域负载均衡。采用了单向多入多出以及双向多入多出路网模型进行仿真验证,改变路网规模以及负载系数进行多次仿真实验,结果表明改进算法可以有效地均衡路网负载,极大提高了AGV系统整体运行效率。 相似文献
15.
16.
17.
随着服务器集群系统大量应用于各中小企业的信息系统中,传统均衡算法一方面由于局限性达不到企业的要求,另一方面大部分中小型企业也无法承受昂贵的硬件负载均衡器费用,本文提出了一种集群系统的透明动态反馈负载均衡算法(TDLBA)。该算法充分考虑集群系统中多种资源(CPU、内存、I/O和网络带宽等),采用双机热备份负载均衡器,服务器节点周期动态反馈方法,同时引入一个负载冗余以动态调整节点负载分配,从而达到尽量简化负载均衡器的任务分配算法、最大限度满足系统最大吞吐率和提高系统响应时间的目标。测试表明,该算法有效的提高了系统服务性能,且优于静态分配算法和Pick-KX算法。 相似文献