人工智能实验报告
学 院：信息科学与工程学院
班 级： 自动化0901班 学 号：
姓 名： 孙锦岗
指导老师： 刘丽珏 日 期：2011年12月20日
一、 实验名称、目的及内容
实验名称：
八数码难题的搜索求解演示
实验目的：
加深对图搜索策略概念的理解，掌握搜索算法。
实验内容要求：
以八数码难题为例演示广度优先或深度优先搜索、A算法（本实验使用的是广度优先搜索）的搜索过程，争取做到直观、清晰地演示算法。
八数码难题：在3×3方格棋盘上，分别放置了标有数字1,2,3,4,5,6,7,8的八张牌，初始状态S0，目标状态如图所示，可以使用的操作有:空格上移，空格左移，空格右移，空格下移。试编一程序实现这一搜索过程。
二、实验原理及基本技术路线图
实验原理：
八数码问题中，程序产生的随机排列转换成目标共有两种可能，而且这两种不可能同时成立，也就是奇数排列和偶数排列。我们可以把一个随机排列的数组从左到右从上到下用一个数组表示，例如｛８，
７，１，５，２，６，３，４，０｝其中０代表空格。它在奇序列位置上。
在这个数组中我们首先计算它能够重排列出来的结果，公式就是：∑（Ｆ（Ｘ））＝Ｙ，其中Ｆ（Ｘ），就是一个数他前面比这个数小的数的个数，Ｙ为奇数和偶数个有一种解法。那么上面的数组我们就可以解出它的结果。 数据结构：
本实验使用的数据结构是队列，应用队列先进先出的特点来实现对节点的保存和扩展。首先建立一个队列，将初始结点入队，并设置队列头和尾指，然后取出队列（头指针所指）的结点进行扩展，从它扩展出子结点，并将这些结点按扩展的顺序加入队列，然后判断扩展出的新结点与队列中的结点是否重复，如果重复则，否则记录其父结点，并将它加入队列，更新队列尾指针，然后判断扩展出的结点是否是目标结点，如果是则显示路径，程序结束。否则如果队列头的结点可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步，知道扩展出的结点是目标结点结束，并显示路径。
算法分析：
九宫问题的求解方法就是交换空格（０）位置，直至到达目标位置为止。如图所示：