astar演算法的優缺點

『壹』 機器人避障問題： astar演算法與神經網路有關嗎

不一樣的 a星方法是利用兩段評價進行路徑尋找 對於障礙的處理 需要進行改進 所以有人用人工勢場處理障礙問題

『貳』 廣度優先演算法的優化——A*演算法問題

英文叫 a-star 中文叫a星
我以前見過用astar演算法求解這類問題的論文
你在上搜索一下 「A星演算法」有這方面的解釋

『叄』 unity烘焙後可以自己實現尋路嗎

可以
但最初的Unity導航系統很不完善，只能靜態烘焙場景圖的可行走區域 而且必須在本地保存場景的NavMesh數據，難以運行時動態計算；這使得鮮有開發者願意再嘗試Unity內置的導航功能，轉向了AStar尋路演算法的研究。需要使用組件實現動態自動烘培

『肆』 求一個A*演算法的C語言或C++代碼，小弟不勝感激，謝謝

1#include <iostream>
2#include <queue>
3usingnamespace std;
4
5struct knight{
6int x,y,step;
7int g,h,f;
8booloperator< (const knight & k) const{ //重載比較運算符
9return f > k.f;
10 }
11}k;
12bool visited[8][8]; //已訪問標記(關閉列表)
13int x1,y1,x2,y2,ans; //起點(x1,y1),終點(x2,y2),最少移動次數ans
14int dirs[8][2]={{-2,-1},{-2,1},{2,-1},{2,1},{-1,-2},{-1,2},{1,-2},{1,2}};//8個移動方向
15priority_queue<knight> que; //最小優先順序隊列(開啟列表)
16
17boolin(const knight & a){ //判斷knight是否在棋盤內
18if(a.x<0|| a.y<0|| a.x>=8|| a.y>=8)
19returnfalse;
20returntrue;
21}
22int Heuristic(const knight &a){ //manhattan估價函數
23return (abs(a.x-x2)+abs(a.y-y2))*10;
24}
25void Astar(){ //A*演算法
26 knight t,s;
27while(!que.empty()){
28 t=que.top(),que.pop(),visited[t.x][t.y]=true;
29if(t.x==x2 && t.y==y2){
30 ans=t.step;
31break;
32 }
33for(int i=0;i<8;i++){
34 s.x=t.x+dirs[i][0],s.y=t.y+dirs[i][1];
35if(in(s) &&!visited[s.x][s.y]){
36 s.g = t.g +23; //23表示根號5乘以10再取其ceil
37 s.h = Heuristic(s);
38 s.f = s.g + s.h;
39 s.step = t.step +1;
40 que.push(s);
41 }
42 }
43 }
44}
45int main(){
46char line[5];
47while(gets(line)){
48 x1=line[0]-'a',y1=line[1]-'1',x2=line[3]-'a',y2=line[4]-'1';
49 memset(visited,false,sizeof(visited));
50 k.x=x1,k.y=y1,k.g=k.step=0,k.h=Heuristic(k),k.f=k.g+k.h;
51while(!que.empty()) que.pop();
52 que.push(k);
53 Astar();
54 printf("To get from %c%c to %c%c takes %d knight moves.\n",line[0],line[1],line[3],line[4],ans);
55 }
56return0;
57}
58

『伍』 astar安卓版怎麼用

最近因為跨國問題中國大陸版禁用中也就是無法使用。
如果你想要使用，你可以從官網上下載的插件解壓後打開Chrome的擴展管理（我用的是Chrome，打開上方一個打開已解壓的擴展程序」然後點你的解壓的astar就ok了。
AStar演算法是一種靜態路網中求解最短路徑最有效的直接搜索方法。在包含各種障礙物的地圖中，為游戲角色的移動，尋找一條到目標地點最短路徑。

『陸』 問： 40 人工智慧及其應用期末作業 用A*演算法解決下面的八數碼難題。試定義估價函數，啟發函數，

#pragma warning(disable:4786)
#include <algorithm>
#include <cstdio>
#include <set>
#include <utility>
#include <ctime>
#include <cassert>
#include <cstring>
#include <iostream>
using namespace std;

/*item記錄搜索空間中一個結點
state 記錄用整數形式表示的8數碼格局
blank 記錄當前空格位置，主要用於程序優化，
擴展時可不必在尋找空格位置
g, h 對應g(n), h(n)
pre 記錄當前結點由哪個結點擴展而來 */
struct item
{
int state;
int blank;
int g;
int h;
int pre;
};

const int MAXSTEPS = 100000;
const int MAXCHAR = 100;
char buf[MAXCHAR][MAXCHAR]; //open表
item open[MAXSTEPS];
//vector<item> open;
int steps = 0;

//closed表，已查詢狀態只要知道該狀態以及它由哪個結點擴展而來即可，用於輸出路徑
//每次只需得到對應f值最小的待擴展結點，用堆實現提高效率
pair<int, int> closed[MAXSTEPS];
//讀入，將8數碼矩陣格局轉換為整數表示

