基于A*算法的地图寻径的研究

论文题目: 基于A*算法的地图寻径的研究

论文类型: 硕士论文

论文专业: 计算机应用技术

作者: 张前哨

导师: 陈和平

关键词: 搜索算法,算法,评价函数,人工智能

文献来源: 武汉科技大学

发表年度: 2005

论文摘要: 长期以来,搜索算法一直是人工智能的一个活跃方向。在50多年的研究中,搜索算法不断发展,已形成了成熟的理论体系。搜索包括对知识块的匹配、选择和解释。而匹配和解释的结果往往引起再搜索。在搜索算法的各种应用中,人们一直关注的是地图寻径问题。 本文针对搜索技术的特点,在对其进行详细分析的基础上,结合实际应用,对A~*算法进行了一定程度的改进。其主要目的是实现更快捷的A~*算法和平滑A~*路径,同时也为基于A~*的地图寻径新算法打下了一定的基础。 论文首先扼要地介绍了产生式系统描述搜索过程的一般方法以及人工智能中常用的一种知识表示方法——状态空间法;接着主要从人工智能的角度介绍了图搜索的两种基本策略——传统的搜索技术和启发式搜索技术;最后详细分析了启发式搜索技术之一——A~*算法的算法思想、特性及实现方法,同时讨论了评价函数的启发能力和搜索效率,并根据A~*算法的思想,给出了基于A~*算法的地图寻径新算法,该算法主要包括地图文件的生成、搜索算法和评价函数等部分。 此外,本文在搜索算法中主要研究A~*算法,并根据地图结构的特点,结合实际应用,在A~*算法的基础上实现加快和平滑路径等方面的改进,实现了一种基于A~*地图寻径的新算法。实验表明,充分利用已经获得的遍历信息指导新的遍历对提高搜索效率有着很大的影响。 本文中所讨论的评价函数主要是依赖于特定领域的知识,并通过不断学习,调整各项特征值和权重值而得到的,同时要综合考虑路径的耗散值、求解路径时所扩展的节点数以及计算从结点n到目标结点的最佳路径的估计代价值h所需的工作量,以便使启发能力达到最大。 最后,本文以上述理论为指导,选定Windows2000为操作系统,以Visual C++.NET为开发环境,设计并实现了基于A~*的地图寻径的新算法,从而达到了本文所提出的智能化的地图寻径目标。

论文目录:

摘要

Abstract

第一章 绪论

1.1 地图寻径的概述

1.2 文献综述

1.2.1 国内外地图寻径算法研究现状分析

1.2.2 地图寻径算法的发展预测

1.3 本文所做的工作

1.3.1 课题来源及意义

1.3.2 本文所做的工作小结

第二章 一般搜索原理

2.1 问题的提出

2.2 研究和选用搜索算法的原则

2.3 产生式系统

2.3.1 组成部分

2.3.2 基本过程

2.3.3 控制策略

2.4 状态空间

2.4.1 状态空间描述

2.4.2 状态图示法

2.4.3 显式状态空间搜索

2.5 图搜索的一般策略

2.5.1 图的相关概念

2.5.2 图搜索策略

2.6 传统搜索技术

2.6.1 回溯策略(Backtracking Strategies)

2.6.2 宽度优先搜索(BFS)

2.6.2.1 概念

2.6.2.2 算法

2.6.3 深度优先搜索(DFS)

2.6.3.1 概念

2.6.3.2 算法

2.6.4 等代价搜索(Uniform-cost Search)[Dijkstra 1959]

2.7 启发式搜索技术

2.7.1 启发式搜索的必要性

2.7.2 评价函数

2.7.2.1 评价函数的重要性

2.7.2.2 瑕癖效应(Blemish Effect)

2.7.2.3 评价函数的启发能力

2.7.3 有序搜索算法

2.7.4 A~*算法

2.7.4.1 A~*算法的评价函数

2.7.4.2 A~*算法

2.7.4.3 A~*的可接纳性

2.7.4.4 一致性(或单调)条件

2.7.4.5 A~*算法实例演示

2.7.5 评价函数和搜索效率

2.8 本章小结

第三章 常见地图寻径算法

3.1 搜索算法

3.2 单个物体寻径算法

3.3 动态障碍物环境中的行走路径生成

第四章 地图与地图编辑器

4.1 相关概念

4.2 数据结构

4.2.1 地图文件结构

4.2.2 文件头结构

4.3 地图类数据处理

4.3.1 多组文件类

4.3.2 图片数据文件类的处理

4.4 地图生成

第五章 基于A~*的地图寻径新算法的实现

5.1 A~*算法的改进

5.1.1 A~*算法的加快算法

5.1.2 平滑A~*路径

5.2 基于A~*的地图寻径新算法

5.2.1 地图寻径新算法

5.2.2 地图寻径实现界面及其主要类框架

5.3 实现步骤

第六章 结束语

6.1 论文的主要结论

6.2 进一步研究工作

参考文献

攻读硕士学位期间录用与发表论文

攻读硕士学位期间主要科研成果

致谢

发布时间: 2005-10-21

参考文献

• [1].移动机器人自主定位和地图生成新算法研究[D]. 付伟铮.北京化工大学2006
• [2].面向游戏地图的寻径算法的研究与实现[D]. 刘梓良.东南大学2016
• [3].面向自然语言的普适地图服务研究和实现[D]. 张正永.华东师范大学2010
• [4].水下机器人同步建立地图和定位技术研究[D]. 赵晶.哈尔滨工程大学2006
• [5].利用单目摄像头进行并行跟踪及地图建立算法的研究[D]. 何梦超.浙江大学2014
• [6].基于文化框架的群搜索和粒子群的混合算法及其应用[D]. 易卜拉欣.华东理工大学2014
• [7].基于局部搜索和二进制的改进人工蜂群算法[D]. 丁亚英.南京师范大学2016
• [8].基于人工蜂群算法的软硬件划分算法研究[D]. 韩宏业.天津大学2014
• [9].基于共享因子的人工蜂群算法的研究与应用[D]. 孟凡明.兰州交通大学2016
• [10].烟花算法及其应用[D]. 胡庆生.陕西师范大学2016

相关论文

• [1].GIS中最短路径问题的研究与实现[D]. 张烜.辽宁师范大学2007
• [2].人工智能寻路算法在电子游戏中的研究和应用[D]. 詹海波.华中科技大学2006
• [3].游戏领域中启发式寻径算法的运用和优化[D]. 靳旭栋.华东师范大学2007
• [4].GIS中最短路径问题的研究与实现[D]. 杨瑜君.四川大学2006
• [5].在智能搜索中A*算法的应用与研究[D]. 郝向荣.西安建筑科技大学2007
• [6].基于道路网的最短路径算法的研究与实现[D]. 荣玮.武汉理工大学2005
• [7].WebGIS中基于遗传算法的最短路径求解方法研究[D]. 乔连军.华东师范大学2006
• [8].人工智能在搜索引擎资源获取中的应用[D]. 车志军.浙江大学2006
• [9].基于Dijkstra、A*算法的汽车导航算路实现[D]. 岳靓亮.吉林大学2006
• [10].基于启发式搜索的灵活规划的算法研究[D]. 李杨.东北师范大学2006

标签：搜索算法论文;  算法论文;  评价函数论文;  人工智能论文;