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

重庆交通大学计算机与信息学院
验证性实验报告
班级:计算机科学与技术专业 2013级1班
学号: 631306050103
姓名: 姜彦斌
实验项目名称: 启发式搜索
实验项目性质: 验证性实验
实验所属课程: 人工智能
实验室(中心): 软件中心实验室(语音楼8楼)
指导教师: 朱振国
实验完成时间: 2016 年 06 月 10 日
评阅意见:
实验成绩: 签名: 年月日
一、实验目的
理解和掌握A*算法。
二、实验内容及要求
在8数码问题中,利用策略函数判断搜索,并使用A*算法减少搜索目标。
三、实验设备及软件
Windows10 Build 14361 64bit(操作系统)
(运行环境)
++ (代码编写环境)
四、设计方案
㈠题目
在8数码问题中,利用策略函数判断搜索,并使用A*算法减少搜索目标。
㈡设计的主要思路
估价函数是搜索特性的一种数学表示,是指从问题树根节点到达目标节点所要耗费的全部代价的一种估算,记为f(n)。估价函数通常由两部分组成,其数学表达式为
f(n)=g(n)+h(n)
其中f(n) 是节点n从初始点到目标点的估价函数,g(n) 是在状态空间中从初始节点到n节点的实际代价,h(n)是从n到目标节点最佳路径的估计代价。保证找到最短路径(最优解)的条件,关键在于估价函数h(n)的选取。估价值h(n)<= n到目标节点的距离实际值,这种情况下,搜索的点数多,搜索范围大,效率低。但能得到最优解。如果估价值>实际值, 搜索的点数少,搜索范围小,效率高,但不能保证得到最优解。
搜索中利用启发式信息,对当前未扩展结点根据设定的估价函数值选取离目标最近的结点进行扩展,从而缩小搜索空间,更快的得到最优解,提高效率。
      进一步考虑当前结点与目标结点的距离信息,令启发函数h ( n )为当前8个数字位与目标结点对应数字位距离和(不考虑中间路径),且对于目标状态有 h ( t ) = 0,对于结点m和n (n 是m的子结点) 有h ( m ) – h ( n ) <= 1 = Cost ( m, n ) 满足单调限制条件。
最重要的是应用了曼哈顿距离。同时可以根据深度和h值,在找最优解的时候,对超过目前最优解的地方进行剪枝,这可以导致搜索深度的急剧减少
㈢主要功能
利用A*算法求解八数码问题
五、主要代码
import copy
def init(target):#初始化tlist,方便计算曼哈顿距离
tlist = [0 for a in range(9)]
for i in range(3):
for j in range(3):
tlist[target[i][j]]=[i,j]
return tlist
def getStep(tlist,current):#获取曼哈顿距离
step = 0
for i in range(3):
for j in range(3):
if current[i][j]!=0:
k = tlist[current[i][j]]
step = step + abs(k[0]-i) + abs(k[1]-j)
return step
def inTable(item,table):#在不在opened or closed表中
it = item[2]
for t in table:
t2 = t[2]
if t2==it:
return True
return False
def roop(tlist,item,target):
opened = []
closed = []
(item)
while len(opened):#opened表的长度不为0
current = opened[0] #第一个元素
del opened[0] #从opened中删除
(current) #移动到closed
if current[2] == target:#已经找到目标,直接返回,目标已经插入到closed
return closed
#以0为点移动
#down 0下移
cur1 = (current)
for i in range(3):
for j in range(3):
if cur1[2][i][j]==0 and i!=2:#不是最底行,下移,交换位置
temp = cur1[2][i