A算法深度优先实现八数码问题

实 验 报 告

课程名称   人工智能   

实验项目 八数码难题 ______________

实验仪器 电脑  、 

系 别 ____________

专 业 __ _____

班级/学号

学生姓名 _ _________

九宫格中有 8 个数码，其中只有一个空，规则是只能把一个数码移动到空的格子

中，要求从一个初始状态移动到一个目标状态所要花费的最少步数

【算法分析】

 解决此类问题的办法是宽度搜索，深度搜索耗时太大无法接受。当需要移动的步数很多

时，普通的宽度搜索仍旧无法满足需要，需要对其进行优化。

 这个问题也可以推广到流行的拼图游戏。

【具体步骤】

一、确定问题规模（考虑搜索的时间代价）

二、确定产生式规则（如果规则太多，则时间代价会很大）

三、套用经典宽度搜索框架写程序

&!""不在位的数目$%

!""耗散值$%'#$%$%

(!

()!

(!

*!"(++++++++++++++++++++("

# !""棋盘初始状态

# !""棋盘目标状态

,!

(,(!""- 表和  表

$(,(%!""向  表中插入新节点

)$(%!""扩展节点

$(%!""打印结果

0$(,(, %!

""是否在 - 表或  表中

$ %!""打印棋盘状态

&$ %!""求不在位棋子的个数

$%!""初始化，获得棋盘初始状态和目标状态

0$(,(%!

$ ,%!

$(%!

"(

 (  '''  1234-

''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''

 (

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''