a化演算法

A. A*演算法的實際運用

估價值與實際值越接近，估價函數取得就越好
例如對於幾何路網來說，可以取兩節點間曼哈頓距離做為估價值，即f=g(n) + (abs(dx - nx) + abs(dy - ny))；這樣估價函數f在g值一定的情況下，會或多或少的受估價值h的制約，節點距目標點近，h值小，f值相對就小，能保證最短路的搜索向終點的方向進行。明顯優於Dijkstra演算法的毫無方向的向四周搜索。
conditions of heuristic
Optimistic (must be less than or equal to the real cost)
As close to the real cost as possible
詳細內容：
創建兩個表，OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
算起點的估價值;
將起點放入OPEN表; while(OPEN!=NULL){從OPEN表中取估價值f(n)最小的節點n;if(n節點==目標節點)break;for(當前節點n的每個子節點X){算X的估價值;if(XinOPEN)if(X的估價值小於OPEN表的估價值){把n設置為X的父親;更新OPEN表中的估價值;//取最小路徑的估價值}if(XinCLOSE)continue;if(Xnotinboth){把n設置為X的父親;求X的估價值;並將X插入OPEN表中;//還沒有排序}}//endfor將n節點插入CLOSE表中;按照估價值將OPEN表中的節點排序;//實際上是比較OPEN表內節點f的大小，從最小路徑的節點向下進行。}//endwhile(OPEN!=NULL)保存路徑，即從終點開始，每個節點沿著父節點移動直至起點，這就是你的路徑；
用C語言實現A*最短路徑搜索演算法 ，作者 Tittup frog(跳跳蛙)。 #include<stdio.h>#include<math.h>#defineMaxLength100//用於優先隊列（Open表）的數組#defineHeight15//地圖高度#defineWidth20//地圖寬度#defineReachable0//可以到達的結點#defineBar1//障礙物#definePass2//需要走的步數#defineSource3//起點#defineDestination4//終點#defineSequential0//順序遍歷#defineNoSolution2//無解決方案#defineInfinity0xfffffff#defineEast(1<<0)#defineSouth_East(1<<1)#defineSouth(1<<2)#defineSouth_West(1<<3)#defineWest(1<<4)#defineNorth_West(1<<5)#defineNorth(1<<6)#defineNorth_East(1<<7)typedefstruct{signedcharx,y;}Point;constPointdir[8]={{0,1},//East{1,1},//South_East{1,0},//South{1,-1},//South_West{0,-1},//West{-1,-1},//North_West{-1,0},//North{-1,1}//North_East};unsignedcharwithin(intx,inty){return(x>=0&&y>=0&&x<Height&&y<Width);}typedefstruct{intx,y;unsignedcharreachable,sur,value;}MapNode;typedefstructClose{MapNode*cur;charvis;structClose*from;floatF,G;intH;}Close;typedefstruct//優先隊列（Open表）{intlength;//當前隊列的長度Close*Array[MaxLength];//評價結點的指針}Open;staticMapNodegraph[Height][Width];staticintsrcX,srcY,dstX,dstY;//起始點、終點staticCloseclose[Height][Width];//優先隊列基本操作voidinitOpen(Open*q)//優先隊列初始化{q->length=0;//隊內元素數初始為0}voidpush(Open*q,Closecls[Height][Width],intx,inty,floatg){//向優先隊列（Open表）中添加元素Close*t;inti,mintag;cls[x][y].G=g;//所添加節點的坐標cls[x][y].F=cls[x][y].G+cls[x][y].H;q->Array[q->length++]=&(cls[x][y]);mintag=q->length-1;for(i=0;i<q->length-1;i++){if(q->Array[i]->F<q->Array[mintag]->F){mintag=i;}}t=q->Array[q->length-1];q->Array[q->length-1]=q->Array[mintag];q->Array[mintag]=t;//將評價函數值最小節點置於隊頭}Close*shift(Open*q){returnq->Array[--q->length];}//地圖初始化操作voidinitClose(Closecls[Height][Width],intsx,intsy,intdx,intdy){//地圖Close表初始化配置inti,j;for(i=0;i<Height;i++){for(j=0;j<Width;j++){cls[i][j].cur=&graph[i][j];//Close表所指節點cls[i][j].vis=!graph[i][j].reachable;//是否被訪問cls[i][j].from=NULL;//所來節點cls[i][j].G=cls[i][j].F=0;cls[i][j].H=abs(dx-i)+abs(dy-j);//評價函數值}}cls[sx][sy].F=cls[sx][sy].H;//起始點評價初始值//cls[sy][sy].G=0;//移步花費代價值cls[dx][dy].G=Infinity;}voidinitGraph(constintmap[Height][Width],intsx,intsy,intdx,intdy){//地圖發生變化時重新構造地inti,j;srcX=sx;//起點X坐標srcY=sy;//起點Y坐標dstX=dx;//終點X坐標dstY=dy;//終點Y坐標for(i=0;i<Height;i++){for(j=0;j<Width;j++){graph[i][j].x=i;//地圖坐標Xgraph[i][j].y=j;//地圖坐標Ygraph[i][j].value=map[i][j];graph[i][j].reachable=(graph[i][j].value==Reachable);//節點可到達性graph[i][j].sur=0;//鄰接節點個數if(!graph[i][j].reachable){continue;}if(j>0){if(graph[i][j-1].reachable)//left節點可以到達{graph[i][j].sur|=West;graph[i][j-1].sur|=East;}if(i>0){if(graph[i-1][j-1].reachable&&graph[i-1][j].reachable&&graph[i][j-1].reachable)//up-left節點可以到達{graph[i][j].sur|=North_West;graph[i-1][j-1].sur|=South_East;}}}if(i>0){if(graph[i-1][j].reachable)//up節點可以到達{graph[i][j].sur|=North;graph[i-1][j].sur|=South;}if(j<Width-1){if(graph[i-1][j+1].reachable&&graph[i-1][j].reachable&&map[i][j+1]==Reachable)//up-right節點可以到達{graph[i][j].sur|=North_East;graph[i-1][j+1].sur|=South_West;}}}}}}intbfs(){inttimes=0;inti,curX,curY,surX,surY;unsignedcharf=0,r=1;Close*p;Close*q[MaxLength]={&close[srcX][srcY]};initClose(close,srcX,srcY,dstX,dstY);close[srcX][srcY].vis=1;while(r!=f){p=q[f];f=(f+1)%MaxLength;curX=p->cur->x;curY=p->cur->y;for(i=0;i<8;i++){if(!(p->cur->sur&(1<<i))){continue;}surX=curX+dir[i].x;surY=curY+dir[i].y;if(!close[surX][surY].vis){close[surX][surY].from=p;close[surX][surY].vis=1;close[surX][surY].G=p->G+1;q[r]=&close[surX][surY];r=(r+1)%MaxLength;}}times++;}returntimes;}intastar(){//A*演算法遍歷//inttimes=0;inti,curX,curY,surX,surY;floatsurG;Openq;//Open表Close*p;initOpen(&q);initClose(close,srcX,srcY,dstX,dstY);close[srcX][srcY].vis=1;push(&q,close,srcX,srcY,0);while(q.length){//times++;p=shift(&q);curX=p->cur->x;curY=p->cur->y;if(!p->H){returnSequential;}for(i=0;i<8;i++){if(!(p->cur->sur&(1<<i))){continue;}surX=curX+dir[i].x;surY=curY+dir[i].y;if(!close[surX][surY].vis){close[surX][surY].vis=1;close[surX][surY].from=p;surG=p->G+sqrt((curX-surX)*(curX-surX)+(curY-surY)*(curY-surY));push(&q,close,surX,surY,surG);}}}//printf(times:%d ,times);returnNoSolution;//無結果}constintmap[Height][Width]={{0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,1,1},{0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1},{0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,1},{0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,1},{0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,1,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0},{0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0},{0,1,0,0,0,0,1,0,0,0,0,0,0,1,0,1,0,0,0,1},{0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0}};constcharSymbol[5][3]={□,▓,▽,☆,◎};voidprintMap(){inti,j;for(i=0;i<Height;i++){for(j=0;j<Width;j++){printf(%s,Symbol[graph[i][j].value]);}puts();}puts();}Close*getShortest(){//獲取最短路徑intresult=astar();Close*p,*t,*q=NULL;switch(result){caseSequential://順序最近p=&(close[dstX][dstY]);while(p)//轉置路徑{t=p->from;p->from=q;q=p;p=t;}close[srcX][srcY].from=q->from;return&(close[srcX][srcY]);caseNoSolution:returnNULL;}returnNULL;}staticClose*start;staticintshortestep;intprintShortest(){Close*p;intstep=0;p=getShortest();start=p;if(!p){return0;}else{while(p->from){graph[p->cur->x][p->cur->y].value=Pass;printf(（%d，%d）→ ,p->cur->x,p->cur->y);p=p->from;step++;}printf(（%d，%d） ,p->cur->x,p->cur->y);graph[srcX][srcY].value=Source;graph[dstX][dstY].value=Destination;returnstep;}}voidclearMap(){//ClearMapMarksofStepsClose*p=start;while(p){graph[p->cur->x][p->cur->y].value=Reachable;p=p->from;}graph[srcX][srcY].value=map[srcX][srcY];graph[dstX][dstY].value=map[dstX][dstY];}voidprintDepth(){inti,j;for(i=0;i<Height;i++){for(j=0;j<Width;j++){if(map[i][j]){printf(%s,Symbol[graph[i][j].value]);}else{printf(%2.0lf,close[i][j].G);}}puts();}puts();}voidprintSur(){inti,j;for(i=0;i<Height;i++){for(j=0;j<Width;j++){printf(%02x,graph[i][j].sur);}puts();}puts();}voidprintH(){inti,j;for(i=0;i<Height;i++){for(j=0;j<Width;j++){printf(%02d,close[i][j].H);}puts();}puts();}intmain(intargc,constchar**argv){initGraph(map,0,0,0,0);printMap();while(scanf(%d%d%d%d,&srcX,&srcY,&dstX,&dstY)!=EOF){if(within(srcX,srcY)&&within(dstX,dstY)){if(shortestep=printShortest()){printf(從（%d，%d）到（%d，%d）的最短步數是:%d ,srcX,srcY,dstX,dstY,shortestep);printMap();clearMap();bfs();//printDepth();puts((shortestep==close[dstX][dstY].G)?正確:錯誤);clearMap();}else{printf(從（%d，%d）不可到達（%d，%d） ,srcX,srcY,dstX,dstY);}}else{puts(輸入錯誤！);}}return(0);}

B. 搜索演算法中,A演算法A*演算法的區別（急）

A演算法一般指某個搜索演算法的樸素的思路
A*指使用了啟發式搜索之後的演算法,也就是運算速度會快很多,但不一定能保證最後得到最優解

C. a演算法不一定能找到目標節點

A演算法不一定能找到目標結點(A)

A.正確

B.錯誤

演算法，是指解題方案的准確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制。也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。如果一個演算法有缺陷，或不適合於某個問題。

執行這個演算法將不會解決這個問題。不同的演算法可能用不同的時間，空間或效率來完成同樣的任務。一個演算法的優劣可以用空間復雜度與時間復雜度來衡量。演算法中的指令描述的是一個計算，當其運行時能從一個初始狀態和（可能為空的）初始輸入開始。

經過一系列有限而清晰定義的狀態，最終產生輸出並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化演算法在內的一些演算法，包含了一些隨機輸入。形式化演算法的概念部分源自嘗試解決希爾伯特提出的判定問題。

並在其後嘗試定義有效計算性或者有效方法中成形。這些嘗試包括庫爾特·哥德爾、Jacques Herbrand和斯蒂芬·科爾·克萊尼分別於1930年、1934年和1935年提出的遞歸函數。

阿隆佐·邱奇於1936年提出的λ演算，1936年Emil Leon Post的Formulation 1和艾倫·圖靈1937年提出的圖靈機。即使在當前，依然常有直覺想法難以定義為形式化演算法的情況。

D. 人工智慧 A*演算法原理

A 演算法是啟發式演算法重要的一種，主要是用於在兩點之間選擇一個最優路徑，而A 的實現也是通過一個估值函數

上圖中這個熊到樹葉的 曼哈頓距離 就是藍色線所表示的距離，這其中不考慮障礙物，假如上圖每一個方格長度為1，那麼此時的熊的曼哈頓距離就為9.
起點（X1,Y1）,終點（X2,Y2）,H=|X2-X1|+|Y2-Y1|
我們也可以通過幾何坐標點來算出曼哈頓距離，還是以上圖為例，左下角為（0，0）點，熊的位置為（1，4），樹葉的位置為（7，1），那麼H=|7-1|+|1-4|=9。

還是以上圖為例，比如剛開始熊位置我們會加入到CLOSE列表中，而熊四周它可以移動到的點位我們會加入到OPEN列表中，並對熊四周的8個節點進行F=G+H這樣的估值運算，然後在這8個節點中選中一個F值為最小的節點，然後把再把這個節點從OPEN列表中刪除，加入到Close列表中，從接著在對這個節點的四周8個節點進行一個估值運算，再接著依次運算，這樣說大家可能不是太理解，我會在下邊做詳細解釋。

從起點到終點，我們通過A星演算法來找出最優路徑

我們把每一個方格的長度定義為1，那從起始點到5位置的代價就是1，到3的代價為1.41，定義好了我們接著看上圖，接著運算

第一步我們會把起始點四周的點加入OPEN列表中然後進行一個估值運算，運算結果如上圖，這其中大家看到一個小箭頭都指向了起點，這個箭頭就是指向父節點，而open列表的G值都是根據這個進行計算的，意思就是我從上一個父節點運行到此處時所需要的總代價，如果指向不一樣可能G值就不一樣，上圖中我們經過計算發現1點F值是7.41是最小的，那我們就選中這個點，並把1點從OPEN列表中刪除，加入到CLOSE列表中，但是我們在往下運算的時候發現1點的四周，2點，3點和起始點這三個要怎麼處理，首先起始點已經加入到了CLOSE，他就不需要再進行這種運算，這就是CLOSE列表的作用，而2點和3點我們也可以對他進行運算，2點的運算，我們從1移動到2點的時候，他需要的代價也就是G值會變成2.41，而H值是不會變的F=2.41+7=9.41，這個值我們發現大於原來的的F值，那我們就不能對他進行改變（把父節點指向1，把F值改為9.41，因為我們一直追求的是F值最小化），3點也同理。

在對1點四周進行運算後整個OPEN列表中有兩個點2點和3點的F值都是7.41，此時我們系統就可能隨機選擇一個點然後進行下一步運算，現在我們選中的是3點，然後對3點的四周進行運算，結果是四周的OPEN點位如果把父節點指向3點值時F值都比原來的大，所以不發生改變。我們在看整個OPEN列表中，也就2點的7.41值是最小的，那我們就選中2點接著運算。

我們在上一部運算中選中的是1點，上圖沒有把2點加入OPEN列表，因為有障礙物的阻擋從1點他移動不到2點，所以沒有把2點加入到OPEN列表中，整個OPEN列表中3的F=8是最小的，我們就選中3，我們對3點四周進行運算是我們發現4點經過計算G=1+1=2，F=2+6=8所以此時4點要進行改變，F變為8並把箭頭指向3點（就是把4點的父節點變為3），如下圖

我們就按照這種方法一直進行運算，最後 的運算結果如下圖

而我們通過目標點位根據箭頭（父節點），一步一步向前尋找最後我們發現了一條指向起點的路徑，這個就是我們所需要的最優路徑。 如下圖的白色選中區域

但是我們還要注意幾點

最優路徑有2個

這是我對A*演算法的一些理解，有些地方可能有BUG，歡迎大家指出，共同學習。

E. A*演算法優化

A演算法是游戲中路徑搜索的常見演算法。Dijkstra是最短路徑的經典演算法，A演算法的思路基本上和Dijkstra演算法一致，在Dijkstra演算法的基礎上增加了啟發函數，也就是：

f(n) = g(n) + h(n)

其中，n是路徑上某一點，g(n)是從出發點到該點的cost，h(n)是關於該點的啟發函數，通常是對從該點到目標花費的一個估計，例如到目標的直線距離或者曼哈頓距離。 A演算法每次選擇f(n)最小的點，然後更新所有g(n)。
如果你明白Dijkstra演算法，那麼在這里h(n) = 0 的話，A演算法就和Dijkstra演算法一樣了。
本文不詳細講解A演算法，需要詳細了解A演算法的具體過程的，參見以下兩篇文章：

理解A*演算法的具體過程
A*演算法詳解

A*演算法優化的關鍵在於h(n)的選擇。 一個啟發函數h(n)被稱為admissible的，是指h(n)的估計，不會超過節點N到目標的實際花費。
如果h(x)滿足以下條件，h(x)被稱為單調的(monotone, or consistent)。 對於任意一條邊(x,y),
h(x) <= d(x,y) + h(y)
其中d(x,y)是（x,y）的長度

如果滿足這個條件，就意味著沒有任何節點需要被處理多次，也就是說，在Dijkstra演算法中，新加入一個節點會導致已添加節點中cost降低的情況不會存在，也就不需要去更新已添加節點(稱為close set)。

如果一個啟發函數是單調的，那麼該啟發函數一定是admissible的。如果該啟發函數是admissible的，那麼可以證明A*在同類演算法中搜尋到最短的路徑。

問題出在這里：如果我們更在意的是搜索的時間空間花費，而不是最優結果，那麼A*演算法就有優化空間。所以我們放鬆要求，修改我們的啟發函數，使得我們搜尋到的路徑不會比最佳路徑差太多，就是優化演算法，稱為ε-admissible演算法。

有多種ε-admissible演算法，在此只舉例最簡單直接的一種： 加權A*(靜態加權)演算法。

假如ha(n)是一個admissible的啟發函數，我們選取新的啟發函數hw(n) = ε ha(n)，其中ε>1 作為啟發函數。就可以在某種程度上進行優化。 下圖1是使用ha(n)作為啟發式演算法，下圖2是使用hw(n)作為啟發式演算法，其中ε取5.

圖1：ha(x)作為啟發演算法

圖2：hn(x)作為啟發演算法

可以看出，ha(n)可以找到最小路徑，但是多了許多無用的搜索；而hw(n)找到的不是最優路徑，但是減少了大量無用搜索。
其他的優化演算法思路類似都是在於啟發函數的選擇。詳見參考文獻。

參考文獻：
https://en.wikipedia.org/wiki/A*_search_algorithm#Admissibility_and_optimality https://en.wikipedia.org/wiki/Consistent_heuristic

F. 廣義逆矩陣的計算方法

廣義逆矩陣的計算方法大致可分為三類：以滿秩分解和奇異值分解為基礎的直接法，迭代法和其他一些常用於低階矩陣的非凡方法。
以A+的計算為例。若A是一個秩為r的m×n階非零矩陣，記作（圖6），,有滿秩分解A=F·G,其中（圖7），則（圖8），即將廣義逆矩陣的計算化為通常逆矩陣的計算。常用LU分解和QR分解等方法實現滿秩分解，然後求出A+。若A有奇異值分解A=UDV*，其中U、V為m階和n階酉矩陣，（圖9）是m×n階矩陣，∑是r階對角陣，對角元（圖10）是A的r個非零奇異值（AA*的非零特徵值的平方根），則A+=VD+U*，其中（圖11）是n×m階矩陣。也可用豪斯霍爾德變換先將 A化為上雙對角陣J0=P*AQ，然後再對J0使用QR演算法化為矩陣D=G*J0h，於是A=(PG)D(Qh)*，故A+1=(Qh)D+(PG)*。設λ1是AA*的最大非零特徵值，若0<α<2/λ1，則計算A+的一個迭代法是x0=αA*，xn+1=(2I-Axn)，當n→∞時，xn收斂於A+。
格雷維爾逐次遞推法也是計算A+的常用方法。設A的第k列為αk(k=1,2,…,n)，A1=α1,Ak=(Ak-1,αk)(k=2,3，…,n),則（圖12），式中（圖13）（圖14）。
1955年以後，出現了大量的關於廣義逆矩陣的理論、應用和計算方法的文獻。70年代還出版了一些專著和會議錄，指出廣義逆矩陣在控制論、系統辨識、規劃論、網路理論、測量、統計和計量經濟學等方面的應用。

G. A*演算法介紹

姓名：車文揚 學號：16020199006

【嵌牛導讀】：A*演算法的逐步詳解

【嵌牛鼻子】：啟發式演算法

【嵌牛提問】：A*演算法的原理是什麼？

【嵌牛正文】：

A*演算法

路徑規劃是指的是機器人的最優路徑規劃問題，即依據某個或某些優化准則（如工作代價最小、行走路徑最短、行走時間最短等），在工作空間中找到一個從起始狀態到目標狀態能避開障礙物的最優路徑。機器人的路徑規劃應用場景極豐富，最常見如游戲中NPC及控制角色的位置移動，網路地圖等導航問題，小到家庭掃地機器人、無人機大到各公司正爭相開拓的無人駕駛汽車等。

目前路徑規劃演算法分為：

A*演算法原理：

在計算機科學中，A*演算法作為Dijkstra演算法的擴展，因其高效性而被廣泛應用於尋路及圖的遍歷，如星際爭霸等游戲中就大量使用。在理解演算法前，我們需要知道幾個概念：

搜索區域（The Search Area）：圖中的搜索區域被劃分為了簡單的二維數組，數組每個元素對應一個小方格，當然我們也可以將區域等分成是五角星，矩形等，通常將一個單位的中心點稱之為搜索區域節點（Node）。

開放列表(Open List)：我們將路徑規劃過程中待檢測的節點存放於Open List中，而已檢測過的格子則存放於Close List中。

父節點（parent）：在路徑規劃中用於回溯的節點，開發時可考慮為雙向鏈表結構中的父結點指針。

路徑排序（Path Sorting）：具體往哪個節點移動由以下公式確定：F(n) = G + H 。G代表的是從初始位置A沿著已生成的路徑到指定待檢測格子的移動開銷。H指定待測格子到目標節點B的估計移動開銷。

啟發函數（Heuristics Function）：H為啟發函數，也被認為是一種試探，由於在找到唯一路徑前，我們不確定在前面會出現什麼障礙物，因此用了一種計算H的演算法，具體根據實際場景決定。在我們簡化的模型中，H採用的是傳統的曼哈頓距離（Manhattan Distance），也就是橫縱向走的距離之和。

如下圖所示，綠色方塊為機器人起始位置A，紅色方塊為目標位置B，藍色為障礙物。

我們把要搜尋的區域劃分成了正方形的格子。這是尋路的第一步，簡化搜索區域。這個特殊的方法把我們的搜索區域簡化為了2 維數組。數組的每一項代表一個格子，它的狀態就是可走(walkalbe)或不可走(unwalkable) 。現用A*演算法尋找出一條自A到B的最短路徑，每個方格的邊長為10，即垂直水平方向移動開銷為10。因此沿對角移動開銷約等於14。具體步驟如下：

從起點 A 開始，把它加入到一個由方格組成的open list(開放列表) 中，這個open list像是一個購物清單。Open list里的格子是可能會是沿途經過的，也有可能不經過。因此可以將其看成一個待檢查的列表。查看與A相鄰的8個方格 ，把其中可走的 (walkable) 或可到達的(reachable) 方格加入到open list中。並把起點 A 設置為這些方格的父節點 (parent node) 。然後把 A 從open list中移除，加入到close list(封閉列表) 中，close list中的每個方格都是不需要再關注的。

如下圖所示，深綠色的方格為起點A，它的外框是亮藍色，表示該方格被加入到了close list 。與它相鄰的黑色方格是需要被檢查的，他們的外框是亮綠色。每個黑方格都有一個灰色的指針指向他們的父節點A。

下一步，我們需要從open list中選一個與起點A相鄰的方格。但是到底選擇哪個方格好呢？選F值最小的那個。我們看看下圖中的一些方格。在標有字母的方格中G = 10 。這是因為水平方向從起點到那裡只有一個方格的距離。與起點直接相鄰的上方，下方，左方的方格的G 值都是10 ，對角線的方格G 值都是14 。H值通過估算起點到終點( 紅色方格) 的Manhattan 距離得到，僅作橫向和縱向移動，並且忽略沿途的障礙。使用這種方式，起點右邊的方格到終點有3 個方格的距離，因此H = 30 。這個方格上方的方格到終點有4 個方格的距離( 注意只計算橫向和縱向距離) ，因此H = 40 。

比較open list中節點的F值後，發現起點A右側節點的F=40，值最小。選作當前處理節點，並將這個點從Open List刪除，移到Close List中。

對這個節點周圍的8個格子進行判斷，若是不可通過（比如牆，水，或是其他非法地形）或已經在Close List中，則忽略。否則執行以下步驟：

若當前處理節點的相鄰格子已經在Open List中，則檢查這條路徑是否更優，即計算經由當前處理節點到達那個方格是否具有更小的 G值。如果沒有，不做任何操作。相反，如果G值更小，則把那個方格的父節點設為當前處理節點 ( 我們選中的方格 ) ，然後重新計算那個方格的 F 值和 G 值。

若當前處理節點的相鄰格子不在Open List中，那麼把它加入，並將它的父節點設置為該節點。

按照上述規則我們繼續搜索，選擇起點右邊的方格作為當前處理節點。它的外框用藍線打亮，被放入了close list 中。然後我們檢查與它相鄰的方格。它右側的3個方格是牆壁，我們忽略。它左邊的方格是起點，在close list 中，我們也忽略。其他4個相鄰的方格均在open list 中，我們需要檢查經由當前節點到達那裡的路徑是否更好。我們看看上面的方格，它現在的G值為14 ，如果經由當前方格到達那裡，G值將會為20( 其中10為從起點到達當前方格的G值，此外還要加上從當前方格縱向移動到上面方格的G值10) ，因此這不是最優的路徑。看圖就會明白直接從起點沿對角線移動到那個方格比先橫向移動再縱向移動要好。

當把4個已經在open list 中的相鄰方格都檢查後，沒有發現經由當前節點的更好路徑，因此不做任何改變。接下來要選擇下一個待處理的節點。因此再次遍歷open list ，現在open list中只有7 個方格了，我們需要選擇F值最小的那個。這次有兩個方格的F值都是54，選哪個呢？沒什麼關系。從速度上考慮，選擇最後加入open list 的方格更快。因此選擇起點右下方的方格，如下圖所示。

接下來把起點右下角F值為54的方格作為當前處理節點，檢查其相鄰的方格。我們發現它右邊是牆（牆下面的一格也忽略掉，假定牆角不能直接穿越)，忽略之。這樣還剩下 5 個相鄰的方格。當前方格下面的 2 個方格還沒有加入 open list ，所以把它們加入，同時把當前方格設為他們的父親。在剩下的 3 個方格中，有 2 個已經在 close list 中 ( 一個是起點，一個是當前方格上面的方格，外框被加亮的 ) ，我們忽略它們。最後一個方格，也就是當前方格左邊的方格，檢查經由當前方格到達那裡是否具有更小的 G 值。沒有，因此我們准備從 open list 中選擇下一個待處理的方格。

不斷重復這個過程，直到把終點也加入到了open list 中，此時如下圖所示。注意在起點下方2 格處的方格的父親已經與前面不同了。之前它的G值是28並且指向它右上方的方格。現在它的G 值為20 ，並且指向它正上方的方格。這是由於在尋路過程中的某處使用新路徑時G值更小，因此父節點被重新設置，G和F值被重新計算。

那麼我們怎樣得到實際路徑呢？很簡單，如下圖所示，從終點開始，沿著箭頭向父節點移動，直至回到起點，這就是你的路徑。

A*演算法總結：

1. 把起點加入 open list 。

2. 重復如下過程：

a. 遍歷open list ，查找F值最小的節點，把它作為當前要處理的節點，然後移到close list中

b. 對當前方格的 8 個相鄰方格一一進行檢查，如果它是不可抵達的或者它在close list中，忽略它。否則，做如下操作：

□  如果它不在open list中，把它加入open list，並且把當前方格設置為它的父親

□  如果它已經在open list中，檢查這條路徑 ( 即經由當前方格到達它那裡 ) 是否更近。如果更近，把它的父親設置為當前方格，並重新計算它的G和F值。如果你的open list是按F值排序的話，改變後你可能需要重新排序。

c. 遇到下面情況停止搜索：

□  把終點加入到了 open list 中，此時路徑已經找到了，或者

□  查找終點失敗，並且open list 是空的，此時沒有路徑。

3. 從終點開始，每個方格沿著父節點移動直至起點，形成路徑。

H. A*演算法的演算法分類

該演算法在最短路徑搜索演算法中分類為
直接搜索演算法：直接在實際地圖上進行搜索，不經過任何預處理
啟發式演算法：通過啟發函數引導演算法的搜索方向
靜態圖搜索演算法：被搜索的圖的權值不隨時間變化（後被證明同樣可以適用於動態圖的搜索 ）

I. 使用A*演算法解決路徑優化問題 必須需要編寫程序嗎 如果需要編寫的話使用什麼軟體呢

這是一種演算法
使用各種編程語言都可以做的
你選擇自己擅長的語言跟工具就行了