共查询到20条相似文献,搜索用时 265 毫秒
1.
基于栅格模型的路径规划是移动机器人的一个重要研究内容.在栅格模型中使用Dijkstra算法进行路径规划,可以一次规划出从初始节点到其他所有节点的最短路径,但是同时存在计算量大、规划时间长、扩展节点个数多等缺点.根据栅格模型及其中最短路径的特性,提出了一种减少扩展节点,进而降低计算代价的方法,并将其用于Dijkstra算法在栅格模型中的具体实现上. 相似文献
2.
基于动态交通信息的最短时间路径规划方法属于导航领域的最短路径问题。本文采用Dijkstra算法探讨基于实时交通信息的最短时间路径规划方法,通过对空间数据的存储管理和对网络拓扑结构的组织,提高最短路径计算速度,实现动态导航的最短时间路径规划。 相似文献
3.
基于栅格法的虚拟人快速路径规划 总被引:2,自引:0,他引:2
在栅格中使用经典的Dijkstra算法进行路径规划有计算量大,规划时间长、进行扩展判断的节点个数多等缺点.栅格的组织结构决定了栅格中最短路径的特性--组成最短路径的各线段间的最小夹角为90°.根据栅格及最短路径的特性,提出了一种在栅格中使用Dijkstra算法规划路径时减少扩展节点的个数,进而缩短规划时间、降低计算代价的算法,并将其用于虚拟人的路径规划.实验验证了算法的可行性和有效性. 相似文献
4.
考虑到粮食具有散粒性,采用履带式机器人可以在粮面上平稳运行。设计一种基于机器人操作系统ROS和激光雷达的粮面巡检机器人导航系统,使用基于粒子滤波的Gmapping算法构建栅格地图。全局路径规划使用改进启发函数的蚁群算法,加速收敛速度获得最短路径,应用动态窗口算法以关键点作为中间目标点规划局部路径,实现路径规划以及实时避障功能。经过仿真实验证明,该方案可以准确建立地图,改进的导航算法能够进行路径规划和避障,该方案设计具有可行性和有效性。 相似文献
5.
6.
从分析城市道路网地理相关性特征入手,研究利用道路网的空间特性信息来解决道路网中两点间的最短路径问题.通过建立体现道路网空间特性的数据模型,根据两点间直线距离最短的原理,提出一种道路网两点间最短路径的算法,利用VC 进行了算法实现和最短路径的可视化显示.实验结果证明:利用空间特性信息可以有效地减少最短路径的搜索花费,同时算法的实现和最短路径的可视化不须依赖地理信息系统平台,具有较好的可移植性和实用性. 相似文献
7.
GIS中最短路径搜索算法 总被引:15,自引:0,他引:15
李春葆 《计算机工程与应用》2002,38(20):70-71
文章讨论了一种在GIS环境下的最短路径规划算法,它根据用户给出的起始结点与目标结点以及必经结点序列和避开结点序列在建立的搜索图基础上分段查找最短路径,最后生成满足用户约束条件的最短路径。 相似文献
8.
在分析传统最短路径算法数据结构的基础上,提出并实现了一种以半边数据结构存储网络拓扑数据的最短路径算法。该算法充分利用半边数据结构存储格式紧凑、操作直观高效等方面的优点,采用较传统方法不同的路径检索方式,实现了快速计算网络中任一结点到其他所有结点的最短路径。实验表明,基于半边数据结构的最短路径算法可以大幅度提高网络中最短路径的计算效率,其性能在网络结点显著增多时愈加明显。 相似文献
9.
针对路网信息不完备性、路网结构特征和驾驶员习惯等因素,研究最短路搜索问题。提出以全局规划和局部规划相结合的动态最短路混合规划方法:全局规划中,基于参数d/l(起终点距离d与平均路段长度l之比),确定路径搜索区域的椭圆方程,运用Dijkstra算法生成静态的全局最短路径;局部规划中,结合路网结构特征、突发事件影响范围,提出改进Bug算法,以避免车辆进入全局最短路径上发生的紧急事件或严重堵塞区域,实现动态诱导。仿真实验结果表明,混合规划方法能在路网信息不完备条件下实现最短路径动态诱导,有效避开拥堵区域。 相似文献
10.
动态拓扑网络最短路径启发式算法 总被引:1,自引:0,他引:1
针对动态拓扑网络的最优路径规划中存在的问题,研究了最短路径搜索算法的快速实现技术,提出了一种启发式快速最优路径规划算法.在分析经典迪杰斯特拉最短路径搜索算法和A*启发式搜索算法的基础上,利用椭圆曲线参数设定启发函数初始值,进一步缩小搜索范围.采用二叉堆结构来实现路径计算过程中优先级队列的一系列操作,从而提高了算法的执行效率.仿真试验结果表明该算法具有良好的性能. 相似文献
11.
设计了基于组件的电子地图显示软件,实现了电子地图基本操作功能及路径规划功能。可以在软件中实现地图放大、缩小、漫游、测距、图层控制、鹰眼视图、全图显示、坐标显示等功能,作为电子导航显示软件,利用DOkstra算法可以在地图中求解任意两点之间最短距离,利用蚁群算法对道路进行了路径规划,在有结点约束的条件下求解一条较优路径。因蚁群算法求解路径规划问题存在求解速度慢问题,利用Cilk++并行模型对蚁群算法进行了并行化。 相似文献
12.
13.
14.
15.
标号算法是交通网络最短路径算法族中应用最广泛的算法,其中以各种D ijkstra算法为核心的标号设定算法是各种商用G IS平台网络分析算法的首选。然而,同样隶属于标号算法的标号改正算法在交通网络路径分析中却罕有应用。为了将标号改正算法应用于交通网络路径分析,首先讨论了标号算法的基本结构;然后分析了标号设定算法和标号改正算法的实现过程、复杂度、运行特点和适用性,进而选择了标号设定和标号改正算法中公认的几种优秀算法———基于逼近桶结构和改进四叉堆的D ijkstra算法(D IKBA与D IKQH)以及Pallottino算法(TWO-Q),并结合交通网络邻接链表结构予以实现;最后采用城市交通网络数据,对几种算法的实际运行效率进行了对比试验,试验结果表明,标号改正算法和标号设定算法优点各异;由于交通网络路径算法的应用越来越强调动态性和网络适用性,而且标号改正算法较之标号设定算法具有更大的适用范围,因此其在交通网络路径分析中具有极大的应用潜力。 相似文献
16.
基于城市道路网的最短路径分析解决方案 总被引:23,自引:0,他引:23
近年来GIS对网络分析功能的需求迅速增长.网络分析中的一个关键问题是最短路径问题,它作为许多领域中速择最优问题的基础,在交通网络分析系统中占有重要地位.由于最短路径分析常用于汽车导航系统以及各种城市应急系统(如l10报警、l19火警以及120急救系统),本文针对城市道路网的特点,提出了一种实用、高效的最短路径分析解决方案. 相似文献
17.
This paper considers the generation of the origin–destination (OD) matrix, basic data in any vehicle routing or traveling salesman problem. An OD matrix must be generated by calculating the shortest paths between some nodes. Candidate methods for this are repetitive use of one-to-all shortest path algorithms such as Dijkstra’s algorithm, use of all-to-all shortest path algorithms such as the Floyd–Warshall algorithm, and use of specifically designed some-to-some shortest path algorithms. This paper compares the performance of several shortest path algorithms in computing OD matrices on real road networks. Dijkstra’s algorithm with approximate bucket data structure performed the best for most of the networks tested. This paper also proposes a grouping-based algorithm for OD matrix generation. Although it is an approximation approach, it has several good characteristics: it can find the exact shortest distances for most OD pairs; it guarantees that all the calculated shortest path distance values have corresponding paths; the deviation of any distance from the corresponding true shortest distance is small; and its computation time is short. 相似文献
18.
XU Zheng-kai 《数字社区&智能家居》2008,(4)
最短路径算法问题是计算机科学、运筹学、地理信息系统和交通导航系统等领域研究的一个热点。Dijkstra算法用于计算一个节点到其他所有节点的最短路径,得出最短路径的最优解,但它的效率是一个很大的问题。组合算法在Dijkstra算法的基础上,利用层次策略与准备算法,计算出最短路径,解决了常用最短路径算法中相关数据量大、耗用资源多、执行效率低等关键问题。 相似文献
19.
20.
许正凯 《数字社区&智能家居》2008,(2):667-671
最短路径算法问题是计算机科学、运筹学、地理信息系统和交通导航系统等领域研究的一个热点。Dijkstra算法用于计算一个节点到其他所有节点的最短路径,得出最短路径的最优解,但它的效率是一个很大的问题。组合算法在Dijkstra算法的基础上.利用层次策略与准备算法,计算出最短路径,解决了常用最短路径算法中相关数据量大、耗用资源多、执行效率低等关键问题。 相似文献