八数码的启发式搜索算法及实现
第3卷第3期2004年9月
安徽职业技术学院学报
FANHUIVOCATIONALTECHNICALCOLLEGEJOURNALO
V01．3NO．3
Sep．2004
八数码的启发式搜索算法及实现
唐朝舜，董玉德
(中国科学技术大学信息学院，安徽合肥230022)
摘要：文章针对八数码的求解，通过使用并行指针结合所设计的经验式启发函数，在无需回溯的情况下能求解所有的测试数据，且测试结果与理论值相同。
关键词：八数码；启发式搜索；逆序数；启发函数中图分类号：TP312
文献标识码：A
文章编号：1672—9536(2004)03—0009-04
Abstract：ThispaperisaboutthesolutionofEight—figurePuzzles．Byusingexperiencedheuristic
functiondesignedbyparellelpointerallthe
results
are
test
datawillbesolvedwithoutanyinversion，andthetest
thesame
as
theorticalvalueinwhichthealgorithmisrealised．
Puzzles；heurcstic
search
technique；versa
ordinal
figure；heuristic
Keywords：Eight—figure
function
目前关于八数码的算法实现比较多，但现有的一般搜索方法需要回溯，故其实现较为复杂。本文对此进行改进，采用并行指针结合所给的经验函数，在搜索目标状态的过程中，不需要回溯，因而有更好的时间与空间复杂度。通过大量的实验数据表明，采用该算法所得结果与A*算法基本一致。
1
2
胛
图1初始状态
孵
图2
目标状态
问题分析和模型表示
(1)关于解的存在性的结论
对于任意给定的一组数，用0代表空格，则九
x
问题描述在一个3
3的九宫中有1—8这8个数及一
宫图初始状态为数0～8的一个排列，记为nONl咒2咒3咒4，z5，z6727，28。使用线性代数的有关理论可
个空格随机地摆放在其中的格子里。如图1所示。
现在要求实现这样的问题：将该八个数码调整为
图2所示的形式。调整的规则是：每次只能将与空格(上、下或左、右)相邻的一个数字平移到空格中。实质是要求给出一个合法的走步序列，实现从初始状态到目标状态的转变。
以证明，与目标结点逆序数(这里的逆序数计算不包括O)奇偶性相同的八数码才可通过一定的移动
到达目标状态，也即对于任一个目标状态节点，只有(1／2)×91—181440个状态有解。
(2)一般搜索方法的比较
在八数码的求解中，一般有深度优先搜索、广
收稿日期：2004—03—16
基金项目：安徽省教委科研资助项目(2001AHZK42A)
作者简介：唐朝舜(1963一)，男，安徽巢湖人，助教，中国科学技术大学信息学院研究生．主要研究
向：
库．
10
安徽职业技术学院学报
第3卷
度优先搜索和启发式搜索，对于前两种搜索，效率底，而且在很多情况下得不到解，更难得到最优
无序并将值增1)。而f(n)一d(以)+h(咒)，其中d(咒)是已搜索的深度。
(3)搜索过程中节点的处理
对于求得的厂(孢)值若有m个相同’，则取第一个扩展，对于扩展后的节点，放入OPEN表中，同时令CLoSE表指向已扩展的节点，再从OPEN表中选取值最小的，这样OPEN表和CLOSE表是交叉连接的，即一个节点有两个指针节点且最多拥有两个指针，但因此省略了回溯。
(4)对于一个初始状态，其搜索图如下：
田始节点
解，按平均节点数计算，前两种搜索所产生的节点
数n与深度deep之间的关系有咒一3如”，这就使得我们必须要采用启发式搜索。在这里我采用的启
发函数是一个经验式的函数，其中包含了启发信
息，h(，2)一2*compare(n)+3*S(，2)(compare(n)是用来求出所给的节点对应于目标结点棋子摆放位置不相同的个数，S(挖)是求出所给节点的无序度，目标节点的无序度为0，对于所给节点，若
相邻两个元素值相等为1，则认为有序，否则认为
休／L1I
2
8
Deep=l
乃l户24
卜——_}—一
7
——一
Deep=2
affn)=17
F霄
I
7
I
Deep=2
t(n)=30
3
—_
什卜——卜
DeetF3
4
6
一——一
Deep=3
肋)=18．
3
—_
如)218』
4
—_
／——JTDeep=3‘]广
苁n)_26
D州
／In)=19
5
Deep=4
吓
Deep=4
8。
一——Deep=4
^n户24毒
刊一
制㈣H
如)=14
厦n)=21
4
5
Deep=5
励户10
Deep--6
乃1)《
目标节点
Deep=6
／《n)=22
6
第3期
唐朝舜，等：八数码的启发式搜索算法及实现
3算法设计如下：
设计本题算法的构思如下：
(1)把起始节点s作为Open表的起始节点，
计算厂(s)，同时将节点s也作为Close表的起始节
点；
(2)从Open表中选择一个厂值最小的节点
J，若为目标节点，则选择节点，若有几个节点值相同且都最小，则选取第一个获得的节点为节点1；
(3)令J节点Close域指向父辈节点的Close域，从而构成Close表。若，是目标节点，则搜索成功，转向(6)；
(4)扩展节点J，生成其全部后继节点，对于J的每个后继节点J：
(口)计算八．，)．
(6)如果歹的Open域指针及Close域指针皆为空，则将其加入父辈节点的Open域中，构成Open表。
(5)转向(2)循环；
(6)若有解，从开始节点的Close域的开始打
印，直至表尾，得到一个解路径。
4
结束语
本问题是直接用Pascal语言实现的一个设
计。由于采用了树形结构来存储节点，使程序的设计流程较为简洁，思想也比较简单。为了设计方便，同时根据题意，将目标节点定义为一个常量数
组，当然稍作改动，也可对不定的目标节点来求解，同时为了防止堆溢出，将搜索深度定义为40，这对有解的八数码问题而言，都能求得一个较优解，同时在一开始就判断逆序数的奇偶性，并给出了是否有解的提示。
5
附录
programPalace(input，output)；
type
NinePalace=array[1．．3，1．．3]of
Integer；
1ink一“node：
node==record
parent：link；deep：Integer；extend：boolean；
Palace：NinePalace；next：link；
end；
{定义目标八数码)
const
aim：NinePalace一((1，2，3)，(8，0，4)，(7，6，5))；
{判断起始节点的逆序数}
judgestart：=judge(temp)；
{判断起始节点的逆序数)judgeend：=judge(aim)；
{判断两逆序数的奇偶性是否相等)
if(judgestartm
od2)一(judgeendmod2)thenelse{提示该起始节点无法到达目标节点){将初始节点的Open域及Close域初始化}
new(crunode)；
crunode“．next：一NIL；
crunode4．palace：一temp；
new(open)；new(close)；
{G的值为与目标节点的差值)
G：=compare(p“．palace，aim)；
{eom的值即为函数F(n)的值)
eom：=p“．deep+2*G+3*S(p“．Palace)；
ifg0thenbegin
writeln(’请稍候…’)；
{主循环开始，若找到则G的值为0，否则搜索溢
出)
while(G0)and(open“．next一1)do
begin
if
open
4．next“．next----nilthen
begin
p：=open
4．next；
open“．next：=Nil；
endelsebegin
new(p)；
12
安徽职业技术学院学报
new(q)；
第3卷
writeln(’九宫搜索深度已到达40，为避免内
{在0PEN表中寻找值最小的点)
存溢出，请重新给定起始节点!!!’)；
q：20pen；
whileq6．next(>pdo
q：=q‘．next；
q
4．next：2p‘．next；
P4．next
：=nil；
end；
{如果q不是目标节点，扩展q并放入OPEN
表，并找出值最小的节点)
crunode：2p；find：=false；
ifclose“．next=nilthen
begin
p“．next：=close“．next；
．close6．next：=p；
end
elsebegin
whilenot(find)do
{在close表中查找是否存在给定的节点，若
存在，返回节点所在位置且置find为true；)
end；
end
elsebegin
G：一一1；end；
end；
ifg=0then
begin
{遍历CLOSE表并输出每个节点)
writeln(’TotalSeachDeepis：’，com
一2)；writeln；
end
elsewriteln(’八数码搜索失败!!’)；
endse
writeln(’起始节点就是目标节点!!!’)；
ndelsewriteln(’所给节点无法移至目标节点!!)；
1]蔡自兴，徐光桔．人工智能及其应用[M]．北京：清华
大学出版社，1996，5(2)．
2]姚雪梅．人工智能中A*算法的程序实现[J]-电脑
与信息技术，2002，2(1)．
3]张信一，黎燕．基于A*算法的八数码问题的程序
求解D]．现代计算机，2003，5(14)．
(t-任编辑：李雪)
ele’参考文献：
EE[