首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 234 毫秒
1.
针对传统A*算法搜索速度慢和规划路径不够优化的缺点,引入可扩展节点,对A*算法流程进行改进,以减少时间和空间复杂度,提高搜索效率,并对规划路径进行优化处理,以有效的缩短路径。对存在凹形障碍物的地图,采用后退—尝试的方法解决路径规划的失败问题,使之绕过凹形障碍物取向目标点,达到输出最短路径的目标。  相似文献   

2.
针对移动机器人未知环境路径规划问题,基于动态自组织特征映射网络提出了一种自组织网络动态生成A*的算法(dynamic growing self-organizing map with A*,DGSOM_A*),并将其应用于移动机器人地图创建和路径规划.该方法利用Mobotsim二维仿真软件构造了环境模型,机器人通过无碰自由巡航获取环境信息,然后把上一步得到的环境信息作为DGSOM_A*算法样本通过SOM神经元自主生长进行地图创建,生成以少数SOM图神经元分布描述环境特征信息的拓扑地图,最后完成起始点到目标点的导航任务.实验结果表明,相比传统的SOM算法,基于DGSOM_A*算法机器人能有效地通过对环境地图的绘制熟悉复杂环境并能实现最优路径选取.  相似文献   

3.
一种实用的最短路径求解算法   总被引:5,自引:0,他引:5  
本文从地图上城市交通网络中道路路段间的地理关联关系入手,探讨了一种求两节点间最短径的新算法,在地理信息系统软件MapInfo中编程实并取得良好的效果。该算法的时间花费极少,有极强的实用性,并有继续研究的价值。  相似文献   

4.
考虑实际道路网络的特殊性以及最短路径算法对路网信息的要求,运用对偶图法的基本思想对前向关联边结构进行了改进,提出了一种能够提高路径优化算法实时性的路网表达方法与数据存储结构,并用Dijkstra和A*最短路径算法进行了验证。结果表明,这种方法在清楚表达转向限制、消除结点权重的同时,由于两个指针数组的引入,使得算法可以迅速而准确地定位相关结点的位置,从而减小了搜索空间,降低了最短路径算法的时间复杂度,提高了最短路径的搜索效率。  相似文献   

5.
针对路由选择对网络性能起重要作用,提出了星图上任意两点之间的最短路径算法.运用群论的循环置换的性质证明了两点之间的距离公式,给出了两点之间所有最短路径个数的一般代数表达式.  相似文献   

6.
提出一种最少边扰动算法,以解决如何在扰动最少边的前提下,以最小代价来使得一条特定的目标路径成为最短路径的问题。该算法基于最少边的最短路径扰动模型,通过引入每条边的权重扰动上限约束,提出了最少扰动边数-最小扰动成本的双目标混合整数规划问题,从而实现操纵网络节点间的最短路径。与以往的最小代价扰动算法相比,该方法降低了扰动的复杂性和扰动网络被察觉的风险。实验表明,最优解使扰动边数减少了约27%,具有更好的性能。  相似文献   

7.
串行算法的并行化是提高算法效率的一种有效途径,在分析最短路径算法特点的基础上,采用带重叠区的网络分割策略,提出了基于双向搜索的并行Dijkstra最短路径搜索算法.采用多粒度通讯方式进行进程间消息传递,能降低算法的通讯时间,并应用离散数学与理论计算研究中心(DIMAS)提供的美国路网数据进行试验.结果表明:采用带重叠区的数据分割策略适用于并行最短路径算法的求解;应用大粒度的多点接口(MPI)通讯方式能减少并行算法进程间的通讯时间;当通讯粒度为50时,MPI通讯所需时间是单粒度通讯模式的1/10左右.  相似文献   

8.
利用ArcGIS软件创建校园矢量图,并结合Floyd算法,解决校园中各地点间的最短路径问题。对Floyd算法从两个方面简化:对于插入的节点,先对其路径长度进行比较,若其到所求节点路径比所求节点对间路径长,则不需参与计算;引入序号矩阵记录使两顶点间的路径长度变短的中间节点序号。最后,在Matlab软件中编程实现,得出校园各地点间的最短路径,结果表明,该方法具有可行性。  相似文献   

9.
考虑了至多可以删除多少个顶点才能保证互连网络的连通。给出了网络的容错能力。根据Menger定理可以得到BC互连网络之间至少存在n条内部节点互不相交的路径。利用广度优先搜索的思想,给出了求任意两个节点之间的n条内部节点互不相交。且在两点间所有路径中是最短的n条路径的算法。该算法为网络故障直径的研究提供了依据。而且。在故障存在但是网络连通的情况下。可以求得网络中任意两节点间的n条最并行路径。提高了网络的容错能力。本文对提出的方法及算法的正确性进行了证明,为研究互连网络的性质提供了新的研究方法。  相似文献   

10.
路径规划算法是室内移动机器人应用中最重要的算法之一.根据室内移动机器人在动静态环境下实时避障规划出一条最优路径的要求,设计一种新的路径规划算法.通过删除冗余点并平滑路径的方式对A*算法进行改进,又将其与TEB算法相结合,实现从指定起始点到指定目标点的路径选择及移动.实验结果表明,利用该算法可得到耗时短、平滑的路径,实时...  相似文献   

