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值升序的队列(即优先队列)进行排列。这样,在整体的搜索

最近更新

二零二五年度生物科技股权投资合同协议 8页

中小企业人才流失及应对策略 4页

二零二五年度珠宝首饰销售代理总代理合同 10页

二零二五年度环保行业实习生聘用合同 8页

中国石化财务共享服务体系的构建与实施 5页

二零二五年度特色蛋糕店加盟连锁经营合同 10页

中华传统太极文化对太极拳的影响 4页

东莞以纯集团有限公司营运能力分析 5页

专利如何转化为生产力 7页

上市公司财务舞弊及其治理研究 4页

等离子熔覆耐磨层的制备及其与摩擦配副的匹配.. 2页

一种单相转三相逆变电源转换器 4页

【毕业设计】基于单片机的电子毕业设计题目 7页

二零二五年度汽车维修合同简易版:汽车悬挂系.. 10页

【人力资源六大模块】员工绩效考核共27 5页

二零二五年度母婴护理月嫂产后康复全面服务合.. 9页

《论A公司绩效考核存在的问题及对策》开题报告.. 4页

《核心供应商管理在采购流程中的重要性》 6页

《企业成本控制现状及其改进对策—以三全食品.. 4页

《人力资源》论文选题参考目录4 5页

《C幼儿园户外游戏活动现状及优化建议开题报告.. 17页

“岗课赛证”综合育人模式下“红匠育成”人才.. 4页

·时代光华管理课程讲义——如何以绩效考核促.. 5页

二零二五年度文化活动货款分期支付合同 10页

二零二五年度文化产业园区合同工期延长及文创.. 10页

二零二五年度教育装备租赁与维护合同 9页

二零二五年度摩托车整车保险代理转让协议 8页

HRM题型及部分范围 6页

FDI对我国碳排放的影响 5页

dqe绩效考核指标 5页