基于A星算法的最優(yōu)路徑規(guī)劃系統(tǒng)

人工智能課程大作業(yè)PAGE1基于A*算法的最優(yōu)路徑規(guī)劃系統(tǒng)XXXXXXXXX摘要：人工智能(ArtificialIntelligence)是當前科學技術(shù)發(fā)展的一門前沿學科，同時也是一門新思想，新觀念，新理論，新技術(shù)不斷出現(xiàn)的新興學科以及正在發(fā)展的學科。本文將主要介紹人工智能在搜索方法上的應(yīng)用，即基于A*算法的最優(yōu)路徑規(guī)劃問題的解決方法。A*算法是一種求解最短路徑的有效方法，也是人工智能算法中一種簡單的啟發(fā)式搜索方法。本文介紹了A*算法的原理及實現(xiàn)機制，以及在搜索出的結(jié)點解空間集中，用A*算法如何選擇最優(yōu)結(jié)點，最終求解出最短路徑的過程。關(guān)鍵詞：人工智能；研究報告；模板本組成員：xxxxxxx本人分工：A*算法設(shè)計及實現(xiàn)1引言人工智能是在計算機科學，控制論，信息論，神經(jīng)心理學，哲學，語言學等多種學科研究的基礎(chǔ)發(fā)展起來的，因此又可把它看作是一門綜合性的邊緣學科[1]。它的出現(xiàn)及所取得的成就引起了人們的高度重視,并取得了很高的評價。有的人把它與空間技術(shù)，原子能技術(shù)一起并譽為20世紀的三大科學技術(shù)成就。人工智能學科研究的主要內(nèi)容包括：知識表示、自動推理和搜索方法、機器學習和知識獲取、知識處理系統(tǒng)、自然語言理計算機視覺、智能機器人、自動程序設(shè)計等方面。本文主要介紹在路徑規(guī)劃問題上使用A*搜索算法來找到最優(yōu)路徑的設(shè)計與實現(xiàn)。路徑規(guī)劃是指在旅行前或旅行中為駕駛員提供參考行駛路線的過程，是車輛定位與導(dǎo)航系統(tǒng)的基本功能之一針對陸地車輛導(dǎo)航的不同要求，在路徑規(guī)劃中可采取多種優(yōu)化標準，如最短距離、最少行駛時間或收費。本實驗中將使用最短距離來尋找最優(yōu)路徑。2算法原理與系統(tǒng)設(shè)計2.1A*算法的基本思想A*算法在人工智能中是一種典型的啟發(fā)式搜索算法，通過選擇合適的估價函數(shù)，指導(dǎo)搜索朝著最有希望的方向前進,以求得最優(yōu)解[2]。A*算法中，關(guān)鍵是求估價函數(shù)：f(n)=g(n)+h(n).其中，g(n)是從起點u到當前節(jié)點n己付出的代價，h(n)是從當前節(jié)點n到目標節(jié)點v的代價估計函數(shù)，必須保證h(n)<=h’(n)，其中h’(n)是從當前點到目標點的實際最小代價。2.2A*算法的步驟A*算法的搜索步驟如下：（1）給起始節(jié)點標記，對它的沒有標記過的子節(jié)點進行擴展；（2）對每一個子節(jié)點計算評價函數(shù)值，按評價值的大小進行排列，找出評價值最小的節(jié)點，并給它作標記，如果當前節(jié)點就是目標節(jié)點，則停止搜索。（3）否則，對最新被標記的節(jié)點進行第（2）步處理，并記錄最短路徑。2.3算法分析A*算法是利用對問題的了解和對問題求解過程和解的了解，尋求某種有利于問題求解的啟發(fā)信息，從而利用這些啟發(fā)信息去搜索最優(yōu)路徑它不用遍歷整個地圖，而是每一步搜索都根據(jù)啟發(fā)函數(shù)朝著某個方向搜索當?shù)貓D很大很復(fù)雜時，它的計算復(fù)雜度大大優(yōu)于算法，是一種搜索速度非?？?、效率非常高的算法。但是，相應(yīng)的A*算法也有它的缺點，啟發(fā)性信息是人為加入的，有很大的主觀性，直接取決于操作者的經(jīng)驗，對于不同的情形要用不同的啟發(fā)信息和啟發(fā)函數(shù)，且他們的選取難度比較大，很大程度上找不到最優(yōu)路徑。2.4系統(tǒng)設(shè)計系統(tǒng)的實現(xiàn)流程圖如圖2.1所示。圖2.1系統(tǒng)的實現(xiàn)流程圖首先判斷初始結(jié)點的周圍8個結(jié)點是否有障礙點，從除障礙點以外的結(jié)點中求解出代價最小的結(jié)點，并加入到結(jié)果列表中。求解結(jié)點代價是根據(jù)A*算法的估價函數(shù)f(n)=g(n)+h(n)。其中g(shù)(n)是從起始結(jié)點到當前節(jié)點n己付出的代價，h(n)是從當前節(jié)點n到目標節(jié)點的代價估計。對于本實驗中，設(shè)計的g(n)=10（當前結(jié)點與起始結(jié)點在同一水平線或者豎直線上。如圖2.2中，初始結(jié)點，即藍結(jié)點與1、3、5、7結(jié)點之間的代價即為10。）g(n)=14（當前結(jié)點與起始結(jié)點在同一對角線上時。如圖2.2中，初始結(jié)點，即藍結(jié)點與0、2、4、6結(jié)點之間的代價即為14。）對于本實驗中，h(n)=(當前結(jié)點與目標結(jié)點之間橫坐標格數(shù)+當前結(jié)點與目標結(jié)點之間縱坐標格數(shù))*10。如圖2.2中，當前結(jié)點依次為0、1、2、3、4、5、6、7，分別與紅色目標結(jié)點求解h(n)。圖2.2搜索圖每次求解出的8個h(n)，比較大小，選出最小的結(jié)點作為起始節(jié)點繼續(xù)搜索。直到遇到目標結(jié)點便結(jié)束搜索，畫出求解出的最優(yōu)路徑。3系統(tǒng)實現(xiàn)voidCAxingTestDlg::ExecuteCalculate(RectIndex{ //判斷8個相鄰點里是否有障礙點 for(inti=0;i<8;i++) { for(intj=0;j<blockPointNum;j++) { if(RI[i].m==blockIndexM[j]&&RI[i].n==blockIndexN[j])//有障礙點 { RI[i].weight=10000; } } } //得到權(quán)值最小的點 intminWeight=10000,minweightIndexM,minweightIndexN; for(inti=0;i<8;i++) { minWeight=min(minWeight,RI[i].weight); } resultRI->weight=minWeight; for(inti=0;i<8;i++)//獲得權(quán)值最小點的坐標 { if(RI[i].weight==minWeight) { minweightIndexM=RI[i].m; minweightIndexN=RI[i].n; } } resultRI->m=minweightIndexM; resultRI->n=minweightIndexN; pathPointIndex[pathPointIndexSub].m=resultRI->m;//存儲路徑 pathPointIndex[pathPointIndexSub].n=resultRI->n; pathPointIndex[pathPointIndexSub].weight=resultRI->weight;//存儲當前遍歷點的權(quán)值 totalWeigeht+=pathPointIndex[pathPointIndexSub].weight; pathPointIndexSub++; //判斷8個相鄰點是否有目標點 for(inti=0;i<8;i++) { if(RI[i].m==endRectIndex.m&&RI[i].n==endRectIndex.n) { *find=true; break; } }}voidCAxingTestDlg::GetAroundPoint(RectIndexRI0,RectIndexRI[])//獲得鄰接點坐標，同時計算權(quán)值{ inti=RI0.m; intj=RI0.n; intpostM,postN; RI[0].m=i-1; RI[0].n=j-1; postM=(i-1)>endRectIndex.m?(i-1-endRectIndex.m):(endRectIndex.m-(i-1)); postN=(j-1)>endRectIndex.n?(j-1-endRectIndex.n):(endRectIndex.n-(j-1)); RI[0].weight=(postM+postN)*10+14; RI[1].m=i-1; RI[1].n=j; postM=(i-1)>endRectIndex.m?(i-1-endRectIndex.m):(endRectIndex.m-(i-1)); postN=j>endRectIndex.n?(j-endRectIndex.n):(endRectIndex.n-j); RI[1].weight=(postM+postN)*10+10; RI[2].m=i-1; RI[2].n=j+1; postM=(i-1)>endRectIndex.m?(i-1-endRectIndex.m):(endRectIndex.m-(i-1)); postN=(j+1)>endRectIndex.n?(j+1-endRectIndex.n):(endRectIndex.n-(j+1)); RI[2].weight=(postM+postN)*10+14; RI[3].m=i; RI[3].n=j-1; postM=i>endRectIndex.m?(i-endRectIndex.m):(endRectIndex.m-i); postN=(j-1)>endRectIndex.n?(j-1-endRectIndex.n):(endRectIndex.n-(j-1)); RI[3].weight=(postM+postN)*10+10; RI[4].m=i; RI[4].n=j+1; postM=i>endRectIndex.m?(i-endRectIndex.m):(endRectIndex.m-i); postN=(j+1)>endRectIndex.n?(j+1-endRectIndex.n):(endRectIndex.n-(j+1)); RI[4].weight=(postM+postN)*10+10; RI[5].m=i+1; RI[5].n=j-1; postM=(i+1)>endRectIndex.m?(i+1-endRectIndex.m):(endRectIndex.m-(i+1)); postN=(j-1)>endRectIndex.n?(j-1-endRectIndex.n):(endRectIndex.n-(j-1)); RI[5].weight=(postM+postN)*10+14; RI[6].m=i+1; RI[6].n=j; postM=(i+1)>endRectIndex.m?(i+1-endRectIndex.m):(endRectIndex.m-(i+1)); postN=j>endRectIndex.n?(j-endRectIndex.n):(endRectIndex.n-j); RI[6].weight=(postM+postN)*10+10; RI[7].m=i+1; RI[7].n=j+1; postM=(i+1)>endRectIndex.m?(i+1-endRectIndex.m):(endRectIndex.m-(i+1)); postN=(j+1)>endRectIndex.n?(j+1-endRectIndex.n):(endRectIndex.n-(j+1)); RI[7].weight=(postM+postN)*10+14; if(i-1<0) { RI[0].weight=10000; RI[1].weight=10000; RI[2].weight=10000; } if(j-1<0) { RI[0].weight=10000; RI[3].weight=10000; RI[5].weight=10000; } if(i+1>nRows-1) { RI[5].weight=10000; RI[6].weight=10000; RI[7].weight=10000; } if(j+1>nCols-1) { RI[2].weight=10000; RI[4].weight=10000; RI[7].weight=10000; } }4實驗或測試