八数码.docx

深 圳 大 学 实 验 报 告 课程名称： 人工智能 实验项目名称： 八数码问题 学院： 信息工程 专业： 电子信息工程 指导教师： 实验时间： 2016.4.8 实验报告提交时间： 2016.4.15教务部制实验目的：问题说明：这是一个九宫格，其中有八个格子有数字，还有一个格子是空位，和空位相邻的数字格子可以和空位相互交换，游戏的最终目的就是让这些数字形成一个有序的局面。假如说我们有左边这样一个初始状态，我们现在就是想找到一种最快捷的方法，使左边的初始状态转换为右边的最终状态。目的：通过自己编写代码，实现上述过程的移动，并用图片来展示这个过程。实验思路：采用A*启发式有哪些信誉好的足球投注网站算法，进行启发式有哪些信誉好的足球投注网站，选择路径最优的进行下一步有哪些信誉好的足球投注网站，直至到达目标状态。在这个试验中，我选择用python作为实现该算法的编程语言。方法、步骤：1：定义一个opened表和一个closed表，opened表用来存储下一个移动可能的状态，closed表用来存储每一步的移动。2：计算移动后的状态与目标状态的曼哈顿距离，并且选择曼哈顿距离最小的存储进closed表中3：在这个过程中会先判断移动后的状态在不在closed表中，若是，则直接不进行计算，避免无效移动。4：由于所有的过程状态都在closed表中，因此只要把closed表中对应的状态以图片的形式显示出来就行了。代码：#作者名，我的英文名是code__author__=code#导入模块from PIL import Image,ImageTkimport 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 tlistdef 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 stepdef is_solve(start,target): #判断该八数码问题是否有解 count1=0 count2=0 a=[] b=[] for i in range(3): for j in range(3): a.append(start[i][j]) b.append(target[i][j]) for i in range(1,9): for j in range(0,i): if a[i]a[j]and a[j]!=0: count1=count1+1 if b[i]b[j]and b[j]!=0: count2=count2+1 if count1%2==count2%2: return True else: return False#判断移动后的状态在不在closed表里面def inTable(item,table): for i in table: if item==i: return True return False#找到空格的位置def find_zeros(current): for i in range(3): for j in range(3): if current[i][j]==0: raw=i col=j item=[raw,col] return itemdef move(tlist,start,target): opened = [] closed = [] opened.append(start) while len(opened):#opened表的长度不为0 current = opened[0] #第一个元素 del opened[0] #从opened中删除 closed.append(current) #移动到closed if current== target:#已经找到目标，直接返回，目标已经插入到closed return closed #上移 cur1=copy.deepcopy(current) item=find_zeros(cur1) if item[0]!=0: temp=cur1[item[0]][item[1]] cur1[item[0]][item[1]]=cur1[item[0]-1][item[1]] cur1[item[0]-1][item[1]]=temp i