631306050103姜彦斌启发式搜索神经网络分类问题

《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]