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

最近更新

二零二五年度劳动合同员工加班费及休息日加班.. 9页

二零二五年度养殖场租赁征收补偿与农村金融服.. 9页

PMC生产计划[1] 94页

二零二五年度个人房产买卖合同(含交易风险提.. 8页

2025年度鱼饲料行业规范与购销合同 9页

2025年度餐厨废弃物收购与废弃物资源化利用技.. 11页

2025年度金融科技创新合作框架协议书 9页

2025年度车库停车场智能化改造与运营合同 9页

2025年度药店负责人绩效考核与激励聘用合同 8页

2025年度股权激励合伙人协议书,优化企业股权.. 9页

2025年度绿色食品脐橙购销合同书复合附录版 10页

2025年度租赁房屋租赁合同纠纷处理指南 8页

2025年度目录版飞防植保作业环境友好合同 10页

2025年度生产一线工人工资调整与劳动合同续签.. 7页

2025年度物流仓库电梯采购、安装与维护合同 10页

2025年度泳池设备租赁与售后服务合同 9页

2025年度校车租赁服务与教师培训合同 9页

2025年度新能源汽车销售提成协议 8页

2025年度按季付费青年公寓租赁合同书 8页

2025年度房屋买卖合同协议书范本(含房屋交易.. 8页

2025年度学校零星维修与校园环境整治服务合同.. 9页

2025年度境外游学夏令营课程设计与实施合同 9页

2025年度土地流转与农村土地整治合同简易版本.. 8页

2025年度商业地产租赁合同关于房屋出租业务 8页

2025年度厨师餐饮企业员工福利保障合同 8页

2025年度医校心理健康服务及心理测评合同 9页

2025年度出租房屋装修改造及租赁纠纷解决协议.. 8页

2025年度农业现代化项目投资与建设合同 9页

2025年度全国青少年篮球联赛参赛球队赞助合同.. 8页

2025年度企业财务管理顾问协议 8页