共查询到20条相似文献,搜索用时 31 毫秒
1.
A~*启发算法是最优路径规划问题中最有效的算法之一,在路径规划问题中得到广泛应用。针对多值栅格环境下的最优路径规划的效率问题,对A~*算法在搜索策略上做了如下改进:一是提出了两种新的启发函数;二是提出了新的A~*双向搜索算法。实验表明改进算法求得的路径为最优路径,搜索效率比传统的Dijkstra算法有显著提升,双向A~*算法比单向A~*算法效率有明显提高。 相似文献
2.
本文在分析Dijkstra算法基础上,考虑城市路网的特点及该算法在路径优化中的不足,提出一种基于双向搜索的Dijkstra改进算法,它可以减少路网节点的搜索范围和计算复杂度。仿真结果表明,改进算法在最短路径搜索中可使候选节点数减少15%~25%,当节点越多这种减少越明显,可提高搜索路径的实时性。 相似文献
3.
本文在分析Dijkstra算法基础上,考虑城市路网的特点及该算法在路径优化中的不足,提出一种基于双向搜索的Dijkstra改进算法,它可以减少路网节点的搜索范围和计算复杂度.仿真结果表明,改进算法在最短路径搜索中可使候选节点数减少15%~25%,当节点越多这种减少越明显,可提高搜索路径的实时性. 相似文献
4.
5.
6.
针对传统蚁群算法在进行无人机三维环境路径规划时存在规划速度慢、容易陷入局部最优等问题,本文提出了用引导函数改变状态转移规则、初始信息素先验分配、时变信息素更新方式3个改进策略,充分挖掘路径规划先验信息。通过增加引导函数进行路径增强,增大最优路径的选择概率;同时根据与先验路径的距离赋予信息素不同的初始浓度,使算法在搜索初期具有明确的方向性,基于优胜劣汰的思想进行信息素更新,并将信息素挥发因子设定为服从Laplace分布的波动因子,避免搜索过程陷入局部最优,最大化提升路径搜索效率,实现三维环境下的无人机路径规划。仿真试验结果表明,改进后的蚁群算法在规划最优路径长度和最优路径搜索效率上明显优于传统蚁群算法。 相似文献
7.
8.
提出了一种基于双向搜索策略的K则最优路径算法,以改进的Dijkstra最优路径算法为基础,从起点和终点同时搜索,分别构造正序和逆序最优路径树,计算网络中两点之间的多条参考K则最优路径.详细描述了算法设计思想和运行过程,分析了算法的时间复杂度,并通过实际路网验证了算法的效率和精度. 相似文献
9.
10.
针对大规模物流配送,提出了一种集成模拟退火机制和Voronoi长边引导优化的启发式算法.模拟退火机制控制局部搜索过程,Voronoi长边发现解中不合理的空间结构,引导局部搜索过程,从而优化路径质量.实验结果表明,本文算法的搜索性能良好,能够在较短时间内给出高质量的车辆路径安排方案. 相似文献
11.
12.
针对多源多汇多路径问题若分别以多个出口为源点,通过多次直接调用Dijkstra算法求解,节点会被多次重复扩展,导致算法搜索效率过低的问题,该文结合Dijkstra算法的执行原理和特点,提出了一种解决多出口室内应急疏散路径规划的新算法。首先通过引入一个连接所有出口节点的虚拟节点作为源点来改变原始网络结构,将多源多汇多路径规划问题转化为单源多汇多路径规划问题;然后以虚拟节点为源点,直接调用Dijkstra算法来搜索源点到各个汇点的最优路径。该算法有效避免了多次调用Dijkstra算法带来的重复搜索节点问题,提高路径搜索效率。实验结果表明,该算法运行时间随着路网总节点数的增加而增加,与出口数关系不大;当出口数越多时,该算法较之现有算法效率提升越明显,具有较高的实用性。 相似文献
13.
主要针对当前嵌入式导航应用中路径规划计算存在的问题,设计了一种满足实时导航应用基于转换路网的分层搜索A*算法。该算法对于大区域的路径规划采用分层搜索策略,路径计算时采用能够处理交叉口转向限制和结点权重,并且占用存储空间小,搜索速度快的基于转换路网的二次搜索A*算法。通过实际的应用表明,算法在计算速度、路径合理性等方面可以满足实时导航应用的技术需求。 相似文献
14.
15.
提出了把基于典型事例推理的智能方法应用到路径规划过程中。在结合道路网络知识的基础上,定义了典型事例,并基于事例进行了推理。实验结果表明,该算法减少了搜索空间,加快了搜索速度,并满足人们喜欢在熟悉路径上行驶的偏好。 相似文献
16.
在GIS环境下研究最优路径问题具有很多优势,本文研究的最优路径问题是基于传统粒子群算法存在的早熟收敛问题,并提出了一种改进的粒子群算法,该算法在后期引入变异算子,变异操作能够提高算法跳出局部最优的能力,同时又保持了前期搜索速度快的优点。 相似文献
17.
最短路径是现代物流配送研究中热点问题之一,在分析传统启发式搜索算法的基础上,针对算法在路径优化中存在的不足,提出基于二叉树优化启发式搜索算法(A*)实现所需结点之间最短路径查询,在引入已知的全局信息条件下选择下一个被检查的结点,并根据用户给出的起始顶点与目标顶点以及搜索的角度查找最短路径,从而搜索可能性较大的结点,提高搜索过程的效率.实验表明,基于二叉树的A*比A*效率提高11%~26%. 相似文献
18.
针对传统路径规划方法在复杂大场景环境下的搜索空间大、效率低、避障安全性差等问题,本文提出了一种基于BIM的室内拓扑-栅格分层路径规划方法。首先,建立复杂室内环境的BIM模型,提取模型中结构、障碍物和通道的语义、几何及其关联信息,通过栅格抽象映射得到基础导航地图,并结合层次图思想,开展地图空间分层,获取拓扑-栅格分层地图;然后,利用细化算法,生成拓扑层中各子区域之间的离线先验路网,联合Dijkstra算法选取其中的最优路径,并基于自主改进的A*算法,快速高效搜索栅格层的最优路径,通过组合拼接拓扑层与栅格层的局部最优路径,构建完整的全局最优路径;最后,将本文方法与标准A*算法及蚁群算法作对比,在保证计算效率的同时,不仅缩小了路径搜索空间,还确保了最优路径的安全性,综合验证了所提路径规划方法的优越性。 相似文献
19.