A* 算法求解最短路徑2008年07月17日 星期四 下午 03:26這個問題太老土了，但是絕對經(jīng)典，我現(xiàn)在就在研究啟發(fā)式搜索算法，用A*算法來做這個題目比較好了，給你一個很詳細的介紹吧！ 

下面的是以前數(shù)據(jù)結(jié)構(gòu)與算法的版主starfish提供的，你好好看看吧。不錯的 


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)該我在這里亂寫一通, 大家隨意翻本將計算機算法的書, 就應(yīng)該看的 
到. (將 AI 的書了更是少不了) 不過既然許多朋友問起, 在各個討論組, BBS 等地方也 
屢次見人提到, 特花一下午時間完成本文和附帶的程序, 滿足我們廣大業(yè)余游戲制作愛 
好者的求知欲, 專業(yè)人士免看, 以免班門弄斧 ^_^ 不過如有錯誤一定指出喲. 
　　如果您的上網(wǎng)時間很寶貴,請下載我注釋過的源碼(3k)離線研究 
　　在介紹 A* 算法前,先提一下廣度優(yōu)先搜索,廣度優(yōu)先搜索就是每次將當(dāng)前狀態(tài)可能 
發(fā)展的策略逐層展開,比如一個地圖中,對象允許向四個方向移動, 那么,就將地點處,對 
象向上下左右各移動一步, 將四個狀態(tài)都保存在內(nèi)存中, 然后再從這四個出發(fā)點向各自 
的四個方向再移動一步... (當(dāng)然這里可以剔除不合理的移動方法,比如不準(zhǔn)向回移動) 
實際上, 整個搜索好似一個圓形向外展開,直到到達目的地,很明顯這樣求解一定能找到 
最優(yōu)解,但節(jié)點展開的數(shù)量是和距離成級數(shù)增加的, 真的用在游戲中, 玩家會抱怨內(nèi)存 
128M 也不夠用了 ^_^ 而且伴隨待處理節(jié)點數(shù)的增加, 處理速度也會迅速減慢... 可以 
說這個算法并不實用 
　　而 A* 算法實際是一種啟發(fā)式搜索, 所謂啟發(fā)式搜索,就是利用一個估價函數(shù)評估每 
次的的決策的價值, 決定先嘗試哪一種方案. 這樣可以極大的優(yōu)化普通的廣度優(yōu)先搜索 
. 一般來說, 從出發(fā)點(A)到目的地(B)的最短距離是固定的,我們可以寫一個函數(shù) judg 
e() 估計 A 到 B 的最短距離, 如果程序已經(jīng)嘗試著從出發(fā)點(A) 沿著某條路線移動到 
了 C 點, 那么我們認為這個方案的 A B 間的估計距離為 A 到 C 實際已經(jīng)行走了的距 
離 H 加上用 judge() 估計出的 C 到 B 的距離. 如此, 無論我們的程序搜索展開到哪 
一步, 都會算出一個評估值, 每一次決策后, 將評估值和等待處理的方案一起排序, 然 
后挑出待處理的各個方案中最有可能是最短路線的一部分的方案展開到下一步, 一直循 
環(huán)到對象移動到目的地, 或所有方案都嘗試過卻沒有找到一條通向目的地的路徑則結(jié)束 
. (通常在游戲里還要設(shè)置超時控制的代碼,當(dāng)內(nèi)存消耗過大或用時過久就退出搜索) 
　　完了? 沒有. 怎么寫這個算法中的估價函數(shù)非常的重要,如何保證一定能找到最短路 
徑呢? 充要條件是, 你的估價函數(shù)算出的兩點間的距離必須小于等于實際距離. 這個可 
以從數(shù)學(xué)上嚴格證明,有興趣可以自己去查閱相關(guān)資料. 如果你的估價函數(shù)不滿足這點, 
就只能叫做 A 算法, 并不能保證最后的結(jié)果是最優(yōu)的,但它可能速度非常的快. 而游戲 
中我們也不一定非要得到最優(yōu)解的. 但無疑, 滿足那個條件的 A* 算法中, 估計值越接 
近真實值的估價函數(shù)就做的越好, 下面給出的程序,我只使用了一個相當(dāng)簡單的估價函數(shù) 
: 求出兩點中,若無障礙物的情況下的最短路徑. 如果您想寫出快速的尋路算法, 請自己 
尋找好的估價函數(shù)吧,有時間的時候,我會對此另文敘述 ;-) 
/* 云風(fēng)的求解最短路徑代碼 (Cloud Wu's Pathfinding code) * 1999 年 1月 8 日 (1999, Jan 8) * 這段代碼沒有進行任何優(yōu)化(包括算法上的), 但不意味我不知道該怎樣優(yōu)化它， 

* 它是為教學(xué)目的而做,旨在用易于理解和簡潔的代碼描述出 A* 算法在求最段路 
* 徑中的運用. 由于很久沒有摸算法書, 本程序不能保證是純正的 A* 算法 ;-) 
* 你可以在理解了這段程序的基礎(chǔ)上,按自己的理解寫出類似的代碼. 但是簡單的 
* 復(fù)制它到你的程序中是不允許的,如果你真要這樣干,請在直接使用它的軟件的 
* 文檔中,寫上我的名字 ;-) 
* 有任何的問題,或建議請 E-mail 到 cloudwu@263.net 
* 歡迎參觀我的主頁 http://member.netease.com/~cloudwu(云風(fēng)工作室) 
* (你可以在上面找到一些有關(guān)這個問題的討論,和有關(guān)游戲設(shè)計的其它大量資料) 
* 
* 本程序附帶有一個數(shù)據(jù)文件 map.dat, 保存有地圖的數(shù)據(jù) 
*/ 
// #define NDEBUG 
#include <stdio.h> 
#include <conio.h> 
#include <assert.h> 
#include <stdlib.h> 
#define MAPMAXSIZE 100 //地圖面積最大為 100x100 
#define MAXINT 8192 //定義一個最大整數(shù), 地圖上任意兩點距離不會超過它 
#define STACKSIZE 65536 //保存搜索節(jié)點的堆棧大小 
#define tile_num(x,y) ((y)*map_w+(x)) //將 x,y 坐標(biāo)轉(zhuǎn)換為地圖上塊的編號 
#define tile_x(n) ((n)%map_w) //由塊編號得出 x,y 坐標(biāo) 
#define tile_y(n) ((n)/map_w) 
// 樹結(jié)構(gòu), 比較特殊, 是從葉節(jié)點向根節(jié)點反向鏈接 
typedef struct node *TREE; 
struct node { 
int h; 
int tile; 
TREE father; 
} ; 
typedef struct node2 *LINK; 
struct node2 { 
TREE node; 
int f; 
LINK next; 
}; 
LINK queue; // 保存沒有處理的行走方法的節(jié)點 
TREE stack[STACKSIZE]; // 保存已經(jīng)處理過的節(jié)點 (搜索完后釋放) 
int stacktop; 
unsigned char map[MAPMAXSIZE][MAPMAXSIZE]; //地圖數(shù)據(jù) 
int dis_map[MAPMAXSIZE][MAPMAXSIZE]; //保存搜索路徑時,中間目標(biāo)地最優(yōu) 
解 
int map_w,map_h; //地圖寬和高 
int start_x,start_y,end_x,end_y; //地點,終點坐標(biāo) 
// 初始化隊列 
void init_queue() 
{ 
queue=(LINK)malloc(sizeof(*queue)); 
queue->node=NULL; 
queue->f=-1; 
queue->next=(LINK)malloc(sizeof(*queue)); 
queue->next->f=MAXINT; 
queue->next->node=NULL; 
queue->next->next=NULL; 
} 
// 待處理節(jié)點入隊列, 依靠對目的地估價距離插入排序 
void enter_queue(TREE node,int f) 
{ 
LINK p=queue,father,q; 
while(f>p->f) { 
father=p; 
p=p->next; 
assert(p); 
} 
q=(LINK)malloc(sizeof(*q)); 
assert(queue); 
q->f=f,q->node=node,q->next=p; 
father->next=q; 
} 
// 將離目的地估計最近的方案出隊列 
TREE get_from_queue() 
{ 
TREE bestchoice=queue->next->node; 
LINK next=queue->next->next; 
free(queue->next); 
queue->next=next; 
stack[stacktop++]=bestchoice; 
assert(stacktop<STACKSIZE); 
return bestchoice; 
} 
// 釋放棧頂節(jié)點 
void pop_stack() 
{ 
free(stack[--stacktop]); 
} 
// 釋放申請過的所有節(jié)點 
void freetree() 
{ 
int i; 
LINK p; 
for (i=0;i<stacktop;i++) 
free(stack[i]); 
while (queue) { 
p=queue; 
free(p->node); 
queue=queue->next; 
free(p); 
} 
} 
// 估價函數(shù),估價 x,y 到目的地的距離,估計值必須保證比實際值小 
int judge(int x,int y) 
{ 
int distance; 
distance=abs(end_x-x)+abs(end_y-y); 
return distance; 
} 
// 嘗試下一步移動到 x,y 可行否 
int trytile(int x,int y,TREE father) 
{ 
TREE p=father; 
int h; 
if (map[y][x]!=' ') return 1; // 如果 (x,y) 處是障礙,失敗 
while (p) { 
if (x==tile_x(p->tile) && y==tile_y(p->tile)) return 1; //如果 (x,y) 曾經(jīng) 
經(jīng)過,失敗 
p=p->father; 
} 
h=father->h+1; 
if (h>=dis_map[y][x]) return 1; // 如果曾經(jīng)有更好的方案移動到 (x,y) 失敗 
dis_map[y][x]=h; // 記錄這次到 (x,y) 的距離為歷史最佳距離 
// 將這步方案記入待處理隊列 
p=(TREE)malloc(sizeof(*p)); 
p->father=father; 
p->h=father->h+1; 
p->tile=tile_num(x,y); 
enter_queue(p,p->h+judge(x,y)); 
return 0; 
} 
// 路徑尋找主函數(shù) 
void findpath(int *path) 
{ 
TREE root; 
int i,j; 
stacktop=0; 
for (i=0;i<map_h;i++) 
for (j=0;j<map_w;j++) 
dis_map[i][j]=MAXINT; 
init_queue(); 
root=(TREE)malloc(sizeof(*root)); 
root->tile=tile_num(start_x,start_y); 
root->h=0; 
root->father=NULL; 
enter_queue(root,judge(start_x,start_y)); 
for (;;) { 
int x,y,child; 
TREE p; 
root=get_from_queue(); 
if (root==NULL) { 
*path=-1; 
return; 
} 
x=tile_x(root->tile); 
y=tile_y(root->tile); 
if (x==end_x && y==end_y) break; // 達到目的地成功返回 
child=trytile(x,y-1,root); //嘗試向上移動 
child&=trytile(x,y+1,root); //嘗試向下移動 
child&=trytile(x-1,y,root); //嘗試向左移動 
child&=trytile(x+1,y,root); //嘗試向右移動 
if (child!=0) 
pop_stack(); // 如果四個方向均不能移動,釋放這個死節(jié)點 
} 
// 回溯樹，將求出的最佳路徑保存在 path[] 中 
for (i=0;root;i++) { 
path[i]=root->tile; 
root=root->father; 
} 
path[i]=-1; 
freetree(); 
} 
void printpath(int *path) 
{ 
int i; 
for (i=0;path[i]>=0;i++) { 
gotoxy(tile_x(path[i])+1,tile_y(path[i])+1); 
cprintf("\xfe"); 
} 
} 
int readmap() 
{ 
FILE *f; 
int i,j; 
f=fopen("map.dat","r"); 
assert(f); 
fscanf(f,"%d,%d\n",&map_w,&map_h); 
for (i=0;i<map_h;i++) 
fgets(&map[i][0],map_w+1,f); 
fclose(f); 
start_x=-1,end_x=-1; 
for (i=0;i<map_h;i++) 
for (j=0;j<map_w;j++) { 
if (map[i][j]=='s') map[i][j]=' ',start_x=j,start_y=i; 
if (map[i][j]=='e') map[i][j]=' ',end_x=j,end_y=i; 
} 
assert(start_x>=0 && end_x>=0); 
return 0; 
} 
void showmap() 
{ 
int i,j; 
clrscr(); 
for (i=0;i<map_h;i++) { 
gotoxy(1,i+1); 
for (j=0;j<map_w;j++) 
if (map[i][j]!=' ') cprintf("\xdb"); 
else cprintf(" "); 
} 
gotoxy(start_x+1,start_y+1); 
cprintf("s"); 
gotoxy(end_x+1,end_y+1); 
cprintf("e"); 
} 
int main() 
{ 
int path[MAXINT]; 
readmap(); 
showmap(); 
getch(); 
findpath(path); 
printpath(path); 
getch(); 
return 0; 
}