迷宫搜索算法的比较研究

研究面向搜救的应用,将事故环境抽象为一个迷宫,通过仿真实验比较研究了深度优先搜索算法和三种不同启发式函数的A*算法在Perfect迷宫中的应用,并分别将深度优先搜索算法和A*算法用于实际迷宫中进行实现与比较.在实验中,迷宫环境对机器人是未知的,而由于迷宫环境的特殊性——未知的迷宫环境中很少有不会碰撞的路径,从而增加了机器人搜索的难度.通过仿真实验对比了不同启发式函数的A*算法与深度优先搜索算法的性能,最后得出在迷宫搜索中A*算法要优于深度优先搜索算法;同时,在实际迷宫中实现了深度优先搜索算法与A*算法的搜救应用.     

人工智能中求解八数码问题算法的实现与分析

针对八数码问题的求解,给出了深度优先搜索、广度优先搜索和启发式搜索(譬如A*算法)之间的算法比较,通过实验验证各种算法并得出结论:在通常情况下,采用启发式搜索算法来进行状态空间的搜索更为方便、高效。     

A＊算法改进算法及其应用

路径优化问题是现代生活和工作中的一个重要而复杂的问题,路径优化算法则是解决路径优化问题并推广应用路径优化问题的关键.在回顾Dijkstra算法和A*算法的基础上,提出了A*改进算法,并结合例子对算法求解过程进行说明.最后编程实现了Dijkstra算法、A*算法和A*改进算法,并对运行结果进行比较分析.     

一种基于改进Theta *的机器人路径规划算法

对Theta *算法进行改进,并用于解决机器人路径规划问题.首先,将障碍物对机器人产生的斥力作为一种惩罚函数加入到启发函数中,并合理地选择惩罚函数权重以确定启发函数.在此基础上,改进A *算法的变种——Theta *算法,提出对路径进行平滑处理的PS_Theta *算法.最后在二维仿真环境中进行验证及数据统计,并推广至三维复杂环境中,实验结果证明了算法的合理性与有效性     

应用于机器人路径规划的双向时效A*算法

针对时效A*算法为了大幅减少算法时间,导致路径规划长度增加和路径锯齿过多的问题,提出一种改进的双向时效A*算法,该方法将从起点和终点同时运行时效A*算法寻找路径,并采用多近邻栅格距离计算方案;同时,根据不同环境地图对传统A*算法、时效A*算法和双向时效A*算法运行结果进行对比研究及分析;最后,制定算法时间、路径长度两个指标来评判算法的优劣。实验结果显示,双向时效A*算法相对于传统A*算法,算法时间最大减少76.8%,相对于时效A*算法,时间最大减少55.4%,并解决了时效A*算法规划路径距离增加、路径不够平滑的问题。     

A~*算法的改进及其PROLOG实现

在人工智能领域中,A~*算法是实现有向图最佳优先搜索的一种启发式算法。本文介绍了A~*算法和对A~*算法的改进——B算法,并叙述了用Turbo Prolog实现B算法的方法。     

游戏中路径搜索算法研究

路径搜索是游戏中非常重要的一部分,A*算法是最常用的搜索算法,但是使用A*算法搜索出的路径的真实性常常不能让人满意。本文介绍A*搜索算法及存在的路径问题,针对该算法在游戏中暴露的问题,提出一种平滑改进的算法,较好地解决了这个问题。     

基于改进A*算法的分拣搬运机器人路径规划

为了解决分拣搬运机器人在路径规划过程中,遇到目标点众多的情况时存在路径寻优效率低、容易出错等问题。针对A*算法存在多个最小值时,无法实现路径最优化的问题进行研究,提出一种将蚁群算法与A*算法相结合的改进A*算法。首先使用A*算法筛选出一条最优化的路线来分布信息素,从而简化A*算法在路径规划上的运算。其次以筛选出的路线为基础,针对不同情况结合蚁群算法设计了三种通用方案,以此为基础进行具体的路径规划,从而解决A*算法本身存在的容易带入大量重复数据的问题。通过仿真与实际实验验证了本文提出的改进的A*算法能够满足自动分拣搬运的需求,值得推广与使用。     

