八数码问题A算法的实现及性能分析(共18页).doc

精选优质文档-倾情为你奉上八数码问题A*算法的实现及性能分析 计算机科学与技术学院专业：计算机科学与技术 杨凯迪目录一、8数码问题1.问题描述八数码问题是指这样一种游戏：将分别标有数字1，2，3，8 的八块正方形数码牌任意地放在一块33 的数码盘上。放牌时要求不能重叠。于是，在33 的数码盘上出现了一个空格。现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则，不断移动该空格方块以使其和相邻的方块互换，直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右4个方向可移动，在四个角落上有2个方向可移动，在其他位置上有3个方向可移动，问题描述如图1-1所示 初始状态 过渡状态 最终状态图1-1 八数码问题执行过程2.