------------專業資料-一、實驗內容和要求3×31到81的，其初始狀態如圖1所示，要求對空格執行空格左移、空格右移、空格上移和空格下移這四個操作使得棋盤從初始狀態到目標狀態。例如：2828316470512384765(a)初始狀態 (b)目標狀態圖1八數碼問題示意圖（廣度優先搜索或深度優先搜索式搜索方法（全局擇優搜索，加權狀態圖搜索，A算法或A*算法）編程求解八（初始狀態任選OPEN表和CLOSED表，給出解路徑，對實驗結果進行分析總結，得出結論。二、實驗目的熟悉人工智能系統中的問題求解過程；熟悉狀態空間的盲目搜索和啟發式搜索算法的應用；三、實驗算法A*算法是一種常用的啟發式搜索算法。在A*算法中，一個結點位置的好壞用估價函數來對它進行評估。A*算法的估價函數可表示為：f'(n)=g'(n)+h'(n)這里，f'(n)是估價函數，g'(n)是起點到終點的最短路徑值（也稱為最小耗費或最小代價h'(n)是n到目標的最短路經的啟發值。由于這個知道的，所以實際上使用的是下面的估價函數：f(n)=g(n)+h(n)其中g(n)是從初始結點到節點n的實際代價，h(n)是從結點n到目標結點的最佳h(ng(n用f(n)作為f'(n)的近似，也就是用g(n)代替g'(n)，h(n)代替h'(n)。這樣必須滿足1g(n)>=g'(n（大多數情況下都是滿足的，可以不用考慮f必必須小于等于實際的從當前節點到達目標節點的最小耗h(n)<=h'(n)。第二點特別的重要。可以證明應用這樣的估價函數是可以找到最短路徑的。3.A*算法的步驟A*函數最小的結點。A*算法的步驟如下：建立一個隊列，計算初始結點的估價函數f，和尾指針。取出隊列頭（隊列頭指針所指）的結點，如果該結點是目標結點，則輸出路徑，程序結束。否則對結點進行擴展。檢查擴展出的新結點是否與隊列中的結點重復，若與不能再擴展的結點重復（位于隊列頭指針之前，則將它拋棄；若新結點與待擴展的結點重復（位于隊列頭指針之后gg跳至第五步。如果擴展出的新結點與隊列中的結點不重復，則按照它的估價函數f大小將它插入隊列中的頭結點后待擴展結點的適當位置，使它們按從小到大的順序排列，最后更新隊列尾指針。一結點，再返回第二步。四、程序框圖------------專業資料-五、實驗結果及分析輸入初始狀態：283 目標狀態：123164 804705 765運行結果屏幕打印OPEN表與CLOSE表：OPENCLOSE123402345601234670152346890157234891001576234811121301576923481213141501576911----------3481213141516174812131415161718194812131415161719208121314151617192122121314151617192122231213141516171921222412131415161719212224發現26為目標節點

015769112015769112301576911231801576911231840157691123184801576911231848230157691123184823240…7280…728310476520.118032147658..121237840659..10123804765注釋：每個方格中最上面兩個數字23..91237846051…72..113..114..112032832832831841640141407657057657655…86…910.1411.1418.1019.1221.1222.140232302832830832832832831841841641642147141431457657657057507650657657607…910.11123234084180765765分別為編號與啟發值，下面九個數字為八數碼。較粗的11..912.1313.13箭頭為解路徑10312312382486484076570576525.1212378465025.1212378465014.1201382476515.1431082476524..8123704685目標節點六、結論對于八數碼問題，BFS，A*算法較快。八數碼問題的一個狀態實際0~90~8871526340，用XF(XY=∑(F(XYY可解，應當能搜索到路徑。否則無解。七、源程序及注釋#include<iostream>#include<ctime>#include<vector>usingnamespacestd;constintROW=3;constintCOL=3;constintMAXDISTANCE=10000;constintMAXNUM=10000;intabs(inta){if(a>0)returna;elsereturn-a;}typedefstruct_Node{intdigit[ROW][COL];intdist; // 距離intdep; //深度intindex//索引值}Node;Nodesrc,dest;vector<Nodenode_v; //儲存節點boolisEmptyOfOPEN(){//判斷Open表是否空for(inti=0;i<node_v.size();i++){if(node_v[i].dist!=MAXNUM)returnfalse;}returntrue;}boolisEqual(intindex,intdigit[][COL]){ //點相同for(inti=0;i<ROW;i++)for(intj=0;j<COL;j++){if(node_v[index].digit[i][j]!=digit[i][j])returnfalse;}returntrue;}ostream&operator<<(ostream&os,Node&node){for(inti=0;i<ROW;i++){for(intj=0;j<COL;j++)os<<node.digit[i][j]<<'';os<<endl;}returnos;}voidPrintSteps(intindex,vector<Node>&rstep_v){rstep_v.push_back(node_v[index]);index=node_v[index].index;while(index!=0){rstep_v.push_back(node_v[index]);index=node_v[index].index;}for(inti=rstep_v.size()-1;i>=0;i--)cout<<"Step"<<rstep_v.size()-i<<endl<<rstep_v[i]<<endl;}

//輸出步驟voidSwap(int&a,int&b){//交換intt;t=a;a=b;b=t;}voidAssign(Node&node,intindex //for(inti=0;i<ROWi++)for(intj=0;j<COL;j++)node.digit[i][j]=node_v[index].digit[i][j];}intGetMinNode( //intdistMAXNUM;intloc; //thelocationofminimizenodefor(inti=0;i<node_v.size();i++){if(node_v[i].dist==MAXNUM)continue;elseif((node_v[i].dist+node_v[i].dep)<dist){loc=i;dist=node_v[i].dist+node_v[i].dep;}}returnloc;}boolisExpandable(Node&node) //for(inti=0;i<node_v.size();i++if(isEqual(i,node.digit))returnfalse;}returntrue;}intDistance(Node&node,intdigit[][COL]) //intdistance0;boolflag=false;for(inti=0;i<ROW;i++)for(intj=0;j<COL;j++)for(intk=0;k<ROW;k++){for(intl=0;l<COL;l++){if(node.digit[i][j]==digit[k][l]){distance+=abs(i-k)+abs(j-l);flag=true;break;}elseflag=false;}if(flag)break;}returndistance;}intMinDistance(inta,intb) //return(a<b?ab);}voidProcessNode(intindex //intxy;boolflag;for(inti=0;i<ROW;i++){for(intj=0;j<COL;j++){if(node_v[index].digit[i][j]==0){x=i;y=j;flag=true;break;}elseflag=false;}if(flag)break;}Nodenode_up; //Assign(node_upindex);intdist_up=MAXDISTANCE;if(x>0){Swap(node_up.digit[x][y],node_up.digit[x-1][y]);if(isExpandable(node_up)){dist_up=Distance(node_up,dest.digit);node_up.index=index;node_up.dist=dist_up;node_up.dep=node_v[index].dep+1;node_v.push_back(node_up);}}Nodenode_down;//下移操作Assign(node_down,index);intdist_down=MAXDISTANCE;if(x<2){Swap(node_down.digit[x][y],node_down.digit[x+1][y]);if(isExpandable(node_down)){dist_down=Distance(node_down,dest.digit);node_down.index=index;node_down.dist=dist_down;node_down.dep=node_v[index].dep+1;node_v.push_back(node_down);}}Nodenode_left;//左移操作Assign(node_left,index);intdist_left=MAXDISTANCE;if(y>0){Swap(node_left.digit[x][y],node_left.digit[x][y-1]);if(isExpandable(node_left)){dist_left=Distance(node_left,dest.digit);node_left.index=index;node_left.dist=dist_left;node_left.dep=node_v[index].dep+1;node_v.push_back(node_left);}}Nodenode_right; //Assign(node_rightindex);intdist_right=MAXDISTANCE;if(y<2){Swap(node_right.digit[x][y],node_right.digit[x][y+1]);if(isExpandable(node_right)){dist_right=Distance(node_right,dest.digit);node_right.index=index;node_right.dist=dist_right;node_right.dep=node_v[index].dep+1;node_v.push_back(node_right);}}node_v[index].dist=