滨江学院课程论文课程名称:人工智能院系滨江学院专业自动化学号20132336931姓名周程指导老师孙玉宝二Ｏ一六年六月二十日1目录引言..................................................................................................................................................3一、问题描述.................................................................................................................................31.1待解决问题的解释...........................................................................................................31.2问题的搜索形式描述（4要素）....................................................................................31.3解决原理...........................................................................................................................4二、算法介绍.................................................................................................................................42.1搜索算法一般介绍...........................................................................................................42.2算法伪代码.......................................................................................................................5三、数据介绍...................................................................................................................................73.1数据结构...........................................................................................................................73.2实验结果...........................................................................................................................83.3系统中间及最终输出结果（要求有屏幕显示）...........................................................9参考文献.................................................................................................................................112摘要人工智能是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。人工智能的研究方向、研究领域、应用领域值得我们关注和探讨。本文以状态空间搜索的观点讨论了八数码问题，给出了八数码问题的Java算法与实现的思想，分析了A*算法的可采纳性等及系统的特点。关键词:九宫重排，状态空间，启发式搜索，A*算法3引言九宫重排问题是人工智能当中有名的难题之一。问题是在3×3方格盘上，放有八个数码，剩下一个位置为空，每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置，要求通过一系列的数码移动，将初始状态转化为目标状态。状态转换的规则：空格四周的数移向空格，我们可以看作是空格移动，它最多可以有４个方向的移动，即上、下、左、右。九宫重排问题的求解方法，就是从给定的初始状态出发，不断地空格上下左右的数码移至空格，将一个状态转化成其它状态，直到产生目标状态。一、问题描述1.1待解决问题的解释八数码游戏（八数码问题）描述为：在3×3组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有1-8八个数码中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。这种游戏求解的问题是：给定一种初始的将牌布局或结构（称初始状态）和一个目标的布局（称目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。1.2问题的搜索形式描述（4要素）初始状态：8个数字将牌和空格在九宫格棋盘上的所有格局组成了问题的状态空间。其中，状态空间中的任一种状态都可以作为初始状态。后继函数：通过移动空格（上、下、左、右）和周围的任一棋子一次，到达新的合法状态。目标测试：比较当前状态和目标状态的格局是否一致。路径消耗：4每一步的耗散值为1，因此整个路径...
