a演算法怎麼實現方向性誘導

㈠ A*演算法java實現

首先，你要知道走迷宮的思路：就是遇到岔路都往一個方向，比如往右，遇到死路就回頭，回頭遇到岔路繼續往右。
線法線在同一平面上，反射光線與入射光線分

㈡ a*演算法裡面哪種啟發式函數的導航效果最好

A*演算法本身是很簡單的，因此原文中並沒有過多地討論A*演算法本身，而是花了較大的篇幅討論了用於保存OPEN和CLOSED集的數據結構，以及A*演算法的變種和擴展。

編程實現A*是簡單的，讀者可以用STL對本文中的偽代碼加以實現（本人已花一天時間實驗過基本的A*搜索）。但是最重要的還是對A*本身的理解，這樣才可以在自己的游戲中處理各種千變萬化的情況。

㈢ A*演算法的原理

A* （A-Star)演算法是一種靜態路網中求解最短路最有效的直接搜索方法。
注意是最有效的直接搜索演算法。之後涌現了很多預處理演算法（ALT，CH，HL等等），在線查詢效率是A*演算法的數千甚至上萬倍。
公式表示為： f(n)=g(n)+h(n),
其中 f(n) 是從初始點經由節點n到目標點的估價函數，
g(n) 是在狀態空間中從初始節點到n節點的實際代價，
h(n) 是從n到目標節點最佳路徑的估計代價。
保證找到最短路徑（最優解的）條件，關鍵在於估價函數f(n)的選取：
估價值h(n)<= n到目標節點的距離實際值，這種情況下，搜索的點數多，搜索范圍大，效率低。但能得到最優解。並且如果h(n)=d(n)，即距離估計h(n)等於最短距離，那麼搜索將嚴格沿著最短路徑進行， 此時的搜索效率是最高的。
如果 估價值>實際值,搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解。

㈣ 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);}

㈤ A*演算法的介紹

A*演算法；A*（A-Star)演算法是一種靜態路網中求解最短路徑最有效的直接搜索方法。估價值與實際值越接近，估價函數取得就越好。

㈥ 什麼是 a演算法a* 演算法有什麼特點

A*演算法：A*（A-Star)演算法是一種靜態路網中求解最短路徑最有效的直接搜索方法。估價值與實際值越接近，估價函數取得就越好
A* （A-Star)演算法是一種靜態路網中求解最短路最有效的直接搜索方法。
注意是最有效的直接搜索演算法。之後涌現了很多預處理演算法（ALT，CH，HL等等），在線查詢效率是A*演算法的數千甚至上萬倍。
公式表示為： f(n)=g(n)+h(n),
其中 f(n) 是從初始點經由節點n到目標點的估價函數，
g(n) 是在狀態空間中從初始節點到n節點的實際代價，
h(n) 是從n到目標節點最佳路徑的估計代價。
保證找到最短路徑（最優解的）條件，關鍵在於估價函數f(n)的選取：
估價值h(n)<= n到目標節點的距離實際值，這種情況下，搜索的點數多，搜索范圍大，效率低。但能得到最優解。並且如果h(n)=d(n)，即距離估計h(n)等於最短距離，那麼搜索將嚴格沿著最短路徑進行， 此時的搜索效率是最高的。
如果 估價值>實際值,搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解。

㈦ A*演算法的演算法分類

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

㈧ A*演算法是什麼

A*
（A-Star)演算法是一種靜態路網中求解最短路最有效的方法。
公式表示為： f(n)=g(n)+h(n),
其中f(n) 是從初始點經由節點n到目標點的估價函數，
g(n) 是在狀態空間中從初始節點到n節點的實際代價，
h(n)是從n到目標節點最佳路徑的估計代價。
保證找到最短路徑（最優解的）條件，關鍵在於估價函數h(n)的選取：
估價值h(n)<= n到目標節點的距離實際值，這種情況下，搜索的點數多，搜索范圍大，效率低。但能得到最優解。
如果 估價值>實際值, 搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解

㈨ A*演算法的問題

演算法沒有錯。只是考慮到所有可能的情況。
如果x出現在close集中，並且新的估價小於原有估價，說明還存在另一條經過x到達目標並且更快捷路徑是之前沒有搜索到的。這時當然要重新把x放回open集中統一考慮。
依你所講，大概你是在方格棋盤類的路徑搜索。則上述情況不會出現，因為方格棋盤構造出的圖很規則。但如果是在某一非常奇怪的圖上，比如兩行星之間有個蟲洞，經過後可以使時間倒流時（哈哈，暫時只想到這樣一個奇怪的例子），則很有可能出現上述情況。
所以，不是演算法誰對誰錯，而是在不同問題中做法不一樣。網路給出的演算法考慮情況更全面。

㈩ 有關A* 尋路演算法。 看了這個演算法 大致都明白。就是有點不大清楚。

1. B的G值是指從起點A開始，到達該點的最短距離，和B在不在最短路徑上沒有關系。

2. 不是遍歷所有路徑，而是所有點。對於m*n的矩陣， 遍歷所有點的復雜度是m*n（多項式復雜度），而遍歷所有路徑的復雜度是4的(m*n)次冪(每個點都有4個可能的方向)。從冪指數復雜度降低到多項式復雜度，這就是A*演算法的意義所在。

3. 最優路徑是要從終點一步步倒退回來。比如終點的G值是k，那麼最多需要4*k次查找，依然是多項式復雜度。但多數問題(對於純演算法題來說)只是需要知道到達終點的步驟，很少要你找出固定路徑的。