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

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

基于A*算法的足球机器人路径规划

路径规划问题是足球机器人研究的一个重点. 以往的路径规划算法忽略了球员的移动对其周围区域产生的影响,导致实际所求得的最优安全路径并非那么安全. 为了解决这个问题,提出了一种对动态障碍物避障的A^*算法. 该方法根据带球球员以及对方防守球员的影响力对球场进行了区域划分,并为每个区域设置了风险值,再运用改进后的A^*算法规划路径. 实验结果表明,该方法能够有效减少带球球员被对方防守球员包围的可能性,并且综合考虑了路径的长度与安全性,规划出的路径性能更好.     

融合简化稀疏A*算法与模拟退火算法的无人机航迹规划

针对无人机航迹规划问题,提出了一种融合简化稀疏A^*算法与模拟退火算法（Fusion of Simplified Sparse A^* Algorithm and Simulated Annealing algorithm,简称FSSA-SA）的航迹规划方法.首先,在对威胁环境进行建模之后,将模拟退火思想与具体航迹规划问题求解相结合,给出了模拟退火算法求解航迹规划问题的具体设计与实现方法.其次,利用简化的稀疏A^*算法在规划起止点之间进行一次往返搜索,并将所得结果中较优的一条航迹作为模拟退火算法的初始解,实现了两种算法的融合.然后,当退火进行至低温区时,通过对位置存在冗余的航迹节点的剔除,进一步改善了算法的求解质量.最后为了验证算法的优越性,将本文算法与稀疏A^*算法、模拟退火算法进行了仿真对比试验.试验结果表明,本文提出的FSSA-SA算法相比于上述两种算法,具有较少的规划耗时;相比于稀疏A^*算法,在所得航迹的综合代价相差不大的情况下,内存占用量少了两个量级;相比与模拟退火算法,在相同的退火条件下,其规划所得航迹的综合代价平均减少了35%左右.     

RFN-B+树索引文件及其有效性

在对比传统的B树和B⁺树的定义和操作算法的基础上,定义了一种新的B⁺树:RFN-B⁺树,以获得更高的空间利用率和可用性.首先比较和分析了RFN-B⁺树与传统B⁺树的空间效率,然后讨论了RFN-B⁺树索引文件的有效性以及支持这种有效性的全链接指针结构和两个备用模块:基于虚拟根结点的随机检索算法和重构结点的算法.     

基于B+树的多关键字密文排序检索方法

针对当前社会信息量大、隐私信息需要加密存储带来的检索难度大等问题,研究分析了现有的基于密文的可搜索加密方案,提出了一种基于B⁺树的多关键字密文排序方法。利用向量模型构建索引和查询陷门,根据相关性分数和关键字匹配度对检索结果进行排序。在真实数据集上进行了实验,结果证明本方案具有较高的检索效率。     

基于B*树聚簇索引的加密字符串查询方法

为了提高在数据库中查询加密字符串数据的性能, 提出一种在索引特征值上创建B^*树聚簇索引的查询方法. 每一个待加密字符串数据对应一个索引特征值, 索引特征值以数值的形式保存在索引字段中. 查询时使用两阶段查询策略, 首先利用索引字段对加密数据进行一次粗糙查询过滤掉不相干的记录, 然后在返回的粗糙集合解密的基础上进行明文查询, 得到最终结果. 实验表明该方法较现有查询方法在查询性能有较大的提升.     

基于Voronoi-R*的隐私保护路网k近邻查询方法

针对已有的保护位置隐私路网k近邻查询依赖可信匿名服务器造成的安全隐患,以及服务器端全局路网索引利用效率低的缺陷,提出基于路网局部索引机制的保护位置隐私路网近邻查询方法.查询客户端通过与LBS服务器的一轮通信获取局部路网信息,生成查询位置所在路段满足l-路段多样性的匿名查询序列,并将匿名查询序列提交LBS服务器,从而避免保护位置隐私查询对可信第三方服务器的依赖.在LBS服务器端,提出基于路网基本单元划分的分段式近邻查询处理策略,对频繁查询请求路网基本单元,构建基于路网泰森多边形和R^*树的局部Vor-R^*索引结构,实现基于索引的快速查找.对非频繁请求路网基本单元,采用常规路网扩张查询处理.有效降低索引存储规模和基于全局索引进行无差异近邻查询的访问代价,在保证查询结果正确的同时,提高了LBS服务器端k近邻查询处理效率.理论分析和实验结果表明,所提方法在兼顾查询准确性的同时,有效地提高了查询处理效率.     

NF2关系模型与属性继承

