a演算法實現

Ⅰ 如何在使用Cocos2D中實現A星（A*）尋路演算法

實現A星演算法
根據演算法，第一步是添加當前坐標到open列表。還需要三個輔助方法：
- 一個方法用來插入一個ShortestPathStep對象到適當的位置（有序的F值）
- 一個方法用來計算從一個方塊到相鄰方塊的移動數值
- 一個方法是根據"曼哈頓距離"演算法，計算方塊的H值。
ssize_t CatSprite::getStepIndex(const cocos2d::Vector<CatSprite::ShortestPathStep *> &steps, const CatSprite::ShortestPathStep *step)
{
for (ssize_t i = 0; i < steps.size(); ++i)
{
if (steps.at(i)->isEqual(step))
{
return i;
}
}
return -1;
}

Ⅱ A*搜尋演算法的代碼實現(C語言實現)

用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;//地圖坐標X graph[i][j].y=j;//地圖坐標Y graph[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(){ //ClearMapMarksofSteps Close*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*演算法的實現要簡單一些:即使不檢查closed節點的狀態重復,也能得到最優的結果

下面是證明最優性的一些關鍵點:

1 沿著任何路徑的fn都是非遞減的

2 closed集合裡面的任何一個節點的fn都要小於open集合裡面的任何一個節點的fn,這個特點保證了在拓展open節點時可以跳過已經在closed節點中的節點

3 目標點的fn=gn+0,如果有路徑到達目標點,那麼所有能到達目標點的路徑都在open表裡面,而且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)等於最短距離，那麼搜索將嚴格沿著最短路徑進行， 此時的搜索效率是最高的。
如果 估價值>實際值,搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解。

Ⅳ 如何用Swift實現A*尋路演算法

A*演算法
?? 啟發式搜索
– 在搜索中涉及到三個函數
?? g(n) = 從初始結點到結點n的耗費
?? h(n) = 從結點n到目的結點的耗費評估值，啟發函數
?? f(n)=g(n)+h(n) 從起始點到目的點的最佳評估值
– 每次都選擇f(n)值最小的結點作為下一個結點，
直到最終達到目的結點
– A*演算法的成功很大程度依賴於h(n)函數的構建
?? 在各種游戲中廣泛應用 Open列表和Closed列表
– Open列表
?? 包含我們還沒有處理到的結點
?? 我們最開始將起始結點放入到Open列表中
– Closed列表
?? 包含我們已經處理過的結點
?? 在演算法啟動時，Closed列表為空 A* 演算法偽代碼初始化OPEN列表
初始化CLOSED列表
創建目的結點；稱為node_goal
創建起始結點；稱為node_start
將node_start添加到OPEN列表
while OPEN列表非空{
從OPEN列表中取出f(n)值最低的結點n
將結點n添加到CLOSED列表中
if 結點n與node_goal相等then 我們找到了路徑，程序返回n
else 生成結點n的每一個後繼結點n'
foreach 結點n的後繼結點n'{
將n』的父結點設置為n
計算啟發式評估函數h(n『)值，評估從n『到node_goal的費用
計算g(n『) = g(n) + 從n』到n的開銷
計算f(n') = g(n') + h(n')
if n『位於OPEN或者CLOSED列表and 現有f(n)較優then丟棄n』 ，處理後繼n』
將結點n『從OPEN和CLOSED中刪除
添加結點n『到OPEN列表
}
}
return failure （我們已經搜索了所有的結點，但是仍然沒有找到一條路徑）

Ⅵ A*演算法詳解

我們討論一個移動機器人遇到問題：如何移動到指定位置

這里討論的是路徑規劃問題。而A*演算法是廣為使用的解決這個問題的演算法。

如圖1，綠色點為start設為A，紅色點為goal設為B，藍色點為不可通過的障礙物，黑色點為自由區域。目標是規劃從A到B的路徑。

對相鄰點，一次計算每一點的g_score，h_score，最後得到f_score。如圖3，節點的右下角為g_score值，左下角為h_score值，右上角為f_score。

Ⅶ A*演算法（啟發式演算法）

A*演算法
這是我寫的第一篇有關A*演算法的文章，寫得比較簡潔，我決定再寫一篇，補充一下對A*演算法的理解。

A*演算法把 Dijkstra演算法 （靠近初始點的結點）和 BFS演算法 （靠近目標點的結點）的信息塊結合起來。
g(n)表示從初始結點到任意結點n的實際代價
h(n)表示從結點n到目標點的啟發式評估代價

（1）h(n)=0，一種極端情況
如果h(n)=0，則只有g(n)起作用，此時A*演變成Dijkstra演算法，這保證能找到最短路徑，但效率不到，因為得不到啟發。
（2）h(n)<實際代價
如果h(n)經常都比從n移動到目標的實際代價小（或者相等），則A*保證能找到一條最短路徑。h(n)越小，A*擴展的結點越多，運行就越慢。
（3）h(n)=實際代價
如果h(n)精確地等於從n移動到目標的實際代價，則A*將會僅僅尋找最佳路徑而不擴展別的任何結點，這會運行得非常快。盡管這不可能在所有情況下發生，你仍可以在一些特殊情況下讓它們精確地相等（指讓h(n)精確地等於實際代價）。只要提供完美的信息，A*就會運行得很完美。
（4）h(n)>實際代價
如果h(n)有時比從n移動到目標的實際代價大，則A*不能保證找到一條最短路徑，但它運行得更快。
（5）h(n)>>實際代價（>>遠大於），另一種極端情況
如果h(n)比g(n)大很多，則只有h(n)起作用，A*演變成BFS演算法。

數組？鏈表？
在Open集上主要有三種操作：查找優先順序最高的結點&刪除結點、查找相鄰結點是否在集合中、插入新結點
在Close集上主要有兩種操作：查找相鄰結點是否在集合中、插入新節點
（1）未排序數組或鏈表
最簡單的數據結構是未排序數組或鏈表。查找結點，花費O(N)；插入結點，花費O(1)；刪除結點，花費O(N)
（2）排序數組
為了加快刪除操作，可以對數組進行排序。查找結點，變成O(logN)，因為可以使用折半查找；插入結點，花費O(N)；查找和刪除優先順序最高的結點，花費O(1)
（3）排序鏈表
在排序數組中，插入操作很慢。如果使用鏈表則可以加速該操作。查找結點，花費O(N)；插入結點，花費O(1)，但查找插入位置，需要花費O(N)
（4）哈希表
使用哈希表，查找結點，花費O(1)；插入結點，花費O(1)；查找和刪除優先順序最高的結點，花費O(N)

https://blog.csdn.net/coutamg/article/details/53923717#!/_alzvzu0wsphb4nstr5bbro1or

Ⅷ C++ A* 演算法實現中，怎樣便捷地實現「搜索節點在OPEN表和CLOSED表之間 切換」

你是在用A*演算法做八數碼問題么。

比如你要在open表中刪除一個節點，然後放到close表中，你可以反過來做，

先找到這個結點，在close表中插入，然後再在open表中刪除

我把我寫的windows下的代碼貼過來你看看，順便說一句，open表和close表都要經常做刪除節點的操作，所以用vector（線性表）其實性能不好，我用的List。