共查询到15条相似文献,搜索用时 375 毫秒
1.
2.
在基于四叉堆优先级队列的改进型Dijkstra 最短路径算法的基础上,进一步提出了利用交通网络的空间分布及方位特征构造限制区域的时间最短路径算法。在对城市交通网络空间分布特征进行统计分析的基础上,针对具体的起、终节点,设定合理的椭圆限制搜索区域,以减少算法的搜索规模。针对椭圆限制搜索区域算法由于计算量大而效率不高的弱点,提出了矩形限制搜索区域算法,达到既减小算法搜索规模,又提高算法运行效率的目的。试验结果显示了本文提出的限制搜索区域算法的合理性与有效性 相似文献
3.
在基于四叉堆优先级队列的改进型Dijkstra最短路径算法的基础上,进一步提出了利用交通网络的空间分布及方位特征构造限制区域的时间最短路径算法。在对城市交通网络空间分布特征进行统计分析的基础上,针对具体的起,终节点,设定合理的椭圆限制搜索区域,以减少算法的搜索规模。 相似文献
4.
限制搜索区域的分层路径规划算法 总被引:4,自引:0,他引:4
依据城市路网独特的空间分布特性及不同道路等级特性,提出一种限制搜索区域的分层路径规划算法.与文献[2]相比,文中算法新增了对路网空间分布特性的利用,引入了限制搜索区域的搜索机制.结合路径规划算法在实时车辆导航系统中的实际应用,给出该算法的一个应用实例,通过对实验结果的分析验证了其有效性. 相似文献
5.
提出了一种物联网技术下盲人导航系统的路径规划算法.采用Dijkstra最短路径算法作为基础算法,以关系数据库作为存储模式,通过多因素模糊算法来确定道路网络中的权值,并根据道路网络的空间分布特性,合理利用矩形限制搜索算法来限制搜索范围.结合算法在盲人导航系统中的应用,给出了算法的应用实例,仿真实验和实例分析结果表明了算法的正确性. 相似文献
6.
7.
从分析城市道路网地理相关性特征入手,研究利用道路网的空间特性信息来解决道路网中两点间的最短路径问题.通过建立体现道路网空间特性的数据模型,根据两点间直线距离最短的原理,提出一种道路网两点间最短路径的算法,利用VC 进行了算法实现和最短路径的可视化显示.实验结果证明:利用空间特性信息可以有效地减少最短路径的搜索花费,同时算法的实现和最短路径的可视化不须依赖地理信息系统平台,具有较好的可移植性和实用性. 相似文献
8.
9.
基于MapX最短路径搜索算法研究 总被引:1,自引:0,他引:1
在深入分析现有最短路径搜索算法和MapX空间特性的基础上,提出了一种基于MapX的局部最短路径搜索算法.该算法依据最短路径沿起点、终点连线方向可能性最大的特征,在小矩形范围内搜索,避免了因道路"振荡"而产生结果失真的问题,减少了搜索的节点数目,降低了搜索规模.实验结果表明,该算法搜索速度快,道路网络结构越复杂,其运行效率越高,具有很强的实用性. 相似文献
10.
改进Dijkstra算法在GIS导航应用中最短路径搜索研究 总被引:3,自引:2,他引:1
研究GIS在电子导航系统应用中的最短路径搜索效率问题。在电子导航系统中对最短路径的搜索效率要求很高。随着城市发展交通线路剧增,传统的基于Dijkstra算法的GIS导航系统不能适应日益复杂的交通线路,存在最短路径搜索效率过低的问题。考虑到GIS空间分布的特性,提出了改进的Dijkstra算法用以解决GIS导航中的最短路径搜索问题。改进算法不仅避免了传统Dijkstra算法逐个节点遍历搜索,而且根据方向优先特性缩小搜索范围,大大减少了搜索工作量,并通过改变搜索节点存储的数据结构提高了最短路径的搜索效率。实验表明,这种改进算法较之传统算法能够有效提高最短路径的搜索效率,满足了电子导航系统对最短路径搜索效率的要求,取得了满意的结果。 相似文献
11.
传统Dijkstra算法用于路径诱导会使路网节点的数量增多、搜索范围扩大,从而耗费大量时间和空间,降低停车诱导信息系统(PGIS)的运行效率和实时性。针对城市路网的特定环境和路径诱导需求,根据2点之间直线最短的原理,在Dijkstra算法的基础上,提出一种应用于PGIS、基于矩形搜索范围的改进Dijkstra算法,设计并实现城市路网模型中单行、禁行、交叉点时间延误等问题的解决方案。实验结果表明,改进Dijkstra算法可以减少路网节点搜索范围和计算复杂度,提高用户搜索路径的实时性。 相似文献
12.
针对大规模城市路网寻找最短路径的问题,提出了一种基于边的聚类树(ECT)和最小封闭格(MCL)的算法来达到路网中快速查询的目的。首先对给定的城市路网进行预处理,即利用封闭格的定义对路网进行划分;其次利用ECT树对划分出的MCL格进行存储;最后利用虚拟路径的思想(两点之间直线距离最短)并结合MCL格的性质和路网的平面性的特点,利用ECT树存储的优势,在查询中大大减少了无用节点的访问数量,降低了时间复杂度,从而达到了快速寻找最短路径的目的。理论分析和仿真实验表明,在大规模的城市路网中ECT树的存储空间相比PCPD算法减少了约45.56%,相比TNR算法减少了24.35%,其在存储方面略优于较为完备的SILC算法。MCL算法在查找过程中的搜索效率比SPB算法快15.6%。实验结果表明基于ECT存储的MCL算法在实际查询过程中能提高查询的效率。 相似文献
13.
基于分层的改进A*算法在路径规划中的应用 总被引:1,自引:0,他引:1
智能交通中的路径诱导系统能够极大地提高人们的出行效率与出行体验。经典A*算法只注重搜索精度而忽略了搜索效率,在城市道路网络分层的基础上,对高层道路使用的A*算法进行了改进,对于道路网络中的不同节点,设置估价函数具有不同的权值,同时给定权值的一个上下限阈值,以平衡算法的搜索效率与搜索精度。实验表明,得到的最短路径虽然不是常规的距离最短却是实际行驶时间最优的。 相似文献
14.
Vehicle navigation is one of the important applications of the single-source single-target shortest path algorithm. This application
frequently involves large scale networks with limited computing power and memory space. In this study, several heuristic concepts,
including hierarchical, bidirectional, and A*, are combined and used to develop hybrid algorithms that reduce searching space, improve searching speed, and provide the
shortest path that closely resembles the behavior of most road users. The proposed algorithms are demonstrated on a real network
consisting 374,520 nodes and 502,485 links. The network is preprocessed and separated into two connected subnetworks. The
upper layer of network is constructed with high mobility links, while the lower layer comprises high accessibility links.
The proposed hybrid algorithms are implemented on both PC and hand-held platforms. Experiments show a significant acceleration
compared to the Dijkstra and A* algorithm. Memory consumption of the hybrid algorithm is also considerably less than traditional algorithms. Results of this
study showed the hybrid algorithms have an advantage over the traditional algorithm for vehicle navigation systems. 相似文献