改进BIT*与DWA算法的动态路径规划

传统批通知树（batch informed trees,BIT*）算法结合了RRT*算法和A*算法的优势,但是该算法在复杂环境下无法躲避未知的动态障碍物,无法完成动态路径规划。针对该问题,提出了一种将改进的BIT*算法和改进的DWA算法相融合的算法。在传统BIT*算法的基础上对路径进行拉伸优化,提取关键转折点,减少路径长度;对传统DWA算法的距离评价函数进行改进、引入轨迹点评价函数,避免局部规划过分偏离,也减少了已知障碍物对路径的影响;将改进的BIT*算法与改进的DWA算法相融合,将提取的关键转折点作为DWA的中间目标点,弥补全局规划算法无法躲避动态障碍物的缺点以及局部规划算法全局能力低下的缺点。在动静态地图中对RRT*算法、BIT*算法、DWA算法、改进BIT*算法以及融合算法进行仿真实验,仿真结果表明：在复杂环境中,改进的BIT*算法具有更短的路径和更少的拐点;与传统的DWA算法相比,融合算法规划的路线更平滑,机器人既能实时动态避障抵达终点,又能更加贴近全局路径,保证路线全局最优。     

游戏地图最短路径搜索设计与实现

最短路径搜索是directx游戏的一项核心技术,文章分析了常用的搜索算法:宽度优先,深度优先和启发式搜索,最后剖析采用搜索树的A*算法来实现大地图与复杂地形的最短路径搜索。     

基于PVM的启发式搜索的并行计算模型设计

通过分析人工智能中的A和A^*启发式搜索,提出了通过PVM工具包,设计和实现A和A^*启发式搜索的并行计算模型。在启发搜索过程中同时进行评估函数计算,使计算的速度加快。解决了在搜索解空间庞大,评估函数计算复杂的情况下,使用单计算机计算速度慢的问题。该文实现了基于PVM的启发式搜索过程,该模型可应用于一般性启发式搜索问题的并行计算模型。     

通过八数码问题比较搜索算法的性能

搜索算法的核心在于搜索策略的制定.一般的搜索算法采用无信息指导的搜索策略,如深度优先搜索(DFS)和宽度优先搜索(BFS),还有一些搜索算法采用了启发式信息指导的搜索策略,如A*算法.不同的搜索策略会使得搜索算法的性能有很大的差异.使用以上3种搜索算法实现八教码问题的求解,分析和比较三者所表现出来的性能,同时指出3种搜索算法的特点和应用范围,最后给出分析结论以指导开发和使用更加高效的搜索策略.     

大规模AGV的改进时间窗路径规划

在机器人路径规划中,A*算法搜索路径时存在大量冗余节点,随着任务量增加,其搜索效率也会急剧下降,因此无法适应大规模任务下的路径规划。为此提出一种改进时间窗的有界次优A*算法用于求解大规模自动导引车（automatic guided vehicle,AGV）路径规划问题。算法使用时间启发式,并在搜索过程中采用时空搜索,规划无冲突的最优或次优路径。算法主要进行了三处改进：采用时间启发式,缩短了路径时间;采用动态时间窗算法,避免多次路径规划;优化了聚焦搜索算子,降低负反馈。通过MATLAB实验结果证明改进后的算法在进行多机器人路径规划时,能快速有效地规划出无冲突的平滑次优路径,搜索效率高,稳定性强。     

基于扇形领域扩展的同步双向A*算法

