大工20春《人工智能》大作業(yè)題目及要求

大連理工大學(xué)遠(yuǎn)程與繼續(xù)教育學(xué)院《人工智能》課程設(shè)計(jì)專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)本文內(nèi)容僅供思路參考題目：題目一：A*算法1.談?wù)勀銓?duì)本課程學(xué)習(xí)過程中的心得體會(huì)與建議？A*算法是一種有序搜索算法，其特點(diǎn)在于對(duì)估價(jià)函數(shù)的定義上。對(duì)于一般的有序搜索，總是選擇f值最小的節(jié)點(diǎn)作為擴(kuò)展節(jié)點(diǎn)。通過本學(xué)期學(xué)習(xí)，我熟悉啟發(fā)式搜索的定義、估價(jià)函數(shù)和算法過程，并利用A*算法求解了8數(shù)碼難題，理解了求解流程和搜索順序。本次課程實(shí)踐過程中鞏固了所學(xué)的知識(shí)，通過實(shí)踐也提高了自己的編程和思維能力，收獲很多。《人工智能》課程設(shè)計(jì),從以下5個(gè)題目中任選其一作答。題目一：A*算法一、算法思路A*算法是一種有序搜索算法，其特點(diǎn)在于對(duì)估價(jià)函數(shù)的定義上。對(duì)于一般的有序搜索，總是選擇f值最小的節(jié)點(diǎn)作為擴(kuò)展節(jié)點(diǎn)。因此，f是根據(jù)需要找到一條最小代價(jià)路徑的觀點(diǎn)來估算節(jié)點(diǎn)的，所以，可考慮每個(gè)節(jié)點(diǎn)n的估價(jià)函數(shù)值為兩個(gè)分量：從起始節(jié)點(diǎn)到節(jié)點(diǎn)n的代價(jià)以及從節(jié)點(diǎn)n到達(dá)目標(biāo)節(jié)點(diǎn)的代價(jià)。A*算法基本步驟1）生成一個(gè)只包含開始節(jié)點(diǎn)n0的搜索圖G，把n0放在一個(gè)叫OPEN的列表上。2）生成一個(gè)列表CLOSED，它的初始值為空。3）如果OPEN表為空，則失敗退出。4）選擇OPEN上的第一個(gè)節(jié)點(diǎn)，把它從OPEN中移入CLPSED，稱該節(jié)點(diǎn)為n。5）如果n是目標(biāo)節(jié)點(diǎn)，順著G中，從n到n0的指針找到一條路徑，獲得解決方案，成功退出（該指針定義了一個(gè)搜索樹，在第7步建立）。6）擴(kuò)展節(jié)點(diǎn)n，生成其后繼結(jié)點(diǎn)集M，在G中，n的祖先不能在M中。在G中安置M的成員，使他們成為n的后繼。7）從M的每一個(gè)不在G中的成員建立一個(gè)指向n的指針（例如，既不在OPEN中，也不在CLOSED中）。把M1的這些成員加到OPEN中。對(duì)M的每一個(gè)已在OPEN中或CLOSED中的成員m，如果到目前為止找到的到達(dá)m的最好路徑通過n，就把它的指針指向n。對(duì)已在CLOSED中的M的每一個(gè)成員，重定向它在G中的每一個(gè)后繼，以使它們順著到目前為止發(fā)現(xiàn)的最好路徑指向它們的祖先。8）按遞增f*值，重排OPEN（相同最小f*值可根據(jù)搜索樹中的最深節(jié)點(diǎn)來解決）。9）返回第3步。在第7步中，如果搜索過程發(fā)現(xiàn)一條路徑到達(dá)一個(gè)節(jié)點(diǎn)的代價(jià)比現(xiàn)存的路徑代價(jià)低，就要重定向指向該節(jié)點(diǎn)的指針。已經(jīng)在CLOSED中的節(jié)點(diǎn)子孫的重定向保存了后面的搜索結(jié)果，但是可能需要指數(shù)級(jí)的計(jì)算代價(jià)。二、算法程序框圖開始開始讀入棋局初始狀態(tài)讀入棋局初始狀態(tài)是否可解否o是否可解否o是o是o初始狀態(tài)加入open表初始狀態(tài)加入open表在open表中找到評(píng)價(jià)值最小的節(jié)點(diǎn)，作為當(dāng)前結(jié)點(diǎn)在open表中找到評(píng)價(jià)值最小的節(jié)點(diǎn)，作為當(dāng)前結(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)是o是目標(biāo)節(jié)點(diǎn)是o否o否o擴(kuò)展新狀態(tài)，把不重復(fù)的新狀態(tài)加入open表中擴(kuò)展新狀態(tài)，把不重復(fù)的新狀態(tài)加入open表中當(dāng)前結(jié)點(diǎn)從open表移除當(dāng)前結(jié)點(diǎn)從open表移除結(jié)束輸出結(jié)果結(jié)束輸出結(jié)果三、程序代碼#include<iostream>#include<ctime>#include<vector>usingnamespacestd;constintROW=3;//行數(shù)constintCOL=3;//列數(shù)constintMAXDISTANCE=10000;//最多可以有的表的數(shù)目constintMAXNUM=10000;typedefstruct_Node{intdigit[ROW][COL];intdist;//一個(gè)表和目的表的距離intdep;//t深度intindex;//節(jié)點(diǎn)的位置}Node;Nodesrc,dest;//父節(jié)表目的表vector<Node>node_v;//存儲(chǔ)節(jié)點(diǎn)boolisEmptyOfOPEN()//open表是否為空{(diào)for(inti=0;i<node_v.size();i++){if(node_v[i].dist!=MAXNUM)returnfalse;}returntrue;}boolisEqual(intindex,intdigit[][COL])//判斷這個(gè)最優(yōu)的節(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)//輸出每一個(gè)遍歷的節(jié)點(diǎn)深度遍歷{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<ROW;i++)for(intj=0;j<COL;j++)node.digit[i][j]=node_v[index].digit[i][j];}intGetMinNode()//找到最小的節(jié)點(diǎn)的位置即最優(yōu)節(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){for(inti=0;i<node_v.size();i++){if(isEqual(i,node.digit))returnfalse;}returntrue;}intDistance(Node&node,intdigit[][COL]){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){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);//向上擴(kuò)展的節(jié)點(diǎn)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);//向下擴(kuò)展的節(jié)點(diǎn)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);//向左擴(kuò)展的節(jié)點(diǎn)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);//向右擴(kuò)展的節(jié)點(diǎn)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()//主函數(shù){intnumber;cout<<"Inputsource:"<<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<<"Inputdestination:"<<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);//在容器的尾部加一個(gè)數(shù)據(jù)cout<<"Search..."<<endl;clock_tstart=clock();while(1){if(isEmptyOfOPEN()){cout<<"Cann'tsolvethisstatement!"<<endl;return-1;}else{intloc;//thelocationoftheminimizenode最優(yōu)節(jié)點(diǎn)的位置loc=GetMinNode();if(isEqual(loc,dest.digit)){vector<Node>rstep_v;cout<<"Source:"<<endl;cout<<src<<endl;PrintSteps(loc,rstep_v);cout<<"Successful!"<<endl;cout<<"Using"<<(clock()-start)/CLOCKS_PER_SEC<<"seconds."<<endl;break;}elseProcessNode(loc);}}return0;}四、程序運(yùn)行效果圖28316475(初始狀態(tài))123804765(結(jié)束狀態(tài))五、對(duì)于重排九宮問題的啟發(fā)式函數(shù)給定九宮格的初始狀態(tài)，要求在有限步的操作內(nèi)，使其轉(zhuǎn)化為目標(biāo)狀態(tài)，且所得到的解是代價(jià)最小解(即移動(dòng)的步數(shù)最少)。如：88124376512384765初始格局目標(biāo)狀態(tài)#include"iostream.h"#include<time.h>#include<stdio.h>#include<dos.h>#include<conio.h>staticinttarget[9]={1,2,3,8,0,4,7,6,5};//classdefinitionclasseight_num{private: intnum[9]; intnot_in_position_num; intdeapth; inteva_function;public: eight_num*parent; eight_num*leaf_next; eight_num*leaf_pre;eight_num(intinit_num[9]); eight_num(intnum1,intnum2,intnum3,intnum4,intnum5,intnum6,intnum7,intnum8,intnum9) { num[0]=num1; num[1]=num2; num[2]=num3; num[3]=num4; num[4]=num5; num[5]=num6; num[6]=num7; num[7]=num8; num[8]=num9; } eight_num(void) { for(inti=0;i<9;i++) num[i]=i; }voidcul_para(void);voidget_numbers_to(intother_num[9]); intget_nipn(void) {returnnot_in_position_num;} intget_deapth(void) {returndeapth;} intget_evafun(void) {returneva_function;} voidset_num(intother_num[9]);voidshow(void); eight_num&operator=(eight_num&); eight_num&operator=(intother_num[9]); intoperator==(eight_num&); intoperator==(intother_num[9]);};//計(jì)算啟發(fā)函數(shù)g(n)的值voideight_num::cul_para(void){ inti; inttemp_nipn=0; for(i=0;i<9;i++) if(num[i]!=target[i]) temp_nipn++; not_in_position_num=temp_nipn; if(this->parent==NULL) deapth=0; else deapth=this->parent->deapth+1; eva_function=not_in_position_num+deapth;}//構(gòu)造函數(shù)1eight_num::eight_num(intinit_num[9]){ for(inti=0;i<9;i++) num[i]=init_num[i];}//顯示當(dāng)前節(jié)點(diǎn)的狀態(tài)voideight_num::show(){ cout<<num[0]; cout<<""; cout<<num[1]; cout<<""; cout<<num[2]; cout<<"\n"; cout<<num[3]; cout<<""; cout<<num[4]; cout<<""; cout<<num[5]; cout<<"\n"; cout<<num[6]; cout<<""; cout<<num[7]; cout<<""; cout<<num[8]; cout<<"\n";}//復(fù)制當(dāng)前節(jié)點(diǎn)狀態(tài)到一個(gè)另數(shù)組中voideight_num::get_numbers_to(intother_num[9]){ for(inti=0;i<9;i++) other_num[i]=num[i];}//設(shè)置當(dāng)前節(jié)點(diǎn)狀態(tài)(欲設(shè)置的狀態(tài)記錄的other數(shù)組中)voideight_num::set_num(intother_num[9]){ for(inti=0;i<9;i++) num[i]=other_num[i];}eight_num&eight_num::operator=(eight_num&another_8num){ for(inti=0;i<9;i++) num[i]=another_8num.num[i]; not_in_position_num=another_8num.not_in_position_num; deapth=another_8num.deapth+1; eva_function=not_in_position_num+deapth; return*this;}eight_num&eight_num::operator=(intother_num[9]){ for(inti=0;i<9;i++) num[i]=other_num[i]; return*this;}inteight_num::operator==(eight_num&another_8num){ intmatch=1; for(inti=0;i<9;i++) if(num[i]!=another_8num.num[i]) { match=0; break; } if(match==0) return0; else return1;}inteight_num::operator==(intother_num[9]){ intmatch=1; for(inti=0;i<9;i++) if(num[i]!=other_num[i]) { match=0; break; } if(match==0) return0; else return1;}//classdefinitionover//空格向上移intmove_up(intnum[9]){ for(inti=0;i<9;i++) if(num[i]==0) break; if(i<3) return0; else { num[i]=num[i-3]; num[i-3]=0; return1; }}//空格向下移intmove_down(intnum[9]){ for(inti=0;i<9;i++) if(num[i]==0) break; if(i>5) return0; else { num[i]=num[i+3]; num[i+3]=0; return1; }}//空格向左移intmove_left(intnum[9]){ for(inti=0;i<9;i++) if(num[i]==0) break; if(i==0||i==3||i==6) return0; else { num[i]=num[i-1]; num[i-1]=0; return1; }}//空格向右移intmove_right(intnum[9]){ for(inti=0;i<9;i++) if(num[i]==0) break; if(i==2||i==5||i==8) return0; else { num[i]=num[i+1]; num[i+1]=0; return1; }}//判斷可否解出inticansolve(intnum[9],inttarget[9]){ inti,j; intcount_num,count_target; for(i=0;i<9;i++) for(j=0;j<i;j++) { if(num[j]<num[i]&&num[j]!=0) count_num++; if(target[j]<target[i]&&target[j]!=0) count_target++; } if((count_num+count_target)%2==0) return1; else return0;}//判斷有無重復(fù)intexisted(intnum[9],eight_num*where){ eight_num*p; for(p=where;p!=NULL;p=p->parent) if(*p==num) return1; return0;}//尋找估價(jià)函數(shù)最小的葉子節(jié)點(diǎn)eight_num*find_OK_leaf(eight_num*start){ eight_num*p,*OK; p=OK=start; intmin=start->get_evafun(); for(p=start;p!=NULL;p=p->leaf_next) if(min>p->get_evafun()) { OK=p; min=p->get_evafun(); } returnOK;}//主函數(shù)開始intmain(void){ doubletime; clock_tStart,Finish; intmemery_used=0,step=0; intnum[9]; intflag=0;//是否輸入錯(cuò)誤標(biāo)志，1表示輸入錯(cuò)誤 intbingo=0;//是否查找成功標(biāo)志，1表示成功 inti,j; cout<<"Pleaseinputthenumber(0fortheblank):\n"; for(i=0;i<9;i++) { flag=0; cin>>num[i]; for(j=0;j<i;j++) if(num[i]==num[j]) flag=1; if(num[i]<0||num[i]>8||flag==1) { i--; cout<<"Illeglenumber!\tReinput!\n"; } } eight_numS(num),Target(target); S.parent=S.leaf_next=S.leaf_pre=NULL; S.cul_para(); memery_used++; cout<<"Nowtheinitialnumbersare:\n"; S.show(); cout<<"AndtheTargetis:\n"; Target.show(); if(!icansolve(num,target)) { cout<<"Noonecansolveit!\n"; cin>>i; return1; } Start=clock(); eight_num*OK_leaf=&S,*leaf_start=&S,*new_8num,*p; while(OK_leaf!=NULL&&bingo!=1) { OK_leaf=find_OK_leaf(leaf_start); if(*OK_leaf==Target) { bingo=1; break; } p=OK_leaf->leaf_pre; OK_leaf->get_numbers_to(num); if(move_up(num)&&!existed(num,OK_leaf)) { new_8num=neweight_num; new_8num->set_num(num); new_8num->parent=OK_leaf; new_8num->cul_para(); new_8num->leaf_pre=p; if(p==NULL) leaf_start=new_8num; else p->leaf_next=new_8num; p=new_8num; memery_used++; } OK_leaf->get_numbers_to(num); if(move_down(num)&&!existed(num,OK_leaf)) { new_8num=neweight_num; new_8num->set_num(num); n