精选优质文档-倾情为你奉上 用A*算法解决八数码问题1 问题描述1.1 待解决问题的解释 八数码游戏(八数码问题)描述为:在33组成的九宫格棋盘上,摆有八个将牌,每一个将牌都刻有1-8八个数码中的某一个数码。棋盘中留有一个空格,允许其周围的某一个将牌向空格移动,这样通过移动将牌就可以不断改变将牌的布局。这种游戏求解的问题是:给定一种初始的将牌布局或结构(称初始状态)和一个目标的布局(称目标状态),问如何移动将牌,实现从初始状态到目标状态的转变。 1.2 问题的搜索形式描述(4要素) 初始状态:8个数字将牌和空格在九宫格棋盘上的所有格局组成了问题的状态空间。其中,状态空间中的任一种状态都可以作为初始状态。后继函数:通过移动空格(上、下、左、右)和周围的任一棋子一次,到达新的合法状态。目标测试:比较当前状态和目标状态的格局是否一致。路径消耗:每一步的耗散值为1,因此整个路径的耗散值是从起始状态到目标状态的棋子移动的总步数。1.3 解决方案介绍(原理)对于八数码问题的解决,首先要考虑是否有答