欢迎来到天天文库
浏览记录
ID:22777175
大小:275.48 KB
页数:17页
时间:2018-10-31
《631306050103姜彦斌启发式搜索神经网络分类问题》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、重庆交通大学计算机与信息学院验证性实验报告级:计算机科学与技木专业2013级1班号:631306050103名:姜彦域实验项目名称:启发式搜索实验项目性质:验证性实验实验所属课程:人工智能朱振国实验室(中心):软件中心实验室(语音楼8楼)指导教师:实验完成时间2016年06月10日评阅意见:实验成绩:签名:年月一、实验目的理解和掌握A*算法。二、实验内容及要求在8数码问题屮,利用策略函数判断搜索,并使用A*算法减少搜索A标。三、实验设备及软件1.MicrosoftWindows10Build1436164bit(操作系统)2.Python3.5.1(运行环境)3.NoteP
2、ad++v6.9.2(代码编写环境)Ui设计方案㈠题目在8数码问题屮,利用策略函数判断搜索,并使用A*算法减少搜索A标。㈡设计的主要思路估价函数是搜索特性的一种数学表示,是指从问题树根节点到达n标节点所要耗费的全部代价的一种估算,记为f(n)。估价函数通常由两部分组成,其数学表达式为f(n)=g(n)+h(n)其中f(n)是节点n从初始点到FI标点的估价阑数,g(n)是在状态空间中从初始节点到n节点的实际代价,h(n)是从n到目标节点最佳路径的估计代价。保证找到最短路径(最优解)的条件,关键在于估价阑数h(n)的选取。估价值h(n)<=n到鬥标节点的距离实际位,这种情况下,
3、搜索的点数多,搜索范围大,效率低。但能得到最优解。如果估价值>实际值,搜索的点数少,搜索范围小,效率高,但不能保证得到最优解。搜索中利用启发式信息,对当前未扩展结点根据没定的估价函数值选取离FI标最近的结点进行扩展,从而缩小搜索空间,更快的得到最优解,提高效率。进一步考虑当前结点与FI标结点的距离信息,令启发函数h(n)为当前8个数字位与目标结点对应数字位距离和(不考虑中间路径),且对于目标状态有h(t)=0,对于结点m和n(n是m的子结点)有h(m)—h(n)<=1=Cost(m,n)满足单调限制条件。最重要的是应用了曼哈顿距离。同时可以根据深度和h值,在找最优解的时候,
4、对超过目前最优解的地方进行剪枝,这可以导致搜索深度的急剧减少㈢主要功能利用A*算法求解八数码问题五、主要代码importcopydefinit(target):#初始化tlist,方便计算曼哈顿距离tlist=[0forainrange(9)]foriinrange(3):forjinrange(3):tlist[target[i][j]]=[i,j]returntlistdefgetStep(tlist,current):#获取曼哈顿距离step=0foriinrange(3):forjinrange(3):ifcurrent[i][j]!=O:k=tlist[curre
5、nt[i][jjjstep=step+abs(k[0]-i)+abs(k[l]-j)returnstepdefinTable(item,table):#在不在openedorclosed表屮it=item[2]fortintable:t2=t[2jift2==it:returnTruereturnFalsedefroop(tlist3tem,target):opened=[]closed=[]opened.append(item)whilelen(opened):#opened表的长度不为0current=opened[0]#第一个元素delopened[0]#从opene
6、d屮删除closed.append(current)#移动到closedifcurrent[2]==target:#已经找到目标,直接返回,目标已经插入到closedreturnclosed#以0为点移动#down0卜移curl=copy.deepcopy(current)foriinrange(3):forjinrange(3):ifcurl[2][i][j]==0andi!=2:#不是最底行,下移,交换位置temp=curl[2][i+l][j]curl[2][i+l]U]=curl[2][i]U]curl[2][i][j]=tempbreakifcurl!=curre
7、nt:#父是closed最后一个元素的位置sonl=[current[0]+l,getStep(tlist,cur1[2]),curl[2],len(closed)-l]ifnotinTable(son1,closed):ifnotinTable(son1,opened):#insertintoopened,方法是按step值小的在前排序插入iflen(opened)==0:opened.append(son1)else:foriinrange(len(opened)):ifopened[i][l]>sonl[l]
此文档下载收益归作者所有