共查询到20条相似文献,搜索用时 625 毫秒
1.
本文对路径规划中比较常见的A*搜索算法进行研究,对几种基于A*搜索算法的路径规划方法如A*单向搜索、A*双向搜索及A*二次搜索进行讨论,并分析其优缺点,同时提出两个有待解决的问题。 相似文献
2.
基于DEM格网的改进型A*路径搜索算法 总被引:2,自引:0,他引:2
为解决DEM格网上的路径搜索问题,分析了DEM格网和道路拓扑网络的共性与区别,并结合DEM格网的特点对比了Dijkstra算法和A*算法的优缺点,提出了基于DEM格网的改进型A*路径搜索算法。该算法充分考虑DEM格网上的路径可达条件,采用移动窗口法获取搜索网格候选集,并根据地理空间分布特征选取A*算法的估价函数,同时引入贪婪准则缩小搜索范围,降低问题复杂度。结合实例对算法进行了实验分析,验证结果表明了该算法的可行性和有效性。 相似文献
3.
迷宫搜索算法的比较研究 总被引:1,自引:1,他引:0
研究面向搜救的应用,将事故环境抽象为一个迷宫,通过仿真实验比较研究了深度优先搜索算法和三种不同启发式函数的A*算法在Perfect迷宫中的应用,并分别将深度优先搜索算法和A*算法用于实际迷宫中进行实现与比较.在实验中,迷宫环境对机器人是未知的,而由于迷宫环境的特殊性——未知的迷宫环境中很少有不会碰撞的路径,从而增加了机器人搜索的难度.通过仿真实验对比了不同启发式函数的A*算法与深度优先搜索算法的性能,最后得出在迷宫搜索中A*算法要优于深度优先搜索算法;同时,在实际迷宫中实现了深度优先搜索算法与A*算法的搜救应用. 相似文献
4.
路径搜索是游戏中非常重要的一部分,A*算法是最常用的搜索算法,但是使用A*算法搜索出的路径的真实性常常不能让人满意。本文介绍A*搜索算法及存在的路径问题,针对该算法在游戏中暴露的问题,提出一种平滑改进的算法,较好地解决了这个问题。 相似文献
5.
针对串行最短路径搜索算法本身固有的局限性,难以随着网络规模的增大而提高搜索速度的问题,设计并实现了一种基于并行Dijkstra思想的并行最短路径搜索算法,使算法复杂度由O(N2)减少到O(N2/p+N*(p-1)),提高了算法的效率。实验结果表明,该算法搜索速度快且性能稳定,当结点数目相当庞大时,算法的优越性更加明显。 相似文献
6.
为了泛化RRT (快速搜索随机树)算法在智能车辆路径规划领域内的应用,解决该算法搜索效率低、最近邻搜索函数不合理等问题,本文提出了一种基于A*引导域的RRT路径规划算法.该算法将A*算法与RRT搜索算法进行有效地结合,利用由A*算法在低分辨率栅格图中生成的最短路径来构建引导域,以提升RRT算法的采样效率;同时在设计RRT算法的最近邻搜索函数时考虑车辆自身约束,以增强搜索树节点选择的合理性.通过仿真实验和实车测试,对该算法的优越性、有效性和实用性进行了验证. 相似文献
7.
与/或图搜索中的A^*算法—AO.A^*算法 总被引:2,自引:0,他引:2
本文建立了普通图和与/或图(指广义与/或图,它包括普通与/或图)的概念之间的相似对应关系,从而将图搜索中完美的理论、算法及分析方法成功地移植到与/或图搜索中来.以A~*算法为例,本文描述了一个类似于A~*的与/或图搜索算法AO.A~*,并分析了其性能. 本文还对与/或图搜索算法的复杂度的定义进行了讨论,并指出了G.Levi的复杂度定义的某些缺陷. 相似文献
8.
王锐 《计算机光盘软件与应用》2012,(17):140-141
本文提出了适用于智能交通系统的基于双向搜索的改进算法。典型的最短路径算法被认为是Dijkstra算法,其时间复杂度是O(n2)。但一个城市的路网地图有很多节点,该算法的时间复杂度高和解决速度慢。为了改变这种情况,我们从算法的设计方面进行了讨论,提出了改进的双向搜索算法。实践证明,改进后的算法能够提高了搜索速度,适用于智能交通系统。 相似文献
9.
10.
认真分析了访问图的过程中已被访问结点、未被访问结点以及环路构成成因,设计出全路径搜索算法.算法采用了邻接表作为数据结构,存储图的基本信息,利用双栈技术为辅助的广度优先搜索算法搜索图中任意两点问的全路径.给出全路径搜索算法的特性分析,在最坏的情况下,算法的时间复杂度为D(2*e*n+2*e*b4),并用江苏省高速公路路网信息数据进行验证,得出正确的结果. 相似文献
11.
为了解决A*路径搜索算法在Silverlight网页游戏中的搜索费时和路径曲折等问题,在结合光线跨越算法和引入父结点指针的二叉堆存储开启列表的A*算法的基础上,提出了一种基于Silverlight网页游戏的寻径优化算法。该算法在现有研究的基础上使用光线跨越算法减小A*算法搜索规模,同时将动态关键点技术与光线跨越算法结合来优化算法返回的路径。将该算法在游戏所使用的网格地图中进行实验,实验结果表明,该算法能够有效地根据系统设定的通行条件寻找出一条最优的实际可行的路径,同时缩短寻路的时间消耗和所寻的路径长度,提高游戏的可玩性。 相似文献
12.
针对传统A*算法搜索空间以及收敛时间等方面的不足,首先提出了改进的A*算法;其次对战斗机突防段综合航迹规划影响因素进行分析,在此基础上建立了战斗机对地攻击突防段代价函数数学模型;然后对支援干扰下的雷达压制区进行研究,确定干扰机位置,由此条件构建支援干扰下战斗机突防段综合航迹规划模型;最后应用改进的A*算法进行战斗机突防段综合航迹规划。仿真实例表明,基于改进的A*算法可以有效地进行突防段的航迹规划,可以有效地减小航迹的代价,提高战斗机的突防概率,有利于我方战斗机成功突防。 相似文献
13.
为提高航空器飞行的安全性和平滑性,解决传统A*算法拐弯角度过大、搜索路径节点过多等问题,提出一种基于扇形领域扩展的同步双向A*搜索算法。首先,根据栅格图法扩展危险区域边界;其次,设计了基于同步双向搜索的A*算法,动态定义正反向搜索的目标节点。针对搜索角度有限问题,提出了在5×5领域内的扇形领域扩展策略,并设计了含有双重权重参数的评价函数以减少冗余点的产生。为验证改进算法的有效性,选取方形和不规则形状危险区进行仿真。结果表明改进的同步双向搜索算法搜索的路径更平滑;与传统双向A*算法的结果相比,在不同形状的危险区域下,搜索路径长度分别减少了1.65%、13.16%,搜索路径节点个数减少了42.6%、46.81%,具有较强的搜索效率。 相似文献
14.
A*算法广泛应用于移动机器人路径规划中,而传统A*算法在寻路时,普遍存在搜索时间较长、效率低下等问题,因此,采用双向搜索的方式,对传统A*算法加以改进,该算法在路径规划过程中,可同时进行正反向路径搜索,同时采用正反向搜索交替机制,保证了最终目标节点搜索在连线中点区域内相遇,从而缩短了寻路计算时间。在MATLAB平台上,针对改进后的A*算法进行仿真实验,结果证明,双向A*算法减少了规划时间,且可生成最优路径。最后,将该算法应用到基于开源机器人操作系统的Turtlebot2移动平台上,进行现场实验,实验结果表明,双向A*算法减少了寻路计算时间,从而使得路径搜索效率得到显著提升,且规划路径合理,满足路径规划要求。 相似文献
15.
在游戏和地理信息系统开发等领域中,专门针对最短路径搜索方面的优化研究较多,尤其是最短路径中启发式搜索算法中的A*算法的效率优化研究.本文将针对在人工智能或算法研究中的使用的地图大多数是基于任意图而不是网格图的状况,通过任意图与网格图及方向的相结合,提出了三种优化A*算法的启发式函数搜索策略,较好地减小了算法搜索的范围和规模,有效地提高了A*算法的运行效率.最后的实验结果显示,与传统的A*算法相比较,优化启发搜索策略后的A*算法寻径更快速,更准确,计算效率更高. 相似文献
16.
双向启发式图搜索算法BRA^*之研究 总被引:2,自引:0,他引:2
本文在[1]中基于模运算,提出了随机产生式系统的启发式图搜索算法RA~*.本文提出一个随机产生式系统的双向搜索的启发式图搜索算法BRA~*,证明了算法BRA~*的可采纳性,并得到了一些新的可采纳性结果.算法BRA~*的搜索效率比算法RA~*高.若启发式估价函数满足单调性限制,通过使用NP操作,则算法BRA~*的搜索空间将进一步减少. 相似文献
17.
王士同 《计算机工程与设计》1996,17(1):3-8
首先针对搜索树中深度固定且目标唯一的寻优问题,指出宽度优先反复加宽的搜索效率要比深度优先反复加深的搜索效率高,基于此,提出了基于宽度优先反复加宽的启发式搜索算法IWA*,算法IWA*是可采纳的。为了保持算法IWA*的搜索效率高于算法IDA*的搜索效率,同时又使算法IWA*的存贮空间复杂度减低,文中基于分层技术,提出了基于深度优先的IWA*算法──IDWA*。算法IDWA*也是一个可采纳的启发式搜索算法。 相似文献
18.
在人工智能领域中,八数码问题一直都是一个游戏难题。介绍了八数码问题,然后在启发式搜索算法上对A*算法定义进行了解释,并在其旨在提高搜索效率的方面作了比较详尽的介绍,详细描述了基于图搜索算法的解决此类问题的一种启发式搜索算法———A*算法。再依据这种算法用可视化编程语言VC 6.0来实现八数码问题的求解过程,取得了预期的搜索解,提高了搜索效率。 相似文献
19.