bool read(pair<int,int> &state)
{
if (!gets(buf[0]))
return false;
if (!gets(buf[1]))
return false;
if (!gets(buf[2]))
return false;

//cout << strlen(buf[0]) << ' ' << strlen(buf[1]) << ' ' << strlen(buf[2]) << endl;
assert(strlen(buf[0]) == 5 && strlen(buf[1]) == 5 && strlen(buf[2]) == 5);
// astar.in中的每行數據長度必須為5
state.first = 0;
for (int i = 0, p = 1; i < 3; ++i)
{
for (int j = 0; j < 6; j += 2)
{
if (buf[i][j] == '0')
state.second = i * 3 + j / 2; // state.second為0（空格）在節點中的位置
else
state.first += p * (buf[i][j] - '0');
p *= 10;
}
}

/* 若初試節點為:
1 2 3
8 0 4
7 6 5
則state.first為567408321，state.second為4
*/
return true;
}

//計算當前結點距目標的距離
int calculate(int current, int target) // return h=the sum of distances each block have to move to the right position,這里的each block不包括空格
{
int c[9], t[9];
int i, cnt = 0;
for (i = 0; i < 9; ++i)
{
c[current % 10] = t[target % 10] = i;
current /= 10;
target /= 10;
}

for (i = 1; i < 9; ++i)
cnt += abs(c[i] / 3 - t[i] / 3) + abs(c[i] % 3 - t[i] % 3);

return cnt;
}

//open表中結點間選擇時的規則 f(n) = g(n) + h(n)

class cmp
{
public: inline bool operator()(item a, item b)
{
return a.g + a.h > b.g + b.h;
}
};

//將整數形式表示轉換為矩陣表示輸出
void pr(int state)
{
memset(buf, ' ', sizeof(buf));
for (int i = 0; i < 3; ++i)
{
for (int j = 0; j < 6; j += 2)
{
if (state % 10)
buf[i][j] = state % 10 + '0';
state /= 10;
}

buf[i][5] = '\0';
puts(buf[i]);
}
}

//用於判斷當前空格是否可以向對應方向移動
inline bool suit(int a, int b) //空格移動後的坐標為(a,b)
{
return (a >= 0 && a < 3 && b >= 0 && b < 3);
}

//遞歸輸出搜索路徑
void path(int index)
{
if (index == 0)
{
pr(closed[index].first);
puts("");
return;
}
path(closed[index].second);
pr(closed[index].first); //將整數形式表示轉換為矩陣表示輸出
puts("");
++steps;
}

int getNixuNum( int state ) //求節點的逆序對數
{
int sum = 0;
int result[9];
memset( result, 0, sizeof(result) );
//cout << result[8] << result[7] << endl;

char buf[10];
itoa( state, buf, 10 );
//cout << buf << endl;
int k = 0;
while( buf[k] != '\0' )
{
result[9-k-1] = buf[k] - '0';
k++;
}

for( int i = 0; i < 9; i++ )
{
for( int j = i + 1; j < 9; j++ )
{
if( result[i] && result[j] && result[i] > result[j] )
{
sum++;
}
}
}
return sum; //返回3*3方格數組的逆序對數
}

