人工智能化八數(shù)碼實(shí)驗(yàn)報(bào)告

...wd......wd......wd...西安郵電大學(xué)人工智能實(shí)驗(yàn)報(bào)告書〔三〕學(xué)院：自動(dòng)化學(xué)院專業(yè)：智能科學(xué)與技術(shù)班級(jí)：智能1403姓名：劉忠強(qiáng)時(shí)間：2016-3-29一、實(shí)驗(yàn)?zāi)康?.熟悉人工智能系統(tǒng)中的問題求解過程；2.熟悉狀態(tài)空間的盲目搜索策略；3.掌握盲目收索算法，重點(diǎn)是寬度優(yōu)先收索和深度優(yōu)先收索。二、實(shí)驗(yàn)算法廣度優(yōu)先收索是一種先生成的節(jié)點(diǎn)先擴(kuò)展的策略。它的過程是：從初始節(jié)點(diǎn)開場(chǎng)逐層向下擴(kuò)展，再第n層節(jié)點(diǎn)還沒有完全搜索之前，不進(jìn)如第n+1層節(jié)點(diǎn)。Open表中的節(jié)點(diǎn)總是按進(jìn)入的先后排序，先進(jìn)入的節(jié)點(diǎn)排在前面，夠進(jìn)入的排在后面。三、程序框圖四、實(shí)驗(yàn)結(jié)果及分析初始狀態(tài)：目標(biāo)狀態(tài)：283216164408705753五、源程序及注釋#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<Node>node_v;//儲(chǔ)存節(jié)點(diǎn)boolisEmptyOfOPEN(){//判斷Open表是否空for(inti=0;i<node_v.size();i++){if(node_v[i].dist!=MAXNUM)returnfalse;}returntrue;}boolisEqual(intindex,intdigit[][COL]){//判斷節(jié)點(diǎn)是否與索引值指向的節(jié)點(diǎn)一樣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){//獲取節(jié)點(diǎn)for(inti=0;i<ROW;i++)for(intj=0;j<COL;j++)node.digit[i][j]=node_v[index].digit[i][j];}intGetMinNode(){//獲取啟發(fā)值最小的節(jié)點(diǎn)intdist=MAXNUM;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){//判斷是否可擴(kuò)展for(inti=0;i<node_v.size();i++){if(isEqual(i,node.digit))returnfalse;}returntrue;}intDistance(Node&node,intdigit[][COL]){//計(jì)算距離intdistance=0;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?a:b);}voidProcessNode(intindex){//展開節(jié)點(diǎn)intx,y;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_up,index);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_right,index);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=MAXNUM;}intmain(){intnumber;cout<<"輸入初始狀態(tài):"<<endl;for(inti=0;i<ROW;i++)for(intj=0;j<COL;j++){cin>>number;src.digit[i][j]=number;}src.index=0;src.dep=1;cout<<"輸入目標(biāo)狀態(tài)"<<endl;for(intm=0;m<ROW;m++)for(intn=0;n<COL;n++){cin>>number;dest.digit[m][n]=number;}node_v.push_back(src);while(1){if(isEmptyOfOPEN()){cout<<"找不到解!"<<endl;return-1;}else{intloc;//thelocationoftheminimizenodeloc=GetMinNode();if(isEqual(loc,dest.digit)){vector<Node>rstep_v;cout<<"初始狀態(tài)："<<endl;cout<<src<<endl;PrintSteps(loc,rstep_v