文档介绍：枣庄学院计算机科学系课程设计任务书题目: 用 A* 算法解决八数码问题学号: ************** 姓名: ******* 专业: 计算机科学与技术课程: 人工智能指导教师: **** 职称: 讲师完成时间: 2011 年 12月----2011 年 12月枣庄学院计算机科学系制 201 1年12月01日摘要: 八数码问题是人工智能中一个很典型的智力问题。本文以状态空间搜索的观点讨论了八数码问题,给出了八数码问题的 Java 算法与实现的思想, 分析了 A 算法的可采纳性等及系统的特点。关键词九宫重排, 状态空间, 启发式搜索,A 算法 1 引言九宫重排问题是人工智能当中有名的难题之一。问题是在 3×3 方格盘上,放有八个数码, 剩下一个位置为空, 每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置, 要求通过一系列的数码移动, 将初始状态转化为目标状态。状态转换的规则: 空格四周的数移向空格, 我们可以看作是空格移动, 它最多可以有4个方向的移动, 即上、下、左、右。九宫重排问题的求解方法, 就是从给定的初始状态出发, 不断地空格上下左右的数码移至空格, 将一个状态转化成其它状态, 直到产生目标状态。一、问题描述待解决问题的解释八数码游戏(八数码问题)描述为:在 3×3 组成的九宫格棋盘上,摆有八个将牌,每一个将牌都刻有 1-8 八个数码中的某一个数码。棋盘中留有一个空格, 允许其周围的某一个将牌向空格移动,这样通过移动将牌就可以不断改变将牌的布局。这种游戏求解的问题是:给定一种初始的将牌布局或结构(称初始状态) 和一个目标的布局(称目标状态) ,问如何移动将牌,实现从初始状态到目标状态的转变。问题的搜索形式描述( 4 要素) 初始状态: 8 个数字将牌和空格在九宫格棋盘上的所有格局组成了问题的状态空间。其中,状态空间中的任一种状态都可以作为初始状态。后继函数: 通过移动空格(上、下、左、右)和周围的任一棋子一次,到达新的合法状态。目标测试: 比较当前状态和目标状态的格局是否一致。路径消耗: 每一步的耗散值为 1 ,因此整个路径的耗散值是从起始状态到目标状态的棋子移动的总步数。解决方案介绍(原理) 对于八数码问题的解决,首先要考虑是否有答案。每一个状态可认为是一个 1×9 的矩阵,问题即通过矩阵的变换,是否可以变换为目标状态对应的矩阵? 由数学知识可知,可计算这两个有序数列的逆序值,如果两者都是偶数或奇数, 则可通过变换到达,否则,这两个状态不可达。这样,就可以在具体解决问题之前判断出问题是否可解,从而可以避免不必要的搜索。如果初始状态可以到达目标状态,那么采取什么样的方法呢? 常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找,直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支, 再查找另一个分支,以至找到目标为止。广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法,可是当状态空间十分大,且不预测的情况下就不可取了。他的效率实在太低,甚至不可完成。由于八数码问题状态空间共有 9! 个状态, 对于八数码问题如果选定了初始状态和目标状态,有 9!/2 个状态要搜索,考虑到时间和空间的限制,在这里采用 A*算法作为搜索策略。在这里就要用到启发式搜索启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径, 提到了效率。在启发式搜索中,对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。启发中的估价是用估价函数表示的,如: f(n) =g(n) +h(n) 其中 f(n) 是节点 n的估价函数,g(n) 是在状态空间中从初始节点到 n节点的实际代价,h(n) 是从 n到目标节点最佳路径的估计代价。在此八数码问题中, 显然 g(n) 就是从初始状态变换到当前状态所移动的步数, 估计函数 f(n) 我们就可采用当前状态各个数字牌不在目标状态未知的个数,即错位数。二、算法介绍搜索算法一般介绍不管哪种搜索,都统一用这样的形式表示:搜索的对象是一个图,它面向一个问题,不一定有明确的存储形式,但它里面的一个结点都有可能是一个解(可行解),搜索的目的有两个方面,或者求可行解,或者从可行解集中求最优解。搜索算法可分为两大类:无信息的搜索算法和有信息的搜索算法。无信息的搜索又称盲目搜索,其特点是只要问题状态可以形式化表示,原则上就可用使用无信息的搜索,无信息搜索有如下常见的几种搜索策略:广度优先搜索、代价一致搜索、深度优先搜索、深度有限搜索、迭代深入优先搜索、双向搜索。我们说 DFS 和BFS 都是蛮力搜索,因