九宫格算法

八数码以及十五数码问题

基于人工智能的状态空间搜索策略研究

——八数码问题求解

一、实验问题

2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用；

3. 熟悉对八数码问题的建模、求解及编程语言的应用。

四、实验数据及步骤

（一、） 实验内容

八数码问题：在 3×3 的方格棋盘上，摆放着 1 到 8 这八个数码，有 1 个方格

是空的，其初始状态如图 1 所示，要求对空格执行空格左移、空格右移、空格

上移和空格下移这四个操作使得棋盘从初始状态到目标状态。

我采用了 struct Node 数据类型

typedef struct _Node{

int digit[ROW][COL];

int dist; // distance between one state and the destination 一个表和目

的表的距离

int dep; // the depth of node 深度

// So the comment function = dist + dep.估价函数值

int index; // point to the location of parent 父节点的位置

} Node; 2.发生器函数

定义的发生器函数由以下的四种操作组成：

Assign(node_down, index);//向下扩展的节点

int dist_down = MAXDISTANCE;

Node node_left;

(4)将当前状态的空格右移

int dist_right = MAXDISTANCE;

通过定义结点状态和发生器函数，就解决了 8 数码问题的隐式图的生成问

题。接下来就是搜索了。

3.图的搜索策略

经过分析，8 数码问题中可采用的搜速策略共有：1.广度优先搜索、2.深度

优先搜索、2.有界深度优先搜索、4.最好优先搜索、5.局部择优搜索，一共五

种。其中，广度优先搜索法是可采纳的，有界深度优先搜索法是不完备的，最

好优先和局部择优搜索法是启发式搜索法。

实验时,采用了广度(宽度)优先搜索来实现。

（三、）广度(宽度)优先搜索原理

1. 状态空间盲目搜索——宽度优先搜索

其基本思想是，从初始节点开始，向下逐层对节点进形依次扩展，并考察它

是否为目标节点，再对下层节点进行扩展（或搜索）之前，必须完成对当层的

所有节点的扩展。再搜索过程中，未扩展节点表 OPEN 中的节点排序准则是：

2. 宽度优先算法如下：

步 2 若 OPEN 表为空，则搜索失败，问题无解

步 4 若目标结点 Sg=N，则搜索成功，问题有解

OPEN 表的尾部，转步 2

3.宽度优先算法流程图