1 / 6
文档名称:

A星算法实验报告11.docx

格式:docx   大小:41KB   页数:6页
下载后只包含 1 个 DOCX 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

A星算法实验报告11.docx

上传人:1542605778 2021/10/30 文件大小:41 KB

下载得到文件列表

A星算法实验报告11.docx

相关文档

文档介绍

文档介绍:人工智能
学院:信息学院
班级:
学号:
姓名:
实验原理
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).
实验过程
运行未修改的程序会得到最优路径为:
算法共扩展节点数792.
若修改源程序,即允许走斜线则
distance=(int)sqrt((end_x-x)*(end_x-x)+(end_y-y)*(end_y-y)),即将估价函数改为欧式距离
四连通改为八连通
trytile(x,y-1,n,1);//尝试向上移动
trytile(x+1,y-1,n,2);// 尝试向前上方移动
trytile(x-1,y-1,n,2); // 尝试向后上方移动
trytile(x-1,y+1,n,2); // 尝试向后下方移动
trytile(x+1,y+1,n,2); // 尝试向前下方移动
trytile(x,y+1,n,1);//尝试向下移动
trytile(x-1,y,n,1);//尝试向左移动
trytile(x+1,y,n,1);//尝试向右移动
并修改g值if(lei==1)//如果是直线走
{g_value=father->g+1;
}
if(lei==2)//如果是斜线走
{g_value=father->g+;
}
修改后的扩展结点数837
实验分析
A*算法最为核心的过程,就在每次选择下一个当前搜索点时,是从所有已探知的但未搜索过点中(可能是不同层,亦可不在同一条支路上),选取f值最小的结点进行展开。而所有“已探知的但未搜索过点”可以通过一个按f值升序的队列(即优先队列)进行排列。这样,在整体的搜索

最近更新

稀土金属冶炼废气处理-全面剖析 36页

植物基食品的营养价值与开发-全面剖析 30页

一年级上册排队问题 34页

信号屏蔽法在加工中心故障处理中的应用 2页

使用有机粘结剂降低球团矿中膨润土用量的研究.. 2页

低温预处理影响水稻花药培养效率的机理初探 2页

伺服电动机系统模型参考自适应建模方法 2页

燃气锅炉维修服务合同 6页

企业数据库营销存在的问题及对策研析 2页

演唱会合同范本:歌手与承办方合作协议 6页

港口作业合同(3) 6页

从成组工艺看机械工业标准化的趋向 2页

消防安保服务合同标准模板 7页

人机界面操作系统在电刷镀电源中的应用 2页

京津冀都市圈经济增长与生态环境关系研究 2页

《经典培训课件》团队建设之团队诊断篇 175页

五连杆浮体闸的水力学试验及研究 2页

云南省永胜县分水岭铜矿找矿模型初探 2页

二硫化钼固体润滑剂在大型球磨机上的应用 2页

江苏省品牌宣传广告服务合同(示范文本版) 6页

乙醇转化法氮基保护气氛制取工艺及装置 2页

水产品购销合同样本 7页

中酸性火成岩岩石化学计算若干问题的讨论及解.. 2页

中日设备维修技术研讨会在京隆重召开 2页

中小企业会计规范化的有效实现路径探究 2页

正式劳动合同样本(国有企业) 6页

棉花购销合同2025 6页

中国和日本棉纺织业资本主义萌芽的比较研究 2页

中华孝道园旅游开发现状及对策研究 2页

东鞍山贫赤铁矿脱泥方法的研究 2页