A*算法
A*算法实验报告
一、 实验原理
A*算法,作为启发式算法中很重要的一种,被广泛应用在最优路径求解和一些策略设计的问题中。而A*算法最为核心的部分,就在于它的一个估值函数的设计上:
f(n)=g(n)+h(n)
其中f(n)是每个可能试探点的估值,它有两部分组成:一部分为g(n),它表示从起始搜索点到当前点的代价(通常用某结点在搜索树中的深度来表示)。另一部分,即h(n),它表示启发式搜索中最为重要的一部分,即当前结点到目标结点的估值,h(n)设计的好坏,直接影响着具有此种启发式函数的启发式算法的是否能称为A*算法。
一种具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法的充分条件是:
1) 搜索树上存在着从起始点到终了点的最优路径。
2) 问题域是有限的。
3)所有结点的子结点的搜索代价值>0。
4)h(n)=<h*(n) (h*(n)为实际问题的代价值)。
当此四个条件都满足时,一个具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法,并一定能找到最优解。
对于一个搜索问题,显然,条件1,2,3都是很容易满足的,而
条件4): h(n)<=h*(n)是需要精心设计的,由于h*(n)显然是无法知道的。
所以,一个满足条件4)的启发策略h(n)就来的难能可贵了。不过h(n)距离h*(n)的程度不能过大,否则h(n)就没有过强的区分能力,算法效率并不会很高。对一个好的h(n)的评价是:h(n)在h*(n)的下界之下,并且尽量接近h*(n).
二、 实验过程
运行未修改的程序会得到最优路径为:

A星算法实验报告11_计算机软件及应用_IT/计算机_专业资料。人工智能人工智能 学院:信息学院 班级: 学号: 姓名: 一、 实验原理 A*算法,作为启发式算法中很重要...
3) 分析估价函数对搜索算法的影响。 4 )分析 A*算法的特点。 5、提交要求 1、本次实验为个人任务,需独立完成,以纸质和电子档的形式把实验报告提交给学习 委员...
D-A转换仿真实现 实验报告 13页 5财富值 A星算法实验报告 4页 2财富值 A-实验报告模版 暂无评价 3页 免费 电子商务安全实验报告A 12页 2财富值...
A星算法求解八数码技术报告_计算机软件及应用_IT/计算机_专业资料。人工智能。...实验结果: 实验结果: 附录: 源代码及其注释 #include "iostream.h" #include ...
A星算法详解_计算机软件及应用_IT/计算机_专业资料。A星算法详解A*路径寻找算法入门 来源于: GameDev.net 作者: Patrick Lester 原文 URL: http://www.game...
人工智能 A*算法实验报告实验目的 1.熟悉和掌握启发式搜索的定义、估价函数和算法过程 2. 学会利用 A*算法求解 N 数码难题 3. 理解求解流程和搜索顺序 实验原理...
算法所用内存较少. 二.广度优先搜索(BFS) 1.先在开始位置测试周围一格所能走...2014年度细分行业报告汇集 2014年移动互联网O2O分析报告 休闲农庄项目可行性研究...
实验结果,如图 3 所示 3 图 3 A*算法求解八数码问题实验结果 7、源代码 ... 休闲农庄项目可行性研究报告 2014年建筑幕墙建筑装饰行业分析报告...
A星算法中文详解_IT/计算机_专业资料。UNITY3D中的A星算法中文详解虽然A*(读作A星)算法对初学者来说是比较深奥难懂,但是一旦你找到门路了, 它又会变得非常简单...
A星算法_专业资料。A星算法A*算法目录 原理简介 估价值与实际值越接近,估价函数取得就越好 详细内容 启发式搜索其实有很多的算法 其实 A*算法也是一种最好优先...
热门文档