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

《姜彦斌 启发式搜索 神经网络分类问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、重庆交通大学计算机与信息学院验证性实验报告班级：计算机科学与技术专业2013级1班学号：631306050103姓名：姜彦斌实验项目名称：启发式搜索实验项目性质：验证性实验实验所属课程：人工智能实验室(中心)：软件中心实验室（语音楼8楼）指导教师：朱振国实验完成时间：2016年06月10日17评阅意见：实验成绩：签名：年月日一、实验目的理解和掌握A*算法。二、实验内容及要求在8数码问题中，利用策略函数判断搜索，并使用A*算法减少搜索目标。三、实验设备及软件1.MicrosoftWindows10Build1436164bit（操

2、作系统）2.Python3.5.1(运行环境)3.NotePad++v6.9.2（代码编写环境）四、设计方案㈠题目在8数码问题中，利用策略函数判断搜索，并使用A*算法减少搜索目标。㈡设计的主要思路估价函数是搜索特性的一种数学表示，是指从问题树根节点到达目标节点所要耗费的全部代价的一种估算，记为f(n)。估价函数通常由两部分组成，其数学表达式为f(n)=g(n)+h(n)其中f(n) 是节点n从初始点到目标点的估价函数，g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。保证找到最短路

3、径（最优解）的条件，关键在于估价函数h(n)的选取。估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。如果估价值>实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。搜索中利用启发式信息，对当前未扩展结点根据设定的估价函数值选取离目标最近的结点进行扩展，从而缩小搜索空间，更快的得到最优解，提高效率。     进一步考虑当前结点与目标结点的距离信息，令启发函数h ( n )为当前8个数字位与目标结点对应数字位距离和（不考虑中间路径），且对于目标状态有 h ( 

4、t ) = 0，对于17结点m和n （n 是m的子结点） 有h ( m ) – h ( n ) <= 1 = Cost ( m, n ) 满足单调限制条件。最重要的是应用了曼哈顿距离。同时可以根据深度和h值，在找最优解的时候，对超过目前最优解的地方进行剪枝，这可以导致搜索深度的急剧减少㈢主要功能利用A*算法求解八数码问题五、主要代码importcopydefinit(target):#初始化tlist，方便计算曼哈顿距离tlist=[0forainrange(9)]foriinrange(3):forjinrange(3):tl

5、ist[target[i][j]]=[i,j]returntlistdefgetStep(tlist,current):#获取曼哈顿距离step=0foriinrange(3):forjinrange(3):ifcurrent[i][j]!=0:k=tlist[current[i][j]]step=step+abs(k[0]-i)+abs(k[1]-j)returnstepdefinTable(item,table):#在不在openedorclosed表中it=item[2]fortintable:t2=t[2]ift2==i

6、t:returnTruereturnFalsedefroop(tlist,item,target):opened=[]closed=[]17opened.append(item)whilelen(opened):#opened表的长度不为0current=opened[0]#第一个元素delopened[0]#从opened中删除closed.append(current)#移动到closedifcurrent[2]==target:#已经找到目标，直接返回，目标已经插入到closedreturnclosed#以0为点移动#do

7、wn0下移cur1=copy.deepcopy(current)foriinrange(3):forjinrange(3):ifcur1[2][i][j]==0andi!=2:#不是最底行，下移，交换位置temp=cur1[2][i+1][j]cur1[2][i+1][j]=cur1[2][i][j]cur1[2][i][j]=tempbreakifcur1!=current:#父是closed最后一个元素的位置son1=[current[0]+1,getStep(tlist,cur1[2]),cur1[2],len(close

8、d)-1]ifnotinTable(son1,closed):ifnotinTable(son1,opened):#insertintoopened,方法是按step值小的在前排序插入iflen(opened)==0:opened.append(son1)els