人工智能论文：九宫重排问题.docx

滨江学院
课程论文
课程名称: 人工智能
院系滨江学院
专业自动化
学号
姓名
指导老师
二O一六年六月二十日
目录
引言 4
一、问题描述 4
待解决问题的解释 4
问题的搜索形式描述(4要素) 4
解决原理 5
二、算法介绍 5
搜索算法一般介绍 5
算法伪代码 6
三、数据介绍 8
数据结构 8
实验结果 9
系统中间及最终输出结果(要求有屏幕显示) 10
参考文献 12
摘要
人工智能是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。人工智能的研究方向、研究领域、应用领域值得我们关注和探讨。
本文以状态空间搜索的观点讨论了八数码问题,给出了八数码问题的Java算法与实现的思想,分析了A*算法的可采纳性等及系统的特点。
关键词:九宫重排,状态空间,启发式搜索,A*算法
引言
九宫重排问题是人工智能当中有名的难题之一。问题是在3×3方格盘上,放有八个数码,剩下一个位置为空,每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置,要求通过一系列的数码移动,将初始状态转化为目标状态。状态转换的规则:空格四周的数移向空格,我们可以看作是空格移动,它最多可以有4个方向的移动,即上、下、左、右。九宫重排问题的求解方法,就是从给定的初始状态出发,不断地空格上下左右的数码移至空格,将一个状态转化成其它状态,直到产生目标状态。
一、问题描述
待解决问题的解释
八数码游戏(八数码问题)描述为:在3×3组成的九宫格棋盘上,摆有八个将牌,每一个将牌都刻有1-8八个数码中的某一个数码。棋盘中留有一个空格,允许其周围的某一个将牌向空格移动,这样通过移动将牌就可以不断改变将牌的布局。这种游戏求解的问题是:给定一种初始的将牌布局或结构(称初始状态)和一个目标的布局(称目标状态),问如何移动将牌,实现从初始状态到目标状态的转变。
问题的搜索形式描述(4要素)
初始状态:
8个数字将牌和空格在九宫格棋盘上的所有格局组成了问题的状态空间。其中,状态空间中的任一种状态都可以作为初始状态。
后继函数:
通过移动空格(上、下、左、右)和周围的任一棋子一次,到达新的合法状态。
目标测试:
比较当前状态和目标状态的格局是否一致。
路径消耗:
每一步的耗散值为1,因此整个路径的耗散值是从起始状态到目标状态的棋子移动的总步数。
解决原理
对于八数码问题的解决,首先要考虑是否有答案。每一个状态可认为是一个1×9的矩阵,问题即通过矩阵的变换,是否可以变换为目标状态对应的矩阵?由数学知识可知,可计算这两个有序数列的逆序值,如果两者都是偶数或奇数,则可通过变换到达,否则,这两个状态不可达。这样,就可以在具体解决问题之前判断出问题是否可解,从而可以避免不必要的搜索。
常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找,直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支,再查找另一个分支,以至找到目标为止。广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法。于八数码问题状态空间共有9!个状态,对于八数码问题如果选定了初始状态和目标状态,有9!/2个状态要搜索,考虑到时间和空间的限制,在这里采用A算法作为搜索策略。在这里就要用到启发式搜索
启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径,提到了效率。在启发式搜索中,对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。
二、算法介绍
搜索算法一般介绍
不管哪种搜索,都统一用这样的形式表示:搜索的对象是一个图,它面向一个问题,不一定有明确的存储形式,但它里面的一个结点都有可能是一个解,搜索的目的有两个方面,或者求可行解,或者从可行解集中求最优解。
搜索算法可分为两大类:无信息的搜索算法和有信息的搜索算法。无信息的搜索又称盲目搜索,其特点是只要问题状态可以形式化表示,原则上就可用使用无信息的搜索,无信息搜索有如下常见的几种搜索策略:广度优先搜索、代价一致搜索、深度优先搜索、深度有限搜索、迭代深入优先搜索、双向搜索。
为了改善上面的算法,我们需要对展开后续结点时对子结点有所了解,这里需要一个估值函数,估值函数就是评价函数,它用来评价子结点的好坏,因为准确评价是不可能的,所以称为估值。这就是我们所谓的有信息搜索。如果估值函数只考虑结点的某种性能上的价值,而不考虑深度,比较有名的就是有序搜索,它着重看好能否找出解,