最優(yōu)路徑

1、由于Dijkstra算法的基礎(chǔ)是平面網(wǎng)絡(luò)拓?fù)淠Ｐ鸵虼水?dāng)計(jì)算網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)目較大時(shí)計(jì)算的時(shí)間將急劇膨脹。為了快速地搜索到最優(yōu)路徑基于分層網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)(HiTopo)提出了雙向分層搜索最優(yōu)路徑算法(BHWA)該算法對(duì)現(xiàn)有分層路徑算法進(jìn)行了以下兩點(diǎn)改進(jìn)(1)將分級(jí)網(wǎng)絡(luò)的局部連通性作為劃分子圖的指標(biāo)(2)在路徑計(jì)算過程中使用弧段作為搜索目標(biāo)并采取了雙向搜索策略。通過北京道路數(shù)據(jù)的實(shí)驗(yàn)表明該算法在保持分層路徑算法高效性的基礎(chǔ)上還提高了路徑搜索結(jié)果的

2、準(zhǔn)確性通過進(jìn)一步研究表明如果使用啟發(fā)式搜索來對(duì)算法進(jìn)行優(yōu)化則可以使算法的速度有更大的提升。1、把原來用于存放已處理節(jié)點(diǎn)的堆棧改為(ste_queue)隊(duì)列，這樣在從st_queue隊(duì)列出列時(shí)可直接放入ste_queue中。2、解除了地圖大小的限制(如果有64K內(nèi)存限制時(shí)，地圖大小只能是180x180)3、刪除了原程序中的一些冗余，見程序中的注釋。4、程序繼續(xù)使用dis_map數(shù)組保存各點(diǎn)歷史歷史最佳距離，也包含了某點(diǎn)是否已經(jīng)經(jīng)過的信息，

3、雖然這樣做可能會(huì)比使用鏈表多用一些內(nèi)存，但是在搜索時(shí)可以節(jié)省不時(shí)間。5、程序更具有實(shí)用性，可直接或修改后運(yùn)用于你的程序中，但請(qǐng)你使用該代碼后應(yīng)該返回一些信息給我，如算法的改進(jìn)或使用于什么程序等。本程序可以用BlC或DJGPP編譯，并附帶有一個(gè)數(shù)據(jù)文件map.dat保存有地圖的數(shù)據(jù)，（注：該地圖文件格式與風(fēng)云的原代碼的地圖格式不一樣）算法描述：findpath()把S點(diǎn)加入樹根（各點(diǎn)所在的樹的高度表示從S點(diǎn)到該點(diǎn)所走過的步數(shù)）；把S點(diǎn)加入

4、排序隊(duì)列（按該點(diǎn)到E點(diǎn)的距離排序走過的步數(shù)從小到大排序）；1、排序隊(duì)列st_queue中距離最小的第一個(gè)點(diǎn)出列，并保存入ste_queue中2、從出列的點(diǎn)出發(fā)，分別向4個(gè)（或8個(gè)）方向中的一個(gè)各走出一步3、并估算第2步所走到位置到目標(biāo)點(diǎn)的距離，并把該位置加入樹，最后把該點(diǎn)按距離從小到大排序后并放入隊(duì)列中。(由trytile函數(shù)實(shí)現(xiàn))。4、如果該點(diǎn)從四個(gè)方向上都不能移動(dòng)，則把該點(diǎn)從ste_queue中刪除5、回到第一點(diǎn)，直到找到E點(diǎn)則結(jié)束

5、從目標(biāo)點(diǎn)回溯樹，直到樹根則可以找到最佳路徑，并保存在path[]中#defineNDEBUG#include#include#include#include#include#definetile_num(xy)((y)map_w(x))將xy坐標(biāo)轉(zhuǎn)換為地圖上塊的編號(hào)#definetile_x(n)((n)%map_w)由塊編號(hào)得出xy坐標(biāo)ste_queue=(LINK)malloc(sizeof(ste_queue))ste_queue

6、node=NULLste_queuef=1ste_queuenext=NULL待處理節(jié)點(diǎn)入隊(duì)列依靠對(duì)目的地估價(jià)距離插入排序voidenter_queue(TREEnodeintf)LINKp=st_queuefatherqwhile(fpf)father=pp=pnextassert(p)q=(LINK)malloc(sizeof(q))assert(st_queue)qf=fqnode=nodeqnext=pfathernext=q將

7、離目的地估計(jì)最近的方案出隊(duì)列TREEget_from_queue(void)LINKbestchoice=st_queuenextLINKnext=st_queuenextnextst_queuenext=nextbestchoicenext=ste_queuenextTop3樓keikei007（keikei）回復(fù)于2004062119:16:02得分0ste_queuenext=bestchoicereturnbestchoicen