将面向对象模型与面向值的模型相结合,可兼得二者的优点．本文基于具有组合元组标识的ＮＦ²关系模型给出了强调嵌套结构特征的关系运算投影II^s和自然连接,并在此基础上研究ＮＦ²关系数据模型中的类、子类及其间的属性继承的语义及形式化定义;引入了Ｓ－子类的概念;研究了公共子类及多属性继承的特征．所有的讨论基于组合元组标识,具有较强的面向对象模型的特征．     

自然地形环境下移动机器人的一种路径规划方法

本文给出了一种规划移动机器人在自然地形中运动的新方法,该方法利用ＮＵＲＢＳ曲面模拟自然地形地貌,以ＴｒｉｍｍｅｄＮＵＲＢＳ曲面描述带有障碍物或不可逾越区域的地形,在综合考虑机器人动力学、地形及障碍描述和曲面特性等各方面因素的情形下,运用测地线的概念和计算方法以及Ａ＊搜索算法,获得了在自然地形环境下任意两点间的距离最短路径和时间最优路径,所有的路径均由ＮＵＲＢＳ曲线表示,实验结果表明,该方法在性能与效率上均十分令人满意．     

基于柱状空间和改进A*算法的无人机规避方法

针对无人机避障问题,提出了基于改进A~*算法和柱状空间的无人机规避方法。首先,根据无人机飞行区域的障碍物分布情况,建立飞行区域的柱状空间;然后将障碍物对无人机的影响引入到估价函数中,重新设计启发函数;最后将基于柱状空间和改进A~*算法的无人机规避方法应用于无人机的规避中,并对规划的路径进行平滑处理。仿真结果表明,该算法能够有效地实现无人机的规避。     

一种基于A*算法的虚拟力场避障导航算法

针对传统A＊算法在实际应用中需要所有的节点信息,算法忽略车身实际宽度的问题,提出了基于A＊算法同时结合使用虚拟力场法的避障导航算法。该改进算法解决了 A＊算法在实际应用中存在的问题,也避免了单独使用虚拟力场法存在的容易陷入局部极小点、在目标点附近有障碍物时无法到达以及摆动剧烈的问题。仿真实验验证了新算法的有效性,实验结果表明该算法拓宽了原有算法的使用范围并且提高了无人车实时路径导航的能力。     

基于多启发式信息融合的攻击路径发现算法研究

攻击路径发现对于提高信息系统安全具有重要意义,传统攻击路径发现技术存在考虑因素有限以及可扩展性不高的问题,导致其在网络攻击复杂化和网络规模扩大化的趋势下应用价值有限.针对该问题,本文提出一种基于多启发式信息融合的攻击路径发现算法,该算法结合攻击路径发现背景知识,将漏洞威胁程度,漏洞成功率以及主机资产作为启发式函数计算依...     

基于遗传算法的UAV自适应航迹规划

根据遗传算法与动态的稀疏A*搜索(Dynamic Sparse A*Search,DASA)算法各自的特点,提出一种组合优化算法来实现在不确定战场环境中自适应航迹规划.在无人机(UAV,Unmanned Aerial Vehicles)飞行前,采用全局搜索能力强的遗传算法进行全局搜索,对从起始点到目标点的飞行航线进行规划,生成全局最优或次优的可行参考飞行航线;在无人机任务执行阶段,以参考飞行航线为基准,采用DASA算法进行在线实时航迹再规划.仿真结果表明,与遗传算法相比,该组合算法不但能生成近似最优解,而且能够满足在线实时应用的要求.     

大型油库消防救援寻路算法改进

大型油库区的地形不同于城市、山地等复杂的地形,虽然范围较大,但是油库区地形十分规整,油罐等建筑排列整齐,且在储油罐区的道路是笔直畅通的.根据这些特点,将标准的A^*寻路算法进行改进.一方面,根据油库地形结构简单,搜索节点相对少的特点,对A^*算法中搜索Open表中节点的数据结构进行改进,采用排序算法提高了搜索效率;另一方面,根据储油罐区道路笔直畅通的特点,将道路分为有障碍路段和无障碍路段,分而治之,提高整体的寻路效率.实验证明,将两种改进方法进行结合,寻路时间明显缩短,平均搜索效率提高6.86%.     

基于触发序列集合的过程模型行为相似性算法

过程模型的相似性计算是业务过程管理中不可缺少的任务,广泛应用于组织合并、用户需求变更、模型仓库管理等多个场景.对基于主变迁序列的相似性度量方法 PTS进行研究,并提出了改进方案.通过定义完整触发序列表示模型行为,基于A*算法结合剪枝策略实现触发序列集合间的映射,进而完成模型相似性计算.实验结果表明:该方法较主流的基于模型行为相似性算法,计算合理性有很大提升.