資源描述：
《淺析a-算法求解最短路徑》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、淺析A*算法求解最短路徑近來(lái)不少的朋友問(wèn)我有關(guān)A*算法的新題目,目的是寫一個(gè)搜索最短路徑的程序.這個(gè)在鼠標(biāo)控制精靈運(yùn)動(dòng)的游戲中(不算智冠出的那些用鼠標(biāo)充當(dāng)鍵盤方向鍵的弱智RPG)大量使用,尤其是即時(shí)戰(zhàn)略類的.但是我個(gè)人以為A*算法只適合處理靜態(tài)路徑求解,對(duì)即時(shí)戰(zhàn)略游戲中大量對(duì)象堵塞過(guò)道時(shí),疏通交通很難實(shí)現(xiàn)(也不是不能實(shí)現(xiàn),這需要一個(gè)相當(dāng)好的估價(jià)函數(shù),且不能一次搜索路徑) 我希奇的是,A*算法應(yīng)該是算法課的基礎(chǔ)知識(shí)了,任何一個(gè)系統(tǒng)學(xué)習(xí)過(guò)算法的人都應(yīng)該了解,本不應(yīng)該我在這里亂寫一通,大家隨意翻本將計(jì)算機(jī)算法是純正的A*算法;-)*你可以在理解了這段程序的基礎(chǔ)上,按
2、自己的理解寫出類似的代碼.但是簡(jiǎn)單的*復(fù)制它到你的程序中是不答應(yīng)的,假如你真要這樣干,請(qǐng)?jiān)谥苯邮褂盟能浖?文檔中,寫上我的名字;-)*有任何的新題目,或建議請(qǐng)E-mail到[email protected]*歡迎參觀我的主頁(yè)~cloudap.dat,保存有輿圖的數(shù)據(jù)*///#defineNDEBUG#include#include#include#include#defineMAPMAXSIZE100//輿圖面積最大為100x100#defineMAXINT8192//定義一個(gè)最大整數(shù),輿圖上任意兩點(diǎn)間隔不會(huì)超過(guò)它#defineSTACKSIZE6
3、5536//保存搜索節(jié)點(diǎn)的堆棧大小#defiile_num(x,y)((y)*map_ap_ap_ap[MAPMAXSIZE][MAPMAXSIZE];//輿圖數(shù)據(jù)intdis_map[MAPMAXSIZE][MAPMAXSIZE];//保存搜索路徑時(shí),中間目標(biāo)地最優(yōu)解intmap_ap_h;//輿圖寬和高intstart_x,start_y,end_x,end_y;//地點(diǎn),終點(diǎn)坐標(biāo)//初始化隊(duì)列voidinit_queue(){queue=(LINK)malloc(sizeof(*queue));queue->node=NULL;queue->f=-1;qu
4、eue->next=(LINK)malloc(sizeof(*queue));queue->next->f=MAXINT;queue->next->node=NULL;queue->next->next=NULL;}//待處理節(jié)點(diǎn)進(jìn)隊(duì)列,依靠對(duì)目的地估價(jià)間隔插進(jìn)排序voidenter_queue(TREEnode,intf){LINKp=queue,father,q;alloc(sizeof(*q));assert(queue);q->f=f,q->node=node,q->next=p;father->next=q;}//將離目的地估計(jì)最近的方案出隊(duì)列TREE
5、get_from_queue(){TREEbestchoice=queue->next->node;LINKnext=queue->next->next;free(queue->next);queue->next=next;stack[stacktop]=bestchoice;assert(stacktop//開(kāi)釋棧頂節(jié)點(diǎn)voidpop_stack(){free(stack[--stacktop]);}//開(kāi)釋申請(qǐng)過(guò)的所有節(jié)點(diǎn)voidfreetree(){inti;LINKp;for(i=0;itile)&&y==tile_y(p->tile))return1;
6、//假如(x,y)曾經(jīng)經(jīng)過(guò),失敗p=p->father;}h=father->h1;if(h>=dis_map[y][x])return1;//假如曾經(jīng)有更好的方案移動(dòng)到(x,y)失敗dis_map[y][x]=h;//記錄這次到(x,y)的間隔為歷史最佳間隔//將這步方案記進(jìn)待處理隊(duì)列p=(TREE)malloc(sizeof(*p));p->father=father;p->h=father->h1;p->tile=tile_num(x,y);enter_queue(p,p->hjudge(x,y));return0;}//路徑尋找主函數(shù)voidfindpa
7、th(int*path){TREEroot;inti,j;stacktop=0;for(i=0;itile=tile_num(start_x,start_y);root->h=0;root->father=NULL;enter_queue(root,judge(start_x,start_y));for(;;){intx,y,child;TREEp;root=get_from_queue();if(root==NULL){*path=-1;return;}x=tile_x(root->tile);y=tile_y(root->tile);if(x==end_x&
8、&y==end_y)br