为提高航空器飞行的安全性和平滑性,解决传统A^*算法拐弯角度过大、搜索路径节点过多等问题,提出一种基于扇形领域扩展的同步双向A^*搜索算法。首先,根据栅格图法扩展危险区域边界;其次,设计了基于同步双向搜索的A^*算法,动态定义正反向搜索的目标节点。针对搜索角度有限问题,提出了在5×5领域内的扇形领域扩展策略,并设计了含有双重权重参数的评价函数以减少冗余点的产生。为验证改进算法的有效性,选取方形和不规则形状危险区进行仿真。结果表明改进的同步双向搜索算法搜索的路径更平滑;与传统双向A^*算法的结果相比,在不同形状的危险区域下,搜索路径长度分别减少了1.65%、13.16%,搜索路径节点个数减少了42.6%、46.81%,具有较强的搜索效率。     

A*算法在Shortest-Path方面的优化研究

在游戏和地理信息系统开发等领域中,专门针对最短路径搜索方面的优化研究较多,尤其是最短路径中启发式搜索算法中的A*算法的效率优化研究.本文将针对在人工智能或算法研究中的使用的地图大多数是基于任意图而不是网格图的状况,通过任意图与网格图及方向的相结合,提出了三种优化A*算法的启发式函数搜索策略,较好地减小了算法搜索的范围和规模,有效地提高了A*算法的运行效率.最后的实验结果显示,与传统的A*算法相比较,优化启发搜索策略后的A*算法寻径更快速,更准确,计算效率更高.     

最长公共子序列算法在文字录入测试中的应用

测试Word中的文字录入内容,是开发Office等考试软件过程中的一个关键 技术问题.常用的处理方法是关键字检测法.通过检测Word文件中的关键字,可以测试出考 生操作的大概结果,但是很不准确.利用最长公共子序列算法进行文字录入测试,可以很 好地解决这一问题.     

通用搜索算法的设计

问题求解系统常常涉及到多种形式的搜索方法，搜索方法的关键是搜索算法设计。这里给出一个简捷的通用搜索算法，算法采用结点指针和搜索指针对关系矩阵进行双重处理的方法，搜索过程中不断改变结点指针和搜索指针，进行推进和回退处理，最终找出问题的全部解。     

Wastewater Treatment Systems from Case–Based Reasoning

Case-Based Reasoning (CBR) is one of the emerging paradigms for designing intelligent systems. Preliminary studies indicate that the area is ripe for theoretical advances and innovative applications. Heuristic search is one of the most widely used techniques for obtaining optimal solutions to many real-world problems. We formulated the design of wastewater treatment systems as a heuristic search problem. In this article we identify some necessary properties of the heuristic search problems to be solved in the CBR paradigm. We designed a CBR system based on these observations and performed several experiments with the wastewater treatment problem. We compare the performance of the CBR system with the A* search algorithm.     

Pattern Databases

The efficiency of A* searching depends on the quality of the lower bound estimates of the solution cost. Pattern databases enumerate all possible subgoals required by any solution, subject to constraints on the subgoal size. Each subgoal in the database provides a tight lower bound on the cost of achieving it. For a given state in the search space, all possible subgoals are looked up in the pattern database, with the maximum cost over all lookups being the lower bound. For sliding tile puzzles, the database enumerates all possible patterns containing N tiles and, for each one, contains a lower bound on the distance to correctly move all N tiles into their correct final location. For the 15-Puzzle, iterative-deepening A* with pattern databases(N ="8) reduces the total number of nodes searched on a standard problem set of 100 positions by over 1000‐fold.     

移动GIS引擎的设计与实现

为能在移动设备资源限制的情况下提供高效高质的地理信息系统(GIS)服务,分析研究移动GIS引擎的系统体系结构和类库结构.采用A*算法解决移动GIS最优(短)路径搜索的问题.通过对引擎内部层次结构的设计,结合手机GPS定位和电子地图等关键技术,在Windows移动平台上用VC++语言开发并实现一个移动GIS引擎系统.研究结果表明该引擎系统界面整洁,功能良好,且A*算法的搜索效率提高15％～20％.