人工智能实验报告
实验一 图搜索策略
一.实验目的
1.加深对各种图搜索策略概念的理解
2.进一步了解启发式搜索
3.比较分析各种搜索策略的异同
二.实验内容和步骤
以重排九宫问题为例演示各种搜索策略（包括广度优先搜索、深度优先搜索、有界深度优先搜索、最好
优先搜索和局部择优搜索等搜索策略）的搜索过程，要求程序具有一定普适性，重点是要把算法描述清楚。
四.重排九宫问题的定义
在一个 3×3 的方格棋盘上放置 8 个标有 1、2、3、4、5、6、7、8 数字的将牌，留下一个空格（用 0 表
示）。
规定与空上下左右相邻的将牌可以移入空格。问题要求寻找一条从某初始状态 S0 到目标状态 Sg 的将牌移
动
路线。
五.我对问题的描述
1.结点状态
我采用了一个 10 元数组 A=(a0,a1,a2,a3,a4,a5,a6,a7,a8,a9)来描述九宫图的每一个状态。将九宫图的
九个格子依次编号为 1、2、3、4、5、6、7、8、9。数组中的 a0 代表空格位于九宫图的那个格子，a1-a9
九个元素代表了九个格子上分别是什么将牌。例如，数组(5,2,8,3,1,0,4,7,6,5)就代表了如下的状态：
2 8 3
1 4
7 6 5
这种表示法与书上略有差别，我个人认为这样做在编程上会带来方便。
2.发生器函数
我定义的发生器函数由以下的四种操作组成：
(1)将当前状态的空格上移
(2)将当前状态的空格下移
(3)将当前状态的空格左移
(4)将当前状态的空格右移
以上的发生器函数，我在程序中（java）分别采用了 4 个类方法来实现。一个结点最多能够扩展出 4 个
结点，而扩展出的结点也不一定就会被采用，这与具体情况有关。
通过定义结点状态和发生器函数，就解决了重排九宫问题的隐式图的生成问题。接下来就是搜索了。
六.图的搜索策略
经过我的分析，重排九宫问题中可采用的搜速策略共有：1.广度优先搜索、2.深度优先搜索、2.有界深
度优先搜索、4.最好优先搜索、5.局部择优搜索，一共五种。其中，广度优先搜索法是可采纳的，有界深度
优先搜索法是不完备的，最好优先和局部择优搜索法是启发式搜索法。
各种搜索策略的搜索法：
1.广度优先搜索