11.
本文给出互连网络上的广度优先搜索算法,并将其应用到螺旋立方体上。给出了n维螺旋立方体TQn的直径的另外一种证明方法;该算法可能用来求解单源节点最短路径问题。为讨论新的互连网络拓扑结构的直径和故障直径问题提供一条新的思路。  相似文献   

12.
针对当前的无线传感器与执行器网络(WSAN)技术缺乏实时性能以及工业无线环境的动态性问题,基于Kautz图设计容错、实时、高效、可靠的先验式路由FRER,不需要维持路由表,只利用节点IDs,根据节点IDs的匹配长度快速找到目标节点的最短路径.当节点故障时,不需要进行路径重挑,根据自身ID与目标节点ID的匹配,上一跳节点能够快速找到剩余节点的最短路径.考虑路径的多样性,不局限于Kautz拓扑,利用邻居节点信息拓展网络中路径的多样性.考虑链路故障,基于链路可用性历史信息组合多路径,保证在链路故障情况下网络维持可接受水平的路由路径可用性.实验结果表明,与REFER和Debruijn图相比,FRER在实时性、容错性和可靠性性能上优于两者.  相似文献   

13.
复杂网络模型的研究主要集中在ER网络模型、小世界网络模型和无标度网络模型,其中ER网络模型是最经典的复杂网络模型之一。文章研究了节点数固定情况下的ER网络模型,根据网络内部边的动态演化特点,将节点数固定的网络模型进行了细分,给出了模型的生成算法,并模拟了算法生成的随机网络的平均路径长度和聚类系数。仿真结果表明,节点数固定的ER网络具有小世界特性,出现这种小世界特性的主要原因是由于网络内部边的异质性,而与网络的节点数变化没有必然联系。  相似文献   

14.
针对通信网络中的路由问题,提出了一种虚令牌动态路由算法,并用Hopfiedl神经网络实现该算法。该Hopfield神经网络,其神经元之间的连接强度固定不变,通信网络的物理逻路值和呼叫请求被反映到神经元的偏置电流中,地用硬件实现。同时,当通信网络中的业务量发生变化时,算法能够自动调整最短路径与负载均衡之间的关系,计算机仿真结果表明,该算法能接入更多的网络连接。  相似文献   

15.
QoS路由问题被证明是一个NP-C问题,而传统的路由算法很难有效地解决NP-C问题。该文提出了一种基于蚁群算法、用于解决带宽和时延约束问题的QoS单播路由算法,利用蚁群算法中蚂蚁通过信息素寻找最优路径的机制,并以网络吞吐量和数据报的平均时延等性能为最优的准则,来定义蚂蚁的转移概率、路由表和信息素更新方式,实现基于蚁群算法的路由选择算法.这种算法具有较强全局最优解搜索能力,较强的灵活性,以及潜在的并行性。  相似文献   

16.
本文首先提出一种有向网络中点对间加权约束的最小用连接问题,当点对数为1时即为约束最短路问题,因此这是一个NP-C问题,本文设法在原有网络基础上构造出一个新的2维网络,然后利用约束最短路问题的算法给出一个点对数为2时的多项式时间近似方案(PTAS)。  相似文献   

17.
基于信息融合的故障行波定位网络算法   总被引:1,自引:0,他引:1  
提出一种基于整个输电网行波信息的故障定位算法.通过分析故障行波到达电网中各变电站的时间关系,运用最短路径原则将复杂的输电网络简化成无环网的辐射型网络,将远端变电站记录的初始行波到达时间折算为故障线路出口侧变电站的初始行波到达时间.通过剔除无效时间数据,并对所有折算得到的有效初始行波到达时间进行融合处理,实现基于整个输电网的故障行波定位.该算法有效解决了电网中某台行波定位装置时间记录不准确或故障导致的故障定位失败问题.仿真结果表明,该算法具有较高的可靠性、准确性,绝对误差不超过100m.  相似文献   

18.
Recently K.Chris studied single-machine schedu-ling with time windows(STW)[1].In project manage-ment,the CPM algorithm computes a time windowwhich defined by the early start and late finishes timesfor each activity.In fact,activity slack is attained bytim…  相似文献   

19.
设想了一个高速网中动态路由选择法,适合于宽带网的路由选择,可将路由选择与拥塞控制在网路趋于拥挤时有机地结合起来.在轻负载的情况下,此方法即为最短路由(最小转接段数)计算法,而当最短路线上变得拥挤时,源发结点总是尽可能地利用其它多条候选路线以便疏散负载和降低分组丢失,提高设备利用率,以求得最优的流量分配.  相似文献   

20.
随着网络功能虚拟化的发展,为带有服务功能链限制的数据流的传输选择最短路变得更加灵活也更加重要。已有的算法都是在单个域内为流选择满足服务功能链限制的最短路。而在多域或者说分布式的网络中,各个成员网络彼此之间的信息往往是不共享的,因此,利用原有算法计算出的最短路可能不再是真正的最短路。该文提出了一个新的算法,解决了跨域的流的传输问题,使得成员网络可以在保护了自己内部的隐私信息的同时为数据流选择成本最低路径。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号