内容发布更新时间 : 2024/6/26 23:49:25星期一 下面是文章的全部内容请认真阅读。

课 程 论 文

论文名称 姓 名 班 级 学 号 课程名称 任课教师 学 期 所在院系 八数码问题 人工智能 摘 要

八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。

所谓问题的一个状态就是棋子在棋盘上的一种摆法。棋子移动后，状态就会发生改变。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。 八数码问题一般使用搜索法来解。

搜索法有广度优先搜索法、深度优先搜索法、A*算法等。这里详细讲述A*算法。

关键词:八数码问题；空间状态；搜索法；A*算法

一、 实验目的

理解并熟悉掌握A*算法。 二、 实验内容

九宫格中有8个数码，其中只有一个空，规则是只能把一个数码移动到空的格子中，要求从一个初始状态移动到一个目标状态所要花费的最少步数

三、问题的搜索形式描述（4要素） 初始状态：

8个数字将牌和空格在九宫格棋盘上的所有格局组成了问题的状态空间。其中，状态空间中的任一种状态都可以作为初始状态。 后继函数：

通过移动空格（上、下、左、右）和周围的任一棋子一次，到达新的合法状态。 目标测试：

比较当前状态和目标状态的格局是否一致。 路径消耗：

每一步的耗散值为1，因此整个路径的耗散值是从起始状态到目标状态的棋子移动的总步数。 四、解决方案介绍（原理）

常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。 广