int main()
{
//cout << getNixuNum(87654321);
//open.resize(MAXSTEPS);
unsigned int t1 = clock();
//cout << open.size() << endl;
if( freopen("astar.in", "r", stdin) == NULL )
{
cout << "file not find\n";
exit(0);
};

freopen("astar2.out", "w", stdout);
set<int>states;
char tmp[100];
int i, x, y, a, b, nx, ny, end, next, index, kase = 0;
pair<int,int> start, target;
item head; //4個方向移動時的偏移量
const int xtran[4] = {-1, 0, 1, 0};
const int ytran[4] = {0, 1, 0, -1};
const int p[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};

while (read(start)) // 讀取初試狀態節點
{
unsigned int t2 = clock();
printf("Case %d:\n\n", ++kase);
gets(tmp);
read(target); // 讀取目標狀態節點
gets(tmp);

int targetNixuNum = getNixuNum(target.first);
//若兩者的逆序對數不是同為奇數或同為偶數，則無解
if( !(getNixuNum(start.first)&1 && targetNixuNum&1 || !(getNixuNum(start.first)&1) && !(targetNixuNum&1)) )
{
cout << "無法從初始節點到終態節點\n";
exit(0);
}
//初始化open表，將初始狀態加入
open[0].state = start.first;
open[0].h = calculate(start.first, target.first); // 計算當前節點到目標節點的估計距離
open[0].blank = start.second;
open[0].pre = -1; // 初始節點無父節點
open[0].g = 0; // 初始節點的g為0
index = 0;
states.insert(start.first); // 擴展過節點保存在states中，即出現過的狀態保存在states中，states為set<int>類型，其中的states中的元素唯一

//提取open表中f值最小元素放入closed表，並對該結點進行擴展
for (end = 1; end > 0; ++index) // end為open表中的元素個數，一直循環到open表為空
{
assert(index < MAXSTEPS);
//臨時存儲
head = open[0]; // 由於使用pop_heap函數和push_heap函數，所以open[0]為g+h最小的元素

//放入closed表記錄當前格局和由哪個結點擴展而來（該結點肯定已在closed表中）
closed[index].first = open[0].state; //放入close表中，表示已經擴展完的節點，下面的for循環會擴展其節點
closed[index].second = open[0].pre; // index表示當前close表中當前擴展節點的下標
//從open表中刪除該結點
pop_heap(open, open + end, cmp());//為algorithm文件中的函數，第一個參數指定開始位置，第二個指定結束，第三個指定比較函數
--end;

//得到結果，遞歸輸出路徑
if (head.state == target.first)
{
path(index);
break;
}

x = head.blank / 3;
y = head.blank % 3; //空格在3*3方格中的x,y坐標
/*
|2 0 3|
A = |1 8 4|
|7 6 5| // 看成3*3的數組
則head.blank=1
x=0,y=1,即空格的在3*3的數組中下標為(0,1)
*/
for (i = 0; i < 4; ++i)
{
nx = x + xtran[i];
ny = y + ytran[i];
/*
i=0時：(nx,ny）為當前空格向上移動一格後的坐標
i=1時：(nx,ny）為當前空格向右移動一格後的坐標
i=2時：(nx,ny）為當前空格向下移動一格後的坐標
i=3時：(nx,ny）為當前空格向左移動一格後的坐標
*/
if (suit(nx, ny)) // 判斷是否能夠移動
{
a = head.blank; // 空格當前位置,以上面矩陣A為例，a=1
b = nx * 3 + ny; // 空格移動後的新位置,開始是能夠向右邊移動，故b=0*3+2=2
//調換十進製表示整數對應兩個數字位
next = head.state + ((head.state % p[a + 1]) / p[a] - (head.state % p[b + 1]) / p[b]) * p[b] + ((head.state % p[b + 1]) / p[b] - (head.state % p[a + 1]) / p[a]) * p[a];
// 如head.state=567481302,空格向右移動一次後，next=567481032,即為移動後的節點

// 判斷能否由當前節點到達目標節點
if( ( getNixuNum(next)&1 && targetNixuNum&1 ) || ( !(getNixuNum(next)&1) && !(targetNixuNum&1) ) )
{
//判斷是否已經擴展過，即已經出現過
if (states.find(next) == states.end()) //沒出現就保存一下，也存入open表
{
states.insert(next);
open[end].pre = index; //擴展後的子節點，其父節點為當前擴展節點
open[end].blank = b;
open[end].state = next;
open[end].h = calculate(next,target.first);
open[end].g = head.g + 1;
++end; //open表中元素加1
push_heap(open, open + end, cmp()); //壓入堆中
}
}

}
}
}

if (end <= 0)
puts("No solution");
else
{
printf("Num of steps: %d\n", steps);
printf("Num of expanded: %d\n", index);
printf("Num of generated: %d\n", index + end);
printf("Time consumed: %d\n\n", clock() - t2);
}

states.clear();
steps = 0;
}
printf("Total time consumed: %d\n", clock() - t1);
return 0;
}

『柒』 Java 鏈表節點值問題

