2005年第20卷第1期电力学报Vol.20No.12005(总第70期)JOURNALOFELECTRICPOWER(Sum.70)文章编号:1005-6548(2005)01-0013-04华容道的广度优先搜索求解X)))散列查找和启发式搜索的应用曹志光(太原电力高等专科学校,山西太原030013)Breadth2FirstSearchofHuaRongDao:ApplicationofHashSearchandHeuristicSearchCAOZhi2guang(TaiyuanHigherElectricalCollege,Taiyuan030013,China)摘要:由搜索算法的选用、流程图及简要说明、搜索技术是人工智能中比较成熟的分支。状判重方法和散列查找、启发式搜索与实验结果等5态空间的盲目搜索算法主要有广度优先算法和深部分组成。重点介绍了判重方法,采用的是哈西函度优先算法。从理论上看,用广度优先算法得到的数与估值函数。第1个解,一定是1个搜索步数最少的解(如果有关键词:华容道;广度优先搜索;散列查找;启发解存在),这正好是解华容道游戏所需要的,但它的式搜索哈西函数;效率可能很低、搜索时间可能很长。因此,首选了中图分类号文献标识码:G898.2:A广度优先算法,并着力提高搜索效率和速度。Abstract:Thisarticleconsistsoffiveparts:search流程图及简要说明algorithm,flowchart,hashsearchfunction,heuristic2search,andexperimentalresults.Attentioniscon2211华容道的棋盘和棋子centratedonpreventingtheduplicationofstates,the华容道棋盘及棋盘位置编号用各数字表示为:selectedhashfunction,andtheselectedevaluation0123function.4567KeyWords:HuaRongDao;breadth2firstsearch;891011hashsearch;heuristicsearch;hashfunction1213141516171819华容道是享誉中外的智力游戏。本文介绍的搜索求解程序采用广度优先搜索算法,故能保证得棋子(把2空格也视为棋子)用以下数字表示:到最少步数解,而且由于采用了散列查找、启发式曹操0;关公1;将军2,3,4,5;兵6,7,8,9;空搜索等技术,使搜索时间也大为减少。本文论述均格10,11。以华容道的典型代表阵式/横刀立马0为例。212阵式的2种表示法1搜索算法的选用a1阵式(棋子在棋盘上的1种摆法,本文有时X收稿日期:2004-11-24修回日期:2004-12-29作者简介:曹志光(1932-),男,上海市川沙人,副教授,电磁场教学。14电力学报2005年又称之为状态或节点)的第1种表示法是用各棋子出的新节点。队列长度SIZE与初态阵式有关,/横在棋盘上的位置来表示。而各棋子在棋盘上的位刀立马0时,SIZE=4500。置,又以其左上角在棋盘上的位置来表示。故横刀数组board(1toSIZE,0to19):储存各节点的立马阵式的第1种表示法如下:第2种表示法(棋盘各方格上的棋子)。棋子01234567891011数组dep((1toSIZE):储存各节点的深度。位置1903811131416191718数组f(1toSIZE):储存各节点的估值函数。2003数组h(1toSIZE):储存各节点的启发函数。2003数组next(1toSIZE):储存启发式搜索所用的4115静态链表的指针。4675数组hash(1toSIZEh,0to1):检测第1,2类810119重复节点的散列表。数组hash_m(1toSIZEh,0to1):检测第3类按曹操、关公、4位将军、4个兵、和2个空格的重复节点的散列表。顺序,将横刀立马阵式的第1种表示法记为:数组tempstate(0to11):在其中进行有关state{1,9,0,3,8,11,13,14,16,19,17,18}。的运算。b1阵式的第2种表示法是用棋盘各方格上摆数组tempboard(0to19):在其中进行有关有哪种棋子来表示。棋盘各方格上的棋子,曹操用board的运算。1表示,关公用2表示,4位将军、4个兵和2个空格waynum节点扩展规则的编号。分别用3,4,0表示。则横刀立马阵式又可表示为:程序流程图见图1所示。31133113322334434004仿前、