啟發(fā)式搜索A星算法

啟發(fā)式搜索—初識(shí)A*算法A*在游戲中有它很典型的用法，是人工智能在游戲中的代表。A*算法在人工智能中是一種典型的啟發(fā)式搜索算法，為了說(shuō)清楚A*算法，先說(shuō)說(shuō)何謂啟發(fā)式算法。一、何謂啟發(fā)式搜索算法在說(shuō)它之前先提提狀態(tài)空間搜索。狀態(tài)空間搜索，如果按專業(yè)點(diǎn)的說(shuō)法，就是將問(wèn)題求解過(guò)程表現(xiàn)為從初始狀態(tài)到目標(biāo)狀態(tài)尋找這個(gè)路徑的過(guò)程。通俗點(diǎn)說(shuō)，就是在解一個(gè)問(wèn)題時(shí)，找到一個(gè)解題的過(guò)程，應(yīng)用這個(gè)過(guò)程可以從求解的開(kāi)始得到問(wèn)題的結(jié)果。由于求解問(wèn)題的過(guò)程中分支有很多，主要是求解過(guò)程中求解條件的不確定性、不完備性造成的，使得求解的路徑很多，這樣就構(gòu)成了一個(gè)圖，我們說(shuō)這個(gè)圖就是狀態(tài)空間。問(wèn)題的求解實(shí)際上就是在這個(gè)圖中找到一條路徑可以從開(kāi)始到結(jié)果。這個(gè)尋找的過(guò)程就是狀態(tài)空間搜索。常用的狀態(tài)空間搜索有深度優(yōu)先和廣度優(yōu)先。廣度優(yōu)先是從初始狀態(tài)一層一層向下找，直到找到目標(biāo)為止。深度優(yōu)先是按照一定的順序，先查找完一個(gè)分支，再查找另一個(gè)分支，直至找到目標(biāo)為止。這兩種算法在數(shù)據(jù)結(jié)構(gòu)書(shū)中都有描述，可以參看這些書(shū)得到更詳細(xì)的解釋。前面說(shuō)的廣度和深度優(yōu)先搜索有一個(gè)很大的缺陷就是：他們都是在一個(gè)給定的狀態(tài)空間中窮舉。這在狀態(tài)空間不大的情況下是很合適的算法，可是當(dāng)狀態(tài)空間十分大，且不可預(yù)測(cè)的情況下就不可取了。他們的效率實(shí)在太低，甚至不可完成。在這里就要用到啟發(fā)式搜索了。啟發(fā)式搜索就是在狀態(tài)空間中搜索時(shí)，對(duì)每一個(gè)搜索的位置進(jìn)行評(píng)估，得到最好的位置，再?gòu)倪@個(gè)位置進(jìn)行搜索直至找到目標(biāo)。這樣可以省略大量無(wú)謂的搜索路徑，提高了效率。在啟發(fā)式搜索中，對(duì)位置的估價(jià)是十分重要的。采用了不同的估價(jià)可以有不同的效果。我們先看看估價(jià)是如何表示的。啟發(fā)中的估價(jià)是用估價(jià)函數(shù)表示的，如：f(n)=g(n)+h(n)其中f(n)是節(jié)點(diǎn)n的估價(jià)函數(shù)，g(n)是在狀態(tài)空間中從初始節(jié)點(diǎn)到n節(jié)點(diǎn)的實(shí)際代價(jià)，h(n)是從n節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)代價(jià)。在這里主要是h(n)體現(xiàn)了搜索的啟發(fā)信息，因?yàn)間(n)是已知的。二、初識(shí)A*算法啟發(fā)式搜索其實(shí)有很多的算法，比如：局部擇優(yōu)搜索法(如爬山法)、最好優(yōu)先搜索法(Best-first)等等，當(dāng)然A*也是。這些算法都使用了啟發(fā)函數(shù)，但在具體選取最佳搜索節(jié)點(diǎn)時(shí)，使用的策略不同。比如局部擇優(yōu)搜索法，就是在搜索的過(guò)程中選取“最佳節(jié)點(diǎn)”后舍棄其他的兄弟節(jié)點(diǎn)、父節(jié)點(diǎn)，而一直搜索下去。這種搜索的結(jié)果很明顯，由于舍棄了其他的節(jié)點(diǎn)，可能也把最好的節(jié)點(diǎn)都舍棄了，因?yàn)榍蠼獾淖罴压?jié)點(diǎn)只是在該階段的最佳(局部的)，并不一定是全局的最佳。最好優(yōu)先(Best-first)就聰明多了，他在搜索時(shí)，便沒(méi)有舍棄節(jié)點(diǎn)(除非該節(jié)點(diǎn)是死節(jié)點(diǎn))，在每一步的估價(jià)中，把當(dāng)前節(jié)點(diǎn)和以前節(jié)點(diǎn)的估價(jià)值作比較，得到一個(gè)“最佳的節(jié)點(diǎn)”。這樣可以有效的防止“最佳節(jié)點(diǎn)”的丟失。那么A*算法又是一種什么樣的算法呢？其實(shí)A*算法也是一種最好優(yōu)先(Best-first)的算法。只不過(guò)要加上一些約束條件罷了。由于在一些問(wèn)題求解時(shí)，我們希望能夠求解出狀態(tài)空間搜索的最短路徑，也就是用最快的方法求解問(wèn)題，A*就是干這種事情的！我們先下個(gè)定義，如果一個(gè)估價(jià)函數(shù)可以找出最短的路徑，我們稱之為可采納性。A*算法是一個(gè)可采納的最好優(yōu)先算法。A*算法的估價(jià)函數(shù)可表示為：f'(n)=g'(n)+h'(n)這里，f'(n)是估價(jià)函數(shù)，g'(n)是起點(diǎn)到當(dāng)前節(jié)點(diǎn)的最短路徑值，h'(n)是口到目標(biāo)的最短路經(jīng)的啟發(fā)值。g'(n)的值實(shí)際上很容易從到目前為止的搜索樹(shù)上計(jì)算出來(lái)，不必專門(mén)定義計(jì)算公式，也就是根據(jù)搜索歷史情況對(duì)g'(n)作出計(jì)算，顯然g(n)>=g'(n)°h'(n)則依賴于啟發(fā)信息，通常稱為啟發(fā)函數(shù)，是要對(duì)未來(lái)擴(kuò)展的方向作出估計(jì)。A*算法是按f'(n)遞增的順序來(lái)排列可能被擴(kuò)展的節(jié)點(diǎn)，因而優(yōu)先擴(kuò)展f'(n)值最小的節(jié)點(diǎn)，體現(xiàn)了最好優(yōu)先(Best-first)的搜索思想。但有一點(diǎn)：h(n)<=h'(n)才可(這一點(diǎn)特別的重要)?？梢宰C明應(yīng)用這樣的估價(jià)函數(shù)是可以找到最短路徑的，也就是可采納的。我們說(shuō)應(yīng)用這種估價(jià)函數(shù)的最好優(yōu)先算法就是A*算法。舉一個(gè)例子，其實(shí)廣度優(yōu)先算法就是A*算法的特例。其中g(shù)(n)是節(jié)點(diǎn)所在的層數(shù)，h(n)=0，這種h(n)肯定小于h'(n)，所以由前述可知廣度優(yōu)先算法是一種可采納的算法。實(shí)際也是。當(dāng)然它是一種最臭的A*算法。再說(shuō)一個(gè)問(wèn)題，就是有關(guān)h(n)啟發(fā)函數(shù)的信息性。h(n)的信息性通俗點(diǎn)說(shuō)其實(shí)就是在估計(jì)一個(gè)節(jié)點(diǎn)的值時(shí)的約束條件，如果信息越多或約束條件越多則排除的節(jié)點(diǎn)就越多，估價(jià)函數(shù)越好或說(shuō)這個(gè)算法越好。這就是為什么廣度優(yōu)先算法的那么臭的原因了，誰(shuí)叫它的h(n)二0，一點(diǎn)啟發(fā)信息都沒(méi)有。但h(n)的信息越多，它的計(jì)算量就越大，耗費(fèi)的時(shí)間就越多。就應(yīng)該適當(dāng)?shù)臏p小h(n)的信息，即減小約束條件。但算法的準(zhǔn)確性就差了，這里就有一個(gè)平衡的問(wèn)題。這是一個(gè)矛盾體，就看你怎樣去掌握這個(gè)平衡了！下面舉個(gè)例子說(shuō)明h(n)的不同設(shè)計(jì)方法：將某一格局與目標(biāo)格局比較，得到位置不符的數(shù)目;缺點(diǎn)：沒(méi)有考慮數(shù)字移動(dòng)的距離。2）計(jì)算將數(shù)字移動(dòng)到目的位置所需移動(dòng)的距離之和；缺點(diǎn)：沒(méi)有考慮牌排列的先后順序，即若兩個(gè)數(shù)字相鄰，但與目的位置相比是相反的，則它們至少需要移動(dòng)3次。深入人*算法在這里我將對(duì)A*算法的實(shí)際應(yīng)用進(jìn)行一定的探討，并且舉一個(gè)有關(guān)A*算法在最短路徑搜索的例子。1、A*算法的程序編寫(xiě)原理在“初識(shí)A*算法”中說(shuō)過(guò)，A*算法是最好優(yōu)先算法的一種。只是有一些約束條件而已。我們先來(lái)看看最好優(yōu)先算法是如何編寫(xiě)的吧。如圖有如下的狀態(tài)空間：（起始位置是A，目標(biāo)位置是P，字母后的數(shù)字表示節(jié)點(diǎn)的估價(jià)值）。TCLOSED=[];TCLOSED=[];并放入OPEN表中；CLOSED=[A5]

