九宫排字问题是（又称八码数问题）是人工智能当中最难的问题之一。本文介绍用普通搜索方法、双向广度方法和如何缩短寻找路径的时间，以及个算法之间的利与弊。103724右图已纾可以演示得相当清楚了,由137246852状态可以衍生三个状态,假如选择了123746855,则乂衍生三个状态,继续按某略进130013行选择,一直到衍生出的新状态为目标状态END为止6856i85容易看出,这样的搜索类似」从树根廾始向茎再向叶搜索目标叶子一样的树型状。山于其规模的不断扩人,其123叶子也愈加茂密,最终的规模会大到无法控制。这样在空5685间上会大大加大搜索难度,在时间上也要消耗许多在普通搜索中遇到以下问题784a.搜索中易出现循环,即访闩某一个状态后又来访问该状态。D84b.搜索路径不佳使无法得到较好的中间状态集(即中闩状态集的元素数量过人)。搜索过程中访问了过多的无用状态,这些状态对最后184的结果无帮助。765765以上三个问题中,a为致命问题,应该它可能导致程序死循环;b和c是非致命的,但若不处理好可能导致性能急剧下降。Q4:怎样避免重复访问一个状态?最直接的方法是记录每一个状态访问否,然后再衍生状态时不衍生那些已经访问的状态了。思想是,给每个状态标记一个fag,若该状态nag=true则不衍生,若为 false则衍生并修改nlag为true在某些算法措述里,称有两个链表,一个为活链表(待访问),一个为死链表(访问完)。每一次衍生状态时,先判断它是否已在两个链衣中,若存在,则不衍生;若不存在,将其放入活链衣对于被衍生的那个状态,放入死链表为了记永每一个状态是否被方问过,我们需要有足够的空间。八数码问题一共有9!,这个数字并不是很大,但迎面而来的另一个问题是我们如何快速访问这些状态,如果是单纯用链表的话,那么在规模相当大,查找的状态数目十分多的时候就不能快速找到状态,其复杂度为O(n,为了解决这个问题,本文将采用哈希函数的方法,使复杂度减为O(1)这里的哈希函数是用能对许多全排列问题适用的方法。取n!为基数,状态第n位的逆序值为哈希值第n位数。对于空格,取其(9-位置)再乘以8!。例如,137246858的哈希值等于:0*0!+0*1!+0*2!+2*3!+1*4!+1*5!+0*6!+3*7!+(9-8)*8!=55596<9!具体的原因可以去查查一些数学书,其中123456789的哈希值是0最小,876543210的哈希值是(9!-1)最大,而其他值都在0到(9!-1)中,且均唯一。Q5:如何使搜索只求得最佳的解?普通的搜索称为DFS(深度优先搜索)。除了DFS,还有BFS,从概念上讲,两者只是在扩展时的方向不同,DFS向深扩张,而BFS向广扩张。在八数码问题的解集树中,树的深度就表示了从初始态到目标态的步数,DFS味向深,所以很容易找出深度较大的解BFS可以保证解的深度最少,因为在未将同一深度的状态全部访问完前,BFS不会去访问更深的状态,因此比较适合八数码问题,至少能解决求最佳解的难题。例如左图进行的是BFS,起始状态衍生四个状态,然后依次访问这四个状态,将第1层全访问完后再访问第二层,直到找到END状态为盐其1但是BFS和DFS一样不能解决问题c,因为每个状态都需要扩张,所以广搜很容易使待搜状态的数目膨胀。最终影响效率。Q6:该如何减少因广搜所扩张的与目标状态及解无关的状态?前面所说的都是从 START状态向END状态搜索,那么,将END状态与 START状态倒一下,其实会有另一条搜索路径(Q8策略三讨论),但简单的父换END与 START并不能缩小状态膨胀的规模。我们可以将正向与反向的搜索结合起来,这就是双向广度搜索。双向广搜是指同时从 STARI和END两端搜,当某一端所要访问的一个状态是被另一端访问过的时侯,即找到解,搜索结束。它的好处是可以避免广搜后期状态的膨胀。可以用下面这张图形象的进行比较左图的解集数是双向广搜的树,通过两端的共同搜索,两端找到了共同的状态。右端的树是同个门题的BFS树,在搜索后期,规模不断扩大,旦然能找到了目标状态,但其访问了许多无用结点,浪费了空间和时间。采用双向广度搜索可以将空间和时间节省一半!Q7:决定一个快的检索策略?双向广搜能大大减少时间和空间,但在有的情况下我们并不需要空间的节省,比如在Q4中已经决定了我们需要使用的空间是9!,所以不需要节省。这样我们可以把重点放在时间的缩短上。启发式搜索是在路径搜索问题中很实用的搜索方式,通过设计一个好的启发式函数来计算状态的优先级,优先考虑优先级高的状态,可以提早搜索到达目标态的时间。A*是一种启发式搜索的,他的启发式函数fO=g'O+h(能够应用到八数码问题中来。从起始状态到当前状态的实际代价g*O的估计值,gO>=g*Oh'(-从当前状态到目标状态的实际代价h*O的估计值,hO<-h+O注意两个限制条件(1)h(<=h*((2)任意状态的fO值必须大于其父状态的rO值,即r"O单调递增其中,gO是搜索的深度,h'O则是一个仙计函数,用以信计当前态到目标态可能的步数。解八薮码问题时一般有两种估计函数。比较简单的是 diference( Status a, Status b),其返回值是a和b状态各位置上数字不同的次数。另一种比较经典的是曼哈顿距离 manhattan( Status a, Status b),其返回的是各个数字从a的位置到b的位置的距离(见例子)。例如状态137246852和状态123456789的 differenc是5(不含空格,图中红色)。而他的 manhattan距离是:1(7d一次)+1(2u一次)+2(41两次)+3(6两次u一次)+2(5u一次1一次)=9单个数字的 manhattan应该小于5,因为对角的距窝才4,若大于4则说明计算有误。1O|3123Q②④4568⑤780o无论是 difference还是 manhattan,估计为越小越接近END,所以优先级高。在计算 difference和 manhattan时,推荐都将空格忽略,因为在 difference中空格可有可无,对整体搜索影响不大考虑下面两个状态(左需要3步到达END态,右需要4步到达END态),不含空格时di-3是相同的,含空格时左边的比右边的大一,但是实际上左图只要3步就能到达END态,而右图需要4步,多计算了空格反而把优先级搞错了。而 manhattan中,如果把空格也算上,实际上只会降低搜索速度(经过实验证明),同样考虑下图,不计算空柊时两者的 manhattan是左3右4,比dif要好,因为左的优先级大于右了。而加上空格后, manhattan是左6右4,不但颠倒了优先级,其误差比dif加空格后还要大。12342548578676O本文后面的实现将使用 manhattan不计空格的方法。其实,每移动一步,不计空格,相当于移动一个数字。如果每次移动都是完美的,即把一个数宇归位,那么 START态到END态的距离就是manhattan反过来说, manhattan是 START到END态的至少走的步数。回到fO)=g'O)+h'(,其实广度搜索是h'(=0的一种启发式搜索的特例,而深度搜索是f'(=的一般搜索。h'O对于优化搜索速度有很重要的作用。Q8:能否进一步优化检索策略?答案是背定的Δ*搜索策晔的优劣就是看h'O的决定好坏。前面列举了两个h'O的函数,但光有这两个是不够的。经过实验分析,在f)中,g'(决定的是 START态到END态中求得的解距离最优解的距离。而h'O能影响搜索的速度。所以优化的第一条策略是,放大h'O,比如,让h'O=10* manhattan,那么f"O=g()-10* manhattan(),可能提高搜索速度。可惜的是所得的解将不再会是最优的了。为什么放人hO能加快搜索速度,我们可以想象一下,h(描述的是本状态到END态的估计距离,估计距离越短自然快ˉ点到达END态。而g()摧述的是目前的深度,放大h'()的目的是尽量忽略深度的因素,是一种带策略的深搜,自然速度会比广搜和深搜都快,而因为减少考虑了深度因素,所以离最优解就越来越远了。关于hO放大多少,是很有趣的问题,有兴趣可以做些实验试试。第二条是更新待检查的状态,于A*搜索会需要一个待检查的序列。首先,在Q4已经提到用哈希避免重复访问同状态。而在待检査队列中的状态是木完成扩张的状态,如果山现了状态相同但其g'O比原gO出色的情况,那么我们更希槊的是搜索新状态,而不是原状态。这样,在待检查队列中出现重复状态时,只需更新其g(就可以了第三条是注意实现程序的方法,在起初我用sort排序fO后雨找出杈佰最大的状态,而后发现用make heap要更快。想一想,由于需要访问的接点较多,待访问队列一大那么自然反复排序对速度会有影响,而堆撅作则比排序更好。另一点是,实现更新待检杏队列时的搜索也要用比较好的方法实现。我在JAVA的演示程序中用的 PriorityQueue,可是结果不是很令人满意第四条优化策略是使用IDA*的算法,这是A*算法的一种,ID名为 Iterative deepening是迭代加深的意思。思想是如下:顺便准备一个记录一次循环最小值的temp=MAX,h取 manhattan距离①先估算从 START态到END态的hO记录为MN,将 START放入待访问队列②读取队列下一个状态,到队列尾则GOIO⑦③若gO> MIN GOTO④若g(+h(>MN是否为真,真GOO⑥,否GOIO⑤⑤扩展该状态,并标记此状态已访问。找到END态的话就结束该算法。GOTO②⑥temp=min( manhattan,temp),GOTO③若无扩展过状态,MIN-temp(ID的意思在这里体现)从头开始循环GO1O②第五条优化策略本身与搜索无关,在做题时也没能帮上忙,不过从理论上讲是有参考价值的。记得Q6中介绍的从END开始搜起吗?如果我们的任务是对多个 START与END进行搜索,那么我可以在每搜索完一次后记录下路径,这个路径很重要,因为在以后的搜索中如果存在 START和END的路径已经被记录过了,那么可以直接调出结果。从END搜起,可以方便判断下一次的 START是合已经有路径到END了。当前一次搜索完时其已访问状态是可以直接使用的,若 START不在其中,则从待访问的状态链表中按搜索策略找下个状态,等于接着上一次的搜索结果开始找之所以没能在速度上帮上忙,是因为这个优化策略需要加大g'O的比重,否则很容易出现深度相当大的情况,由于前一次搜索的策略与下一次的基本无关,导致前一次的路径无法预料,所以就会出现深度过大的情况。解决方法是加大gO策略五类似给程序加一个缓冲区,避免亘复计算。如果要做八数码的应用,缓冲区会帮上忙的Q10:怎样记录找到的路径?当找到解的时候我们就需要冇类似回退的工作来整理一条解路径,由」使用了不是简单的DFS,所以不能借助通过函数调用所是使用的程序栈。我们可以手L加个模拟栈。在Q4中解决了哈希的问题,利用哈希衣就能快速访问状态对应的值,在这里,我们把原来的bool值改为char或其他能表示一次操作(至少需要5种状态,除了urld外还要能表示状态已访问)的值就行了。在搜索到解时,记录下最后·个访问的状态值,然后从读取该状态对应的操作开始,就像栈操作的退栈一样,不停往回搜,直到找到搜索起点为止。记录好栈退出来的操作值,就是一条路径。三、算法设计基本设计(个简单的类图如下)Eightstatust balue inthash nullstar: int+wil. intman intMAsK: n[=1.10. 109, 1000, 10000.1DD0DDD, 10000909, 1009000001DDDDDoDoDmannitan: Intquu: Yector=动似compare Tora: status); inthasht pde(status int: Intt OrcersTatus..,ko le anpane(status: in, curLee: inD: intmwe(status inil, o persion. thar: inEvalidincitBtatus: int nexdLE'el: int, operation: chan-vaidACM解题测试Status表示可以不压缩(即直接用char表示,因为看下来几个网站对内存要求都不高)。哈希读取可以直接用map(C++), HashMap(ava),速度不会慢的。在每次取优先级最大的状态时,建议用C→+的 make heap检索略及效果见下:PKU1077题:数据不强,用一点点技巧就能过JAVADHS,BHS超时双向广搜406Ms,4904K以 distance为h'O搜索718MS,3056KC++:双向广搜46MS,1252Kf'O= manhattan搜索0-15MS,276K左右以 manhattan为.h'O)搜索265MS,376K以 manhattan为h'O,更新待检查队列15Ms,276KIDA108MS,888K杭州申子科技大学1043题:数据强了点f'O= manhattan搜索203lms,676KrO=gO+ manhattan搜索403lms,708KfO=g+5* manhattan搜索3766ms,708KfO=g(+10 manhattan搜索2515ms,708KfO=g+15* manhattan搜索4297ms,704KfO=gO+20* manhattan搜索4328ms,704KZJ1217颗;对时间好苛刻,在这里 make-heapo能过 sorto就不能--0只有纯以 manhattan为f")搜索AC了00:05.07,900K以 manhattan为h'O,更新待检查队列00:06.11,904K惊讶an是如何以00:00.11,396K过的(还有"绿野凤烟")。A652颗;看来功丿不够啊-没有通过应用设计首先,拒绝在ACM试题中衣现出色的fO- manhattan搜索,因为其搜索所得的结果太长了(搜索深度过大),得不到最优解就宁可选择慢一点点的。在我写的小八数码软件里,我用了普通广搜、双向搜和A*(fO=g()+h'()三个搜索作比较。其中普通搜索的速度很慢,而且消耙內存较多。以卜用三个搜索对面 -a Grid口区Game Anane Hep74512456782136进行搜索,情况如回区Statistic Tree Solitonsart sterlin7452138D6End status121456780BreastheiegtsearchHear?证ad|EB:Time used [ns:2125ouble ThReshold BFs14mMemoEy ued Bl. 3P7Tame tBed CneA-Sta工 SearchTRaveled pades 512Time tased [ne?AIyar itriea山 hhis SaiC口rsy Analyse□回区SHEslie ee SaiEnTaille Hastur DFsAluunithn:真 Slai search让我们来分析一下几个结果出现的原因。首先,普通广搜访问了7万多节点,节点的膨胀之大让人无法承受,所以除非拿广搜来做比较,否则不要拿它来做应用。然后,广搜的规模比普通搜索少了近70倍。在许多次测试后都显小,广搜的搜索节点数不多,速度也很快,最重要的是它所求的一定是最优解。因此,比较适合拿来做应用。A*表现也不错,由于是带有一种好的倾向,所以他搜索的节点十分少,也因为这样他的表现也比较好。仔细的读者一定发现了,在数据统计中双向广搜和A*的时间上相差无几。其原因我分析是在用A*搜索时的状态优先级的顺序是用 Priority Queue(优先队列,插入复杂度O(lgn,移除和査找复杂度O(m),出队列复杂度O(1))来实现,加上史新待检査队列没办法很简单的实现,所以在这些细节上还是有所消耗。最后,A*的解不是最优(最短的),但还是可以接受的。对于Q8中的第五条,我在BFS和A*中实现了,双端广搜因为结构上的因素没能实现。四、程序实现:(JAVA)提供几个在ACM解题中双端广搜用到的基本函数,关于应用的八数码,我放在CSDN里了有兴趣可以下载(带源码)static class Operation∥为了记录每步操作写的类char laptop∥操作boolean flag∥从上端开始还是下端开始Operation(char o, boolean u)ilastop-o,static Hash Map hsstatic final int END=123456789static int move( char dir, int num)&∥栘动操作,将num按dir操作int next-0, temp=num %010, target-0, tI∥ud操作比较复杂target=(int)pow(10, (9-temp+ 1)next=num/largett1= next 1000next=next-t1+(t1 %100)*10+t1/100nexL i- larget;nextirectbreakcasenext =nu+Icase 'dtarget =(int) pow(10, (9-temp-2))next =num/target:tl= next %1000next=next-tI+(tI %10)*100+t1/10next " target:%o target+ 3;ease 'next =num-1breaketurn next:∥约東函数,把只将未检查的状态加入待檢查队列中static void valid(int t, char op, Array List queue, boolean flag)iOperation temp,if((temp=hs. get(t))hs put(t, new Operation(op, flagqueue. add(t)felse if(temp. flag flag &i& tempo==0)if(flag)itcmpop-=opselsettempo=temp laptopemp laptop=op;nuequeue. add (t)