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