人工智能实验（一）实验报告
班级一实验题目
图搜索与问题求解：本次实验主要用来熟悉图搜索技术在具体问题中的求解过程，下面主要以八数码问题展开，也可以以其它题目展开实验。
姓名：
学号：
二实验目的
1．熟悉和掌握启发式搜索的定义、估价函数和算法过程；
2．理解和掌握启发式搜索过程，能够用选定的编程语言求解八数码问题，理解求解流程和搜索顺序；3．比较并分析图搜索策略的实质，通过实验理解启发式搜索的意义。
三实验要求
1．自己定义启发式函数能正确求解出从初始状态到目标状态的移动路线；2．要求界面显示初始状态、目标状态和中间搜索步骤；3．对不可达状态能进行正确识别；4．对所采用的启发式函数做出性能分析。
四数据结构
structChess棋盘i
tcellNN数码记录数组i
tValue评估函数值Directio
BelockDirec屏蔽方向structChessPare
t父节点
CLOSED表的动态数据结构（使用堆栈）来专门记录考查过的节点OPEN表的动态数据结构（使用堆栈）来专门登记当前待考查的节点
f五实验算法
1．说明有解和无解如何判定：将九宫格中数字顺序排列后，形成一个包含0在内的9位数字序列，该字串可用来表示九宫格的当前状态，其中0表示空格所在位置。当空格上下、左右移动时，易知序列的逆序值奇偶性不会发生改变。由此可知，九宫问题的362880种状态被分成逆序值为奇数和逆序值为偶数两部分，每一部分内任意两种状态相互可达。在八数码问题中，有些状态之间是不可达的。如果我们能在一开始先判断初始状态和目标状态之间是否可达，这样可以避免不可达状态之间的盲目求解。两个状态之间是否可达可以通过两个状态逆序值的奇偶性进行判断。我们把每个状态看作一个数列，然后计算数列的逆序值，若两个数列逆序值的奇偶性相同，则对应的两个状态是可达的，否则不可达。（注：求逆序值不把空格算在内）。如图2所示状态：
256
38
147
图2棋局示例
它对应的数列是：23158467（不包括空格）。对于一个数列，数列中每个数的逆序值是指位于这个数前面的比这个数大的数的个数。数列的逆序值就是数列中每个数的逆序值之和。逆序值求法：例：23158467的逆序值为6，求解过程为：002121300245481681786而状态12345678的逆序值自然就是0。2说明启发式函数如何设定：1简单设定：通过判断相同位置存放的的数字是否相同来计算启发函数2曼哈顿距离：曼哈顿距离（Ma
hatta
Dista
ce），又称为出租车距离，是由十九世纪的赫尔曼闵r