包com.link;公共類節點 {

/ /前一個節點

私營節點上一頁;/ /後一個節點

私營節點未來;

/ /值

私人的T值;公共節點（）{

超（）;

}公共節點（節點預防和控制，節點接下來，T值）{

超（）;

this.prev =上一頁;

this.next =未來;

THIS.VALUE =值;

}公共節點的GetNext（）{

未來的回報;

}公共無效setNext（節點旁邊）{

this.next =未來;

}公共節點 getPrev（）{

返回上級;

}公共無效setPrev（節點先前）{

this.prev =上一頁;

}公共牛逼的getValue（）{

返回值;

}公共無效的setValue（T值）{

THIS.VALUE =值;

/ /如果有一個節點或下一個節點

公共布爾的hasNext（）{

如果（！this.next = NULL）返回true;

返回false;

公共布爾hasPrev（）{

如果（this.prev = NULL！）返回true;

返回false;

------------------------------------ ----包com.link;公共類鏈表 {

/ /頭節點

私營節點頭;

/ /構造函數

公眾鏈表（）{

頭=新的Node （NULL，NULL，NULL）;

公共無效添加（T T）{

節點溫度=頭;

而{

溫度= temp.getNext（）（溫度的hasNext（））;

temp.setNext（新節點（溫度，空，T））;

私營節點發現（T T）{

如果（T == NULL）返回NULL; （！head.hasNext（））

如果返回NULL; 節點溫度=頭;

而（temp.hasNext（））{

溫度= temp.getNext（）;

如果（t.equals（temp.getValue（）））{

返回溫度;

返回NULL;

公共布爾hasValue的（T T）{如果（發現（T）=空！）返回true;

返回false;

公共布爾刪除（T T）{

節點溫度=發現（T）;

如果（temp! = NULL）{

temp.getNext（）setPrev（temp.getPrev（））;。

temp.getPrev（）。 setNext（temp.getNext（））;

溫度= NULL;

返回true;

返回false;

/ /取一個節點通過索引

公眾噸得到（INT指數）{

如果返回空值（head.hasNext（）！）;

節點溫度=頭;

INT I = 0;

為（我「=指數&& temp.hasNext（）; i + +）{

溫度= temp.getNext（）;

}

如（i ==指數+1）返回temp.getValue（）;

返回NULL;

}公共靜態無效的主要（字串[] args）{

LINKLIST 列表=新LINKLIST （）;

為（int i = 0; I <20; i + +）{

將對List.Add（「字元串」+ I）;

/ /以下只列印顯示的結果，所以一般情況下不會列印

節點溫度= list.head;

INT I = 0;

而（temp.hasNext（））{

溫度= temp.getNext（）;

System.out.println（「值」+ I +「：」+ temp.getValue（））;

i + +;

如果（list.remove（「String10」））{

System.out.println（「成功」）;

}其他{

系統。通過out.println（「否」）;

溫度= list.head;

I = 0;

而（temp.hasNext（））{

溫度= temp.getNext（）;

System.out.println（「值」+ I +「：」+ temp.getValue（））; i + +;
}

『捌』 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);}

『玖』 求八數碼問題演算法，並說明下該演算法優缺點，要演算法，不是源代碼（可以沒有）。

八數碼問題

一.八數碼問題
八數碼問題也稱為九宮問題。在3×3的棋盤，擺有八個棋子，每個棋子上標有1至8的某一數字，不同棋子上標的數字不相同。棋盤上還有一個空格，與空格相鄰的棋子可以移到空格中。要求解決的問題是：給出一個初始狀態和一個目標狀態，找出一種從初始轉變成目標狀態的移動棋子步數最少的移動步驟。所謂問題的一個狀態就是棋子在棋盤上的一種擺法。棋子移動後，狀態就會發生改變。解八數碼問題實際上就是找出從初始狀態到達目標狀態所經過的一系列中間過渡狀態。
八數碼問題一般使用搜索法來解。搜索法有廣度優先搜索法、深度優先搜索法、A*演算法等。這里通過用不同方法解八數碼問題來比較一下不同搜索法的效果。

二.搜索演算法基類
1.八數碼問題的狀態表示
八數碼問題的一個狀態就是八個數字在棋盤上的一種放法。每個棋子用它上面所標的數字表示，並用0表示空格，這樣就可以將棋盤上棋子的一個狀態存儲在一個一維數組p[9]中，存儲的順序是從左上角開始，自左至右，從上到下。也可以用一個二維數組來存放。
2.結點
搜索演算法中，問題的狀態用結點描述。結點中除了描述狀態的數組p[9]外，還有一個父結點指針last，它記錄了當前結點的父結點編號，如果一個結點v是從結點u經狀態變化而產生的，則結點u就是結點v的父結點，結點v的last記錄的就是結點u的編號。在到達目標結點後，通過last 可以找出搜索的路徑。
3.類的結構
在C++中用類來表示結點，類將結點有關的數據操作封裝在一起。
不同的搜索演算法具有一定共性，也有各自的個性，因此這里將不同搜索演算法的共有的數據和功能封裝在一個基類中，再通過繼承方式實現不同的搜索演算法。
4.結點擴展規則
搜索就是按照一定規則擴展已知結點，直到找到目標結點或所有結點都不能擴展為止。
八數碼問題的結點擴展應當遵守棋子的移動規則。按照棋子移動的規則，每一次可以將一個與空格相鄰棋子移動到空格中，實際上可以看作是空格作相反移動。空格移動的方向可以是右、下、左、上，當然不能移出邊界。棋子的位置，也就是保存狀態的數組元素的下標。空格移動後，它的位置發生變化，在不移出界時，空格向右、下、左和上移動後，新位置是原位置分別加上1、3、-1、-3，如果將空格向右、下、左和上移動分別用0、1、2、3表示，並將-3、3、-1、1放在靜態數組d[4]中，空格位置用spac表示，那麼空格向方向i移動後，它的位置變為spac+d[i]。空格移動所產生的狀態變化，反映出來則是將數組p[]中，0的新位置處的數與0交換位置。
5.八數碼問題的基類

八數碼問題的基類及其成員函數的實現如下：
#define Num 9
class TEight
{
public:
TEight(){}
TEight(char *fname); //用文件數據構造節點
virtual void Search()=0; //搜索
protected:
int p[Num];
int last,spac;
static int q[Num],d[],total;
void Printf();
bool operator==(const TEight &T);
bool Extend(int i);
};
int TEight::q[Num];//儲存目標節點
int TEight::d[]={1,3,-1,-3};//方向
int TEight::total=0;//步數

TEight::TEight(char *fname)
{
ifstream fin;
fin.open(fname,ios::in);
if(!fin)
{
cout<<"不能打開數據文件!"<<endl;
return;
}
int i;
for(i=0;i<Num;)//得到源節點
fin>>p[i++];
fin>>spac;
for(i=0;i<Num;)//得到目標節點
fin>>q[i++];
fin.close();
last=-1;
total=0;
}

void TEight::Printf()//把路徑列印到結果文件
{
ofstream fout;
fout.open("eight_result.txt",ios::ate|ios::app);
fout<<total++<<"t";
for(int i=0;i<Num;)
fout<<" "<<p[i++];
fout<<endl;
fout.close();
}

bool TEight::operator==(const TEight &T)//判斷兩個狀態是否相同
{
for(int i=0;i<Num;)
if(T.p[i]!=p[i++])
return 0;
return 1;
}

bool TEight::Extend(int i)//擴展
{
if(i==0 && spac%3==2 || i==1 && spac>5
|| i==2 && spac%3==0 || i==3 && spac<3)
return 0;
int temp=spac;
spac+=d[i];
p[temp]=p[spac];
p[spac]=0;
return 1;
}

數據文件的結構：
一共三行，第一行是用空格隔開的九個數字0~8，這是初始狀態。第二行是一個數字，空格（數字0）的位置，第三行也是用空格隔開的九個數字0~8，這是目標狀態。

三.線性表
搜索法在搜索過程中，需要使用一個隊列存儲搜索的中間結點，為了在找到目標結點後，能夠找到從初始結點到目標結點的路徑，需要保留所有搜索過的結點。另一方面，不同問題甚至同一問題的不同搜索方法中，需要存儲的結點數量相差很大，所以這里採用鏈式線性表作為存儲結構，同時，為適應不同問題，線性表設計成類模板形式。
template<class Type> class TList; //線性表前視定義

template<class Type> class TNode //線性表結點類模板
{
friend class TList<Type>;
public:
TNode(){}
TNode(const Type& dat);
private:
TNode<Type>* Next;
Type Data;
};

template<class Type> class TList
{
public:
TList(){Last=First=0;Length=0;} //構造函數
int Getlen()const{return Length;} //成員函數，返回線性表長度
int Append(const Type& T); //成員函數，從表尾加入結點
int Insert(const Type& T,int k); //成員函數，插入結點
Type GetData(int i); //成員函數，返回結點數據成員
void SetData(const Type& T,int k); //成員函數，設置結點數據成員
private:
TNode<Type> *First,*Last; //數據成員，線性表首、尾指針
int Length; //數據成員，線性表長度
};

template<class Type> int TList<Type>::Append(const Type& T)
{
Insert(T,Length);
return 1;
}

template<class Type> int TList<Type>::Insert(const Type& T,int k)
{
TNode<Type> *p=new TNode<Type>;
p->Data=T;
if(First)
{
if(k<=0)
{
p->Next=First;
First=p;
}
if(k>Length-1)
{
Last->Next=p;
Last=Last->Next;
Last->Next=0;
}
if(k>0 && k<Length)
{
k--;
TNode<Type> *q=First;
while(k-->0)
q=q->Next;
p->Next=q->Next;
q->Next=p;
}
}
else
{
First=Last=p;
First->Next=Last->Next=0;
}
Length++;
return 1;
}

template<class Type> Type TList<Type>::GetData(int k)
{
TNode<Type> *p=First;
while(k-->0)
p=p->Next;
return p->Data;
}

template<class Type> void TList<Type>::SetData(const Type& T,int k)
{
TNode<Type> *p=First;
while(k-->0)
p=p->Next;
p->Data=T;
}
線性表單獨以頭文件形式存放。

四.廣度優先搜索法
在搜索法中，廣度優先搜索法是尋找最短路經的首選。
1.廣度優先搜索演算法的基本步驟
1）建立一個隊列，將初始結點入隊，並設置隊列頭和尾指針
2）取出隊列頭（頭指針所指）的結點進行擴展，從它擴展出子結點，並將這些結點按擴展的順序加入隊列。
3）如果擴展出的新結點與隊列中的結點重復，則拋棄新結點，跳至第六步。
4）如果擴展出的新結點與隊列中的結點不重復，則記錄其父結點，並將它加入隊列，更新隊列尾指針。
5）如果擴展出的結點是目標結點，則輸出路徑，程序結束。否則繼續下一步。
6）如果隊列頭的結點還可以擴展，直接返回第二步。否則將隊列頭指針指向下一結點，再返回第二步。
2.搜索路徑的輸出
搜索到目標結點後，需要輸出搜索的路徑。每個結點有一個數據域last，它記錄了結點的父結點，因此輸出搜索路徑時，就是從目標結點Q出發，根據last找到它的父結點，再根據這個結點的last找到它的父結點，....,最後找到初始結點。搜索的路徑就是從初始結點循相反方向到達目標結點的路徑。
3.廣度優先搜索法TBFS類的結構
廣度優先搜索法TBFS類是作為TEight類的一個子類。其類的結構和成員函數的實現如下：
class TBFS:public TEight
{
public:
TBFS(){}
TBFS(char *fname):TEight(fname){}
virtual void Search();
private:
void Printl(TList<TBFS> &L);
int Repeat(TList<TBFS> &L);
int Find();
};

void TBFS::Printl(TList<TBFS> &L)
{
TBFS T=*this;
if(T.last==-1)
return;
else
{
T=L.GetData(T.last);
T.Printl(L);
T.Printf();
}
}

int TBFS::Repeat(TList<TBFS> &L)
{
int n=L.Getlen();
int i;
for(i=0;i<n;i++)
if(L.GetData(i)==*this)
break;
return i;
}

int TBFS::Find()
{
for(int i=0;i<Num;)
if(p[i]!=q[i++])
return 0;
return 1;
}

void TBFS::Search()
{
TBFS T=*this;
TList<TBFS> L;
L.Append(T);
int head=0,tail=0;
while(head<=tail)
{
for(int i=0;i<4;i++)
{
T=L.GetData(head);
if(T.Extend(i) && T.Repeat(L)>tail)
{
T.last=head;
L.Append(T);
tail++;
}
if(T.Find())
{
T.Printl(L);
T.Printf();
return;
}
}
head++;
}
}
4.廣度優先搜索法的缺點
廣度優先搜索法在有解的情形總能保證搜索到最短路經，也就是移動最少步數的路徑。但廣度優先搜索法的最大問題在於搜索的結點數量太多，因為在廣度優先搜索法中，每一個可能擴展出的結點都是搜索的對象。隨著結點在搜索樹上的深度增大，搜索的結點數會很快增長，並以指數形式擴張，從而所需的存儲空間和搜索花費的時間也會成倍增長。

五、A*演算法
1.啟發式搜索
廣度優先搜索和雙向廣度優先搜索都屬於盲目搜索，這在狀態空間不大的情況下是很合適的演算法，可是當狀態空間十分龐大時，它們的效率實在太低，往往都是在搜索了大量無關的狀態結點後才碰到解答，甚至更本不能碰到解答。
搜索是一種試探性的查尋過程，為了減少搜索的盲目性引，增加試探的准確性，就要採用啟發式搜索了。所謂啟發式搜索就是在搜索中要對每一個搜索的位置進行評估，從中選擇最好、可能容易到達目標的位置，再從這個位置向前進行搜索，這樣就可以在搜索中省略大量無關的結點，提高了效率。
2.A*演算法
A*演算法是一種常用的啟發式搜索演算法。
在A*演算法中，一個結點位置的好壞用估價函數來對它進行評估。A*演算法的估價函數可表示為：
f'(n) = g'(n) + h'(n)
這里，f'(n)是估價函數，g'(n)是起點到終點的最短路徑值（也稱為最小耗費或最小代價），h'(n)是n到目標的最短路經的啟發值。由於這個f'(n)其實是無法預先知道的，所以實際上使用的是下面的估價函數：
f(n) = g(n) + h(n)
其中g(n)是從初始結點到節點n的實際代價，h(n)是從結點n到目標結點的最佳路徑的估計代價。在這里主要是h(n)體現了搜索的啟發信息，因為g(n)是已知的。用f(n)作為f'(n)的近似，也就是用g(n)代替g'(n)，h(n)代替h'(n)。這樣必須滿足兩個條件：（1）g(n)>=g'(n)（大多數情況下都是滿足的，可以不用考慮），且f必須保持單調遞增。（2）h必須小於等於實際的從當前節點到達目標節點的最小耗費h(n)<=h'(n)。第二點特別的重要。可以證明應用這樣的估價函數是可以找到最短路徑的。
3.A*演算法的步驟
A*演算法基本上與廣度優先演算法相同，但是在擴展出一個結點後，要計算它的估價函數，並根據估價函數對待擴展的結點排序，從而保證每次擴展的結點都是估價函數最小的結點。
A*演算法的步驟如下：
1）建立一個隊列，計算初始結點的估價函數f，並將初始結點入隊，設置隊列頭和尾指針。
2）取出隊列頭（隊列頭指針所指）的結點，如果該結點是目標結點，則輸出路徑，程序結束。否則對結點進行擴展。
3）檢查擴展出的新結點是否與隊列中的結點重復，若與不能再擴展的結點重復（位於隊列頭指針之前），則將它拋棄；若新結點與待擴展的結點重復（位於隊列頭指針之後），則比較兩個結點的估價函數中g的大小，保留較小g值的結點。跳至第五步。
4）如果擴展出的新結點與隊列中的結點不重復，則按照它的估價函數f大小將它插入隊列中的頭結點後待擴展結點的適當位置，使它們按從小到大的順序排列，最後更新隊列尾指針。
5）如果隊列頭的結點還可以擴展，直接返回第二步。否則將隊列頭指針指向下一結點，再返回第二步。
4.八數碼問題的A*演算法的估價函數
估價函數中，主要是計算h，對於不同的問題，h有不同的含義。那麼在八數碼問題中，h的含意是各什麼？八數碼問題的一個狀態實際上是數字0~8的一個排列，用一個數組p[9]來存儲它，數組中每個元素的下標，就是該數在排列中的位置。例如，在一個狀態中，p[3]=7，則數字7的位置是3。如果目標狀態數字3的位置是8，那麼數字7對目標狀態的偏移距離就是3，因為它要移動3步才可以回到目標狀態的位置。
八數碼問題中，每個數字可以有9個不同的位置，因此，在任意狀態中的每個數字和目標狀態中同一數字的相對距離就有9*9種，可以先將這些相對距離算出來，用一個矩陣存儲，這樣只要知道兩個狀態中同一個數字的位置，就可查出它們的相對距離，也就是該數字的偏移距離：
0 1 2 3 4 5 6 7 8
0 0 1 2 1 2 3 2 3 4
1 1 0 1 2 1 2 3 2 3
2 2 1 0 3 2 1 4 3 2
3 1 2 3 0 1 2 1 2 3
4 2 1 2 1 0 1 2 1 2
5 3 2 1 2 1 0 3 2 1
6 2 3 4 1 2 3 0 1 2
7 3 2 3 2 1 2 1 0 1
8 4 3 2 3 2 1 2 1 0
例如在一個狀態中，數字8的位置是3，在另一狀態中位置是7，那麼從矩陣的3行7列可找到2，它就是8在兩個狀態中的偏移距離。
估價函數中的h就是全體數字偏移距離之和。顯然，要計算兩個不同狀態中同一數字的偏移距離，需要知道該數字在每個狀態中的位置，這就要對數組p[9]進行掃描。由於狀態發生變化，個數字的位置也要變化，所以每次計算h都沿線掃描數組，以確定每個數字在數組中的位置。為了簡化計算，這里用一個數組存儲狀態中各個數字的位置，並讓它在狀態改變時隨著變化，這樣就不必在每次計算h時，再去掃描狀態數組。
例如，某個狀態中，數字5的位置是8，如果用數組r[9]存儲位置，那麼就有r[5]=8。
現在用數組r[9]存儲當前狀態的數字位置，而用s[9]存儲目標狀態的數字位置，那麼當前狀態數字i對目標狀態的偏移距離就是矩陣中r[i]行s[i]列對應的值。
5.A*演算法的類結構
A*演算法的類聲明如下：
class TAstar:public TEight
{
public:
TAstar(){} //構造函數
TAstar(char *fname); //帶參數構造函數
virtual void Search(); //A*搜索法
private:
int f,g,h; //估價函數
int r[Num]; //存儲狀態中各個數字位置的輔助數組
static int s[Num]; //存儲目標狀態中各個數字位置的輔助數組
static int e[]; //存儲各個數字相對距離的輔助數組
void Printl(TList<TAstar> L); //成員函數，輸出搜索路徑
int Expend(int i); //成員函數，A*演算法的狀態擴展函數
int Calcuf(); //成員函數，計算估價函數
void Sort(TList<TAstar>& L,int k); //成員函數，將新擴展結點按f從小到大順序插入待擴展結點隊列
int Repeat(TList<TAstar> &L); //成員函數，檢查結點是否重復
};

int TAstar::s[Num],TAstar::e[Num*Num];

TAstar::TAstar(char *fname):TEight(fname)
{
for(int i=0;i<Num;)
{
r[p[i]]=i; //存儲初始狀態個個數字的位置
s[q[i]]=i++; //存儲目標狀態個個數字的位置
}
ifstream fin;
fin.open("eight_dis.txt",ios::in); //打開數據文件
if(!fin)
{
cout<<"不能打開數據文件!"<<endl;
return;
}
for(int i=0;i<Num*Num;i++) //讀入各個數字相對距離值
fin>>e[i];
fin.close();
f=g=h=0; //估價函數初始值
}

void TAstar::Printl(TList<TAstar> L)
{
TAstar T=*this;
if(T.last==-1) return;
else
{
T=L.GetData(T.last);
T.Printl(L);
T.Printf();
}
}

int TAstar::Expend(int i)
{
if(Extend(i)) //結點可擴展
{
int temp=r[p[r[0]]]; //改變狀態後數字位置變化，存儲改變後的位置
r[p[r[0]]]=r[0];
r[0]=temp;
return 1;
}
return 0;
}

int TAstar::Calcuf()
{
h=0;
for(int i=0;i<Num;i++) //計算估價函數的 h
h+=e[Num*r[i]+s[i]];
return ++g+h;
}

void TAstar::Sort(TList<TAstar>& L,int k)
{
int n=L.Getlen();
int i;
for(i=k+1;i<n;i++)
{
TAstar T=L.GetData(i);
if(this->f<=T.f)
break;
}
L.Insert(*this,i);
}

int TAstar::Repeat(TList<TAstar> &L)
{
int n=L.Getlen();
int i;
for(i=0;i<n;i++)
if(L.GetData(i)==*this)
break;
return i;
}

void TAstar::Search()
{
TAstar T=*this; //初始結點
T.f=T.Calcuf(); //初始結點的估價函數
TList<TAstar> L; //建立隊列
L.Append(T); //初始結點入隊
int head=0,tail=0; //隊列頭和尾指針
while(head<=tail) //隊列不空則循環
{
for(int i=0;i<4;i++) //空格可能移動方向
{
T=L.GetData(head); //去隊列頭結點
if(T.h==0) //是目標結點
{
T.Printl(L);//輸出搜索路徑
T.Printf(); //輸出目標狀態
return; //結束
}
if(T.Expend(i)) //若結點可擴展
{
int k=T.Repeat(L); //返回與已擴展結點重復的序號
if(k<head) //如果是不能擴展的結點
continue; //丟棄
T.last=head; //不是不能擴展的結點，記錄父結點
T.f=T.Calcuf(); //計算f
if(k<=tail) //新結點與可擴展結點重復
{
TAstar Temp=L.GetData(k);
if(Temp.g>T.g) //比較兩結點g值
L.SetData(T,k); //保留g值小的
continue;
}
T.Sort(L,head) ; //新結點插入可擴展結點隊列
tail++; //隊列尾指針後移
}
}
head++; //一個結點不能再擴展，隊列頭指針指向下一結點
}
}

六、測試程序
A*演算法的測試：
int main()
{
TAstar aStar("eight.txt");
aStar.Search();
system("pauze");
return 0;
}
eight.txt文件中的數據（初始態和目標態）：
一共三行，第一行是用空格隔開的九個數字0~8，這是初始狀態。第二行是一個數字，空格（數字0）的位置，第三行也是用空格隔開的九個數字0~8，這是目標狀態。

8 3 5 1 2 7 4 6 0
8
1 2 3 4 5 6 7 8 0

eight_dis.txt中的數據（估計函數使用）
0 1 2 1 2 3 2 3 4
1 0 1 2 1 2 3 2 3
2 1 0 3 2 1 4 3 2
1 2 3 0 1 2 1 2 3
2 1 2 1 0 1 2 1 2
3 2 1 2 1 0 3 2 1
2 3 4 1 2 3 0 1 2
3 2 3 2 1 2 1 0 1
4 3 2 3 2 1 2 1 0

eight_Result.txt中的結果（運行後得到的結果）

七、演算法運行結果
1.BFS演算法只能適用於到達目標結點步數較少的情況，如果步數超過15步，運行時間太長，實際上不再起作用。
2.對於隨機生成的同一個可解狀態，BFS演算法最慢，DBFS演算法較慢，A*演算法較快。但在15步以內，DBFS演算法與A*演算法相差時間不大，超過15步後，隨步數增加，A*演算法的優勢就逐漸明顯，A*演算法要比DBFS演算法快5倍以上，並隨步數增大而增大。到25步以上，DBFS同樣因運行時間過長而失去價值。
3.一般來說，解答的移動步數每增加1，程序運行時間就要增加5倍以上。由於八數碼問題本身的特點，需要檢查的節點隨步數增大呈指數形式增加，即使用A*演算法，也難解決移動步數更多的問題。

八、問題可解性
八數碼問題的一個狀態實際上是0~9的一個排列，對於任意給定的初始狀態和目標，不一定有解，也就是說從初始狀態不一定能到達目標狀態。因為排列有奇排列和偶排列兩類，從奇排列不能轉化成偶排列或相反。
如果一個數字0~8的隨機排列871526340，用F(X)表示數字X前面比它小的數的個數，全部數字的F(X)之和為Y=∑(F(X))，如果Y為奇數則稱原數字的排列是奇排列，如果Y為偶數則稱原數字的排列是偶排列。
例如871526340這個排列的
Y=0+0+0+1+1+3+2+3+0=10
10是偶數，所以他偶排列。871625340
Y=0+0+0+1+1+2+2+3+0=9
9是奇數，所以他奇排列。
因此，可以在運行程序前檢查初始狀態和目標狀態的窘是否相同，相同則問題可解，應當能搜索到路徑。否則無解。

PS:整理自網路

『拾』 求一個最短路徑演算法（能避障）的程序！非常感謝！

給你幾個關鍵字自己搜吧,一搜一大把的.
Dijkstra演算法; AStar演算法; 遺傳演算法; 螞蟻演算法;