并放入OPEN表中；CLOSED=[B4,A5]并放入OPEN表中；搜索過(guò)程中設(shè)置兩個(gè)表：OPEN和CLOSED。OPEN表保存了所有已生成而未考察的節(jié)點(diǎn)，CLOSED表中記錄已訪問(wèn)過(guò)的節(jié)點(diǎn)。算法中有一步是根據(jù)估價(jià)函數(shù)重排OPEN表的節(jié)點(diǎn)。K這樣循環(huán)中的每一步只考慮|OPEN表中狀態(tài)最好的節(jié)點(diǎn)。具S體搜索過(guò)程如下：1）始狀態(tài)：OPEN=[A5];2）估算A5，取得所有子節(jié)點(diǎn)，OPEN=[B4,C4,D6];3）估算B4,取得所有子節(jié)點(diǎn)，OPEN=[C4,E5,F5,D6];4）估算C4；取得所有子節(jié)點(diǎn)，OPEN=[H3,G4,E5,F5,D6];CLOSED=[C4,B4,A5]5）估算H3，取得所有子節(jié)點(diǎn)，并放入OPEN表中；OPEN=[O2,P3,G4,E5,F5,D6];CLOSED=[H3,C4,B4,A5]6）估算O2，取得所有子節(jié)點(diǎn)，并放入OPEN表中；OPEN=[P3,G4,E5,F5,D6];CLOSED=[O2,H3,C4,B4,A5]7）估算P3，已得到解。算法結(jié)束看了具體的過(guò)程，再看看偽程序吧。算法的偽程序如下:Best_First_Search（）{Open=[起始節(jié)點(diǎn)];Closed=[];while（Open表非空）{從Open中取得一個(gè)節(jié)點(diǎn)X,并從OPEN表中刪除.if（X是目標(biāo)節(jié)點(diǎn)）{求得路徑PATH;返回路徑PATH;}for（每一個(gè)X的子節(jié)點(diǎn)Y）{if（Y不在OPEN表和CLOSED表中）{求Y的估價(jià)值；并將Y插入OPEN表中；//還沒(méi)有排序}elseif（Y在OPEN表中）{if（Y的估價(jià)值小于OPEN表的估價(jià)值）更新OPEN表中的估價(jià)值；}else//Y在CLOSED表中{if（Y的估價(jià)值小于CLOSED表的估價(jià)值）{更新CLOSED表中的估價(jià)值；從CLOSED表中移出節(jié)點(diǎn)，并放入OPEN表中;}}將X節(jié)點(diǎn)插入CLOSED表中；按照估價(jià)值將OPEN表中的節(jié)點(diǎn)排序；}//endfor}//endwhile}//endfunc偽程序出來(lái)了，寫(xiě)一個(gè)源程序應(yīng)該不是問(wèn)題了，依葫蘆畫(huà)瓢就可以。A*算法的程序與此是一樣的，只要注意估價(jià)函數(shù)中的g(n)的h(n)約束條件就可以了。下面，我們可以進(jìn)入另一個(gè)重要的話題，用A*算法實(shí)現(xiàn)最短路徑的搜索。在此之前你最好認(rèn)真的理解前面的算法。2、用A*算法實(shí)現(xiàn)最短路徑的搜索在實(shí)際應(yīng)用中中，經(jīng)常要涉及到最短路徑的搜索，現(xiàn)在一個(gè)比較好的方法就是用A*算法進(jìn)行設(shè)計(jì)。先復(fù)習(xí)一下，A*算法的核心是估價(jià)函數(shù)f(n)，它包括g(n)和h(n)兩部分°g(n)是已經(jīng)走過(guò)的代價(jià)，h(n)是n到目標(biāo)的估計(jì)代價(jià)。在這個(gè)例子中g(shù)(n)表示在狀態(tài)空間從起始節(jié)點(diǎn)到n節(jié)點(diǎn)的深度，h(n)表示n節(jié)點(diǎn)所在地圖的位置到目標(biāo)位置的直線距離。一個(gè)是狀態(tài)空間，一個(gè)是實(shí)際的地圖，不要搞錯(cuò)了。再詳細(xì)點(diǎn)說(shuō)，有一個(gè)物佩，在地圖上的坐標(biāo)是(xa,ya)，A所要到達(dá)的目標(biāo)b的坐標(biāo)是(xb,yb)。則開(kāi)始搜索時(shí)，設(shè)置一個(gè)起始節(jié)點(diǎn)1，生成八個(gè)子節(jié)點(diǎn)2-9因?yàn)橛邪藗€(gè)方向。如圖：先看搜索主函數(shù)：voidAstarPathfinder::FindPath(intsx,intsy,intdx,intdy){NODE*Node,*BestNode;intTileNumDest;〃得到目標(biāo)位置，作判斷用TileNumDest=TileNum(sx,sy);//生成Open和Closed表OPEN=(NODE*)calloc(1,sizeof(NODE));CLOSED=(NODE*)calloc(1,sizeof(NODE));//生成起始節(jié)點(diǎn)，并放入Open表中Node=(NODE*)calloc(1,sizeof(NODE));Node->g=0;〃這是計(jì)算h值Node->h=(dx-sx)*(dx-sx)+(dy-sy)*(dy-sy);//shouldreallyusesqrt().〃這是計(jì)算f值，即估價(jià)值Node->f=Node->g+Node->h;Node->NodeNum=TileNum(dx,dy);Node->x=dx;Node->y=dy;OPEN->NextNode=Node;//makeOpenListpointtofirstnodefor(;;){〃從Open表中取得一個(gè)估價(jià)值最好的節(jié)點(diǎn)BestNode=ReturnBestNode();〃如果該節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)就退出if(BestNode->NodeNum==TileNumDest)//ifwe'vefoundtheend,breakandfinishbreak;〃否則生成子節(jié)點(diǎn)GenerateSuccessors(BestNode,sx,sy);}PATH=BestNode;}再看看生成子節(jié)點(diǎn)函數(shù)GenerateSuccessors：voidAstarPathfinder::GenerateSuccessors(NODE*BestNode,intdx,intdy){intx,y;//依次生成八個(gè)方向的子節(jié)點(diǎn)//Upper-Leftif(FreeTile(x=BestNode->x-TILESIZE,y=BestNode->y-TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);//Upperif(FreeTile(x=BestNode->x,y=BestNode->y-TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);//Upper-Rightif(FreeTile(x=BestNode->x+TILESIZE,y=BestNode->y-TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);//Rightif(FreeTile(x=BestNode->x+TILESIZE,y=BestNode->y))GenerateSucc(BestNode,x,y,dx,dy);//Lower-Rightif(FreeTile(x=BestNode->x+TILESIZE,y=BestNode->y+TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);//Lowerif(FreeTile(x=BestNode->x,y=BestNode->y+TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);//Lower-Leftif(FreeTile(x=BestNode->x-TILESIZE,y=BestNode->y+TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);//Leftif(FreeTile(x=BestNode->x-TILESIZE,y=BestNode->y))GenerateSucc(BestNode,x,y,dx,dy);}看看最重要的函數(shù)GenerateSucc：voidAstarPathfinder::GenerateSucc(NODE*BestNode,intx,inty,intdx,intdy){intg,TileNumS,c=0;NODE*Old,*Successor;//計(jì)算子節(jié)點(diǎn)的g值g=BestNode->g+1;//g(Successor)=g(BestNode)+costofgettingfromBestNodetoSuccessorTileNumS=TileNum(x,y);//identificationpurposes〃子節(jié)點(diǎn)再Open表中嗎？if((Old=CheckOPEN(TileNumS))!=NULL)//ifequaltoNULLthennotinOPENlist,//elseitreturnstheNodeinOld{〃若在for(c=0;c<8;c++)if(BestNode->Child[c]==NULL)//AddOldtothelistofBestNode'sChildren//(orSuccessors).break;BestNode->Child[c]=Old;//比較Open表中的估價(jià)值和當(dāng)前的估價(jià)值(只要比較g值就可以了)if(gg)//ifournewgvalueisParent=BestNode;Old->g=g;Old->f=g+Old->h;}}else〃在Closed表中嗎？if((Old=CheckCLOSED(TileNumS))!=NULL)//ifequaltoNULLthennotinOPENlist//elseitreturnstheNodeinOld{//若在for(c=0;c<8;c++)if(BestNode->Child[c]==NULL)//AddOldtothelistofBestNode's//Children(orSuccessors).break;BestNode->Child[c]=Old;〃比較Closed表中的估價(jià)值和當(dāng)前的估價(jià)值(只要比較g值就可以了)if(gg)//ifournewgvalueisParent=BestNode;Old->g=g;Old->f=g+Old->h;〃再依次更新Old的所有子節(jié)點(diǎn)的估價(jià)值PropagateDown(Old);//SincewechangedthegvalueofOld,weneed//topropagatethisnewvaluedownwards,i.e.//doaDepth-Firsttraversalofthetree!}}else〃不在Open表中也不在Close表中{//生成新的節(jié)點(diǎn)Successor=(NODE*)calloc(1,sizeof(NODE));Successor->Parent=BestNode;Successor->g=g;Successor->h=(x-dx)*(x-dx)+(y-dy)*(y-dy);//shoulddosqrt(),butsincewe//don'treallySuccessor->f=g+Successor->h;//careaboutthedistancebutjustwhichbranchlooksSuccessor->x=x;//betterthisshouldsuffice.Anyayzit'sfaster.Successor->y=y;Successor->NodeNum=TileNumS;〃再插入Open表中，同時(shí)排序。Insert(Successor);//InsertSuccessoronOPENlistwrtffor(c=0;c<8;c++)if(BestNode->Child[c]==NULL)//AddOldtothelistofBestNode's//Children(orSuccessors).break;BestNode->Child[c]=Successor;}}仔細(xì)看看這個(gè)程序，你會(huì)發(fā)現(xiàn)，這個(gè)程序和前面說(shuō)的偽程序有一些不同，在GenerateSucc函數(shù)中，當(dāng)子節(jié)點(diǎn)在Closed表中時(shí)，沒(méi)有將子節(jié)點(diǎn)從Closed表中刪除并放入Open表中。而是直接的重新的計(jì)算該節(jié)點(diǎn)的所有子節(jié)點(diǎn)的估價(jià)值（用PropagateDown函數(shù)）。這樣可以快一些。/""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""http://**************************************************************************//*****************************a*Algorithm*******************************/""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""/**************************************************************************structNODE*FindPath(longsx,longsy,longdx,longdy){structNODE*Node,*BestNode;intTileNumDest;TileNumDest=TileNum((int)dx,(int)dy);OPEN=(structNODE*)calloc(1,sizeof(structNODE));CLOSED=(structNODE*)calloc(1,sizeof(structNODE));Node=(structNODE*)calloc(1,sizeof(structNODE));Node->g=0;Node->h=(sx-dx)*(sx-dx)+(sy-dy)*(sy-dy);//shouldreallyusesqrt().Node->f=Node->g+Node->h;Node->NodeNum=TileNum((int)sx,(int)sy);Node->x=sx;Node->y=sy;OPEN->NextNode=Node;/*makeOpenListpointtofirstnode*/for(;;){BestNode=(structNODE*)ReturnBestNode();if(BestNode->NodeNum==TileNumDest)/*ifwe'vefoundtheend,breakandfinish*/break;GenerateSuccessors(BestNode,dx,dy);}return(BestNode);}structNODE*ReturnBestNode(void){structNODE*tmp;if(OPEN->NextNode==NULL){printf("ERROR:nomorenodesonOPEN\n");RestoreKeyboard();//restoreBIOSkeyboardhandlingclosegraph();exit(0);}/*PickNodewithlowestf,inthiscaseit'sthefirstnodeinlistbecausewesorttheOPENlistwrtlowestf.CallitBESTNODE.*/tmp=OPEN->NextNode;//pointtofirstnodeonOPENOPEN->NextNode=tmp->NextNode;//MakeOPENpointtonextnodeorNULL./*NexttakeBESTNODE(ortempinthiscase)andputitonCLOSED*/tmp->NextNode=CLOSED->NextNode;CLOSED->NextNode=tmp;return(tmp);}voidGenerateSuccessors(structNODE*BestNode,longdx,longdy){/*Upper-Left*/if(FreeTile(x=(long)BestNode->x-TILESIZE,y=(long)BestNode->y-TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);/*Upper*/if(FreeTile(x=(long)BestNode->x,y=(long)BestNode->y-TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);/*Upper-Right*/if(FreeTile(x=(long)BestNode->x+TILESIZE,y=(long)BestNode->y-TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);/*Right*/if(FreeTile(x=(long)BestNode->x+TILESIZE,y=(long)BestNode->y))GenerateSucc(BestNode,x,y,dx,dy);/*Lower-Right*/if(FreeTile(x=(long)BestNode->x+TILESIZE,y=(long)BestNode->y+TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);/*Lower*/if(FreeTile(x=(long)BestNode->x,y=(long)BestNode->y+TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);/*Lower-Left*/if(FreeTile(x=(long)BestNode->x-TILESIZE,y=(long)BestNode->y+TILESIZE))GenerateSucc(BestNode,x,y,dx,dy);/*Left*/if(FreeTile(x=(long)BestNode->x-TILESIZE,y=(long)BestNode->y))GenerateSucc(BestNode,x,y,dx,dy);}voidGenerateSucc(structNODE*BestNode,longx,longy,longdx,longdy){intg,TileNumS,c=0;structNODE*Old,*Successor;g=BestNode->g+1;/*g(Successor)=g(BestNode)+costofgettingfromBestNodetoSuccessor*/TileNumS=TileNum((int)x,(int)y);/*identificationpurposes*/if((Old=CheckOPEN(TileNumS))!=NULL)/*ifequaltoNULLthennotinOPENlist,elseitreturnstheNodeinOld*/{for(c=0;c<8;c++)if(BestNode->Child[c]==NULL)/*AddOldtothelistofBestNode'sChildren(orSuccessors).*/break;BestNode->Child[c]=Old;if(g<Old->g)/*ifournewgvalueis<Old'sthenresetOld'sparenttopointtoBestNode*/{Old->Parent=BestNode;Old->g=g;Old->f=g+Old->h;}}elseif((Old=CheckCLOSED(TileNumS))!=NULL)/*ifequaltoNULLthennotinOPENlist,elseitreturnstheNodeinOld*/{for(c=0;c<8;c++)if(BestNode->Child[c]==NULL)/*AddOldtothelistofBestNode'sChildren(orSuccessors).*/break;BestNode->Child[c]=Old;if(g<Old->g)/*ifournewgvalueis<Old'sthenresetOld'sparenttopointtoBestNode*/{Old->Parent=BestNode;Old->g=g;Old->f=g+Old->h;PropagateDown(Old);/*SincewechangedthegvalueofOld,weneedtopropagatethisnewvaluedownwards,i.e.doaDepth-Firsttraversalofthetree!*/}}else{Successor=(structNODE*)calloc(1,sizeof(structNODE));Successor->Parent=BestNode;Successor->g=g;Successor->h=(x-dx)*(x-dx)+(y-dy)*(y-dy);//shoulddosqrt(),butsincewedon'treallySuccessor->f=g+Successor->h;//careaboutthedistancebutjustwhichbranchlooksSuccessor->x=x;//betterthisshouldsuffice.Anyayzit'sfaster.Successor->y=y;Successor->NodeNum=TileNumS;Insert(Successor);/*InsertSuccessoronOPENlistwrtf*/for(c=0;c<8;c++)if(BestNode->Child[c]==NULL)/*AddOldtothelistofBestNode'sChildren(orSuccessors).*/break;BestNode->Child[c]=Successor;}}structNODE*CheckOPEN(inttilenum){structNODE*tmp;tmp=OPEN->NextNode;while(tmp!=NULL){if(tmp->NodeNum==tilenum)return(tmp);elsetmp=tmp->NextNode;}return(NULL);}structNODE*CheckCLOSED(inttilenum){structNODE*tmp;tmp=CLOSED->NextNode;while(tmp!=NULL){if(tmp->NodeNum==tilenum)return(tmp);elsetmp=tmp->NextNode;}return(NULL);}voidInsert(structNODE*Successor){structNODE*tmp1,*tmp2;longf;if(OPEN->NextNode==NULL){OPEN->NextNode=Successor;return;}/*insertintoOPENsuccessorwrtf*/f=Successor->f;tmp1=OPEN;tmp2=OPEN->NextNode;while((tmp2!=NULL)&&(tmp2->f<f)){tmp1=tmp2;tmp2=tmp2->NextNode;}Successor->NextNode=tmp2;tmp1->NextNode=Successor;}voidPropagateDown(structNODE*Old){intc,g;structNO