昆明理工大學(xué)八數(shù)碼實(shí)驗(yàn)報(bào)告

-.z.昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院學(xué)生實(shí)驗(yàn)報(bào)告（2014—2015學(xué)年第1學(xué)期）課程名稱：人工智能及其應(yīng)用開課實(shí)驗(yàn)室：信自樓5042014年11月26日年級(jí)、專業(yè)、班計(jì)科122班**4鄒華宇成績(jī)實(shí)驗(yàn)項(xiàng)目名稱八數(shù)碼問題指導(dǎo)教師吳霖教師評(píng)語該同學(xué)是否了解實(shí)驗(yàn)原理： A.了解□ B.基本了解□ C.不了解□該同學(xué)的實(shí)驗(yàn)?zāi)芰Γ? A.強(qiáng)□ B.中等□ C.差□該同學(xué)的實(shí)驗(yàn)是否達(dá)到要求： A.達(dá)到□ B.基本達(dá)到□ C.未達(dá)到□實(shí)驗(yàn)報(bào)告是否規(guī)范： A.規(guī)范□ B.基本規(guī)范□ C.不規(guī)范□實(shí)驗(yàn)過程是否詳細(xì)記錄： A.詳細(xì)□ B.一般□ C.沒有□教師簽名：年月日一、上機(jī)目的及內(nèi)容1.上機(jī)內(nèi)容：求解八數(shù)碼問題。問題描述：八數(shù)碼難題，問題描述：在3×3方格棋盤上，分別放置了標(biāo)有數(shù)字1,2,3,4,5,6,7,8的八張牌，初始狀態(tài)S0，目標(biāo)狀態(tài)S1如圖所示，可以使用的操作有：空格上移，空格左移，空格右移，空格下移。只允許位于空格左，上，右，下方的牌移入空格。用廣度優(yōu)先搜索策略尋找從初始狀態(tài)到目標(biāo)狀態(tài)的解路徑。2.上機(jī)目的:（1）復(fù)習(xí)程序設(shè)計(jì)和數(shù)據(jù)結(jié)構(gòu)課程的相關(guān)知識(shí)；（2）熟悉人工智能系統(tǒng)中的問題求解過程；（3）熟悉對(duì)八碼數(shù)問題的建模、求解及編程語言的運(yùn)用。二、實(shí)驗(yàn)原理及基本技術(shù)路線圖（方框原理圖或程序流程圖）（1）建立一個(gè)只含有起始節(jié)點(diǎn)S的搜索圖G，把S放到一個(gè)叫做OPEN的未擴(kuò)展節(jié)點(diǎn)的表中；（2）建立一個(gè)叫做CLOSED的已擴(kuò)展節(jié)點(diǎn)表，其初始為空表；（3）LOOP:若OPEN表是空表，則失敗退出；（4）選擇OPEN表上的第一個(gè)節(jié)點(diǎn)，把它從OPEN表移除并放進(jìn)CLOSED表中，稱此節(jié)點(diǎn)為節(jié)點(diǎn)n；（5）若n為一目標(biāo)節(jié)點(diǎn)，則有解并成功退出，此解是追蹤圖G中沿著指針從n到S這條路徑而得到的；（6）擴(kuò)展節(jié)點(diǎn)n，同時(shí)生成不是n的祖先的那些后繼節(jié)點(diǎn)的集合M。把M的這些成員作為n的后繼節(jié)點(diǎn)舔到圖中；（7）對(duì)那些未曾在G中出現(xiàn)過的M成員設(shè)置一個(gè)通向n的指針。把M的這些成員加進(jìn)OPEN表。對(duì)已經(jīng)在OPEN表或CLOSED表上的成員，確定是否需要更改通到n的指針方向；（8）按*一任意方式或按*個(gè)探視值，重排OPEN表。開始把S放入開始把S放入OPEN表OPEN表為空把第一個(gè)節(jié)點(diǎn)（n）從OPEN移至CLOSED表n為目標(biāo)節(jié)點(diǎn)成功失敗把n的后繼節(jié)點(diǎn)n放入OPEN表的末端，提供返回節(jié)點(diǎn)的指針修改指針方向重排OPEN表（1）把起始節(jié)點(diǎn)放到OPEN表中；（2）如果OPEN是個(gè)空表，則沒有解，失敗退出；否則繼續(xù)；（3）把第一個(gè)節(jié)點(diǎn)從OPEN表中移除，并把它放入CLOSED的擴(kuò)展節(jié)點(diǎn)表中；（4）擴(kuò)展節(jié)點(diǎn)n。如果沒有后繼節(jié)點(diǎn)，則轉(zhuǎn)向（2）；（5）把n的所有后繼結(jié)點(diǎn)放到OPEN表末端，并提供從這些后繼結(jié)點(diǎn)回到n的指針；（6）如果n的任意一個(gè)后繼結(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)，則找到一個(gè)解答，成功退出，否則轉(zhuǎn)（2）。開始開始把S放入OPEN表OPEN表為空失敗把第一個(gè)節(jié)點(diǎn)n從把S放入OPEN表移除，放到CLOSED表中移除擴(kuò)展n，把它的后繼節(jié)點(diǎn)放入OPEN表的末端，提供回到n的指針是否任何節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)成功深度優(yōu)先實(shí)現(xiàn)過程（1）把起始節(jié)點(diǎn)S放入未擴(kuò)展節(jié)點(diǎn)OPEN表中。如果此節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則得一個(gè)解；（2）如果OPEN為一空表，則失敗退出；（3）把第一個(gè)節(jié)點(diǎn)從OPEN表移到CLOSED表；（4）如果節(jié)點(diǎn)n的深度等于最大深度，則轉(zhuǎn)向（2）；（5）擴(kuò)展節(jié)點(diǎn)n，產(chǎn)生其全部后裔，并把它們放入OPEN表的前頭。如果沒有后裔，則轉(zhuǎn)向（2）；（6）如果后繼結(jié)點(diǎn)中有任一個(gè)目標(biāo)節(jié)點(diǎn)，則得到一個(gè)解，成功退出，否則轉(zhuǎn)向（2）。開始開始把S放入OPEN表S是否為目標(biāo)節(jié)點(diǎn)成功把第一個(gè)節(jié)點(diǎn)n從把S放入OPEN表移除，放到CLOSED表中移除節(jié)點(diǎn)n深度是否等于最深界限OPEN表為空失敗擴(kuò)展n，把它的后繼放入OPEN表的前頭，提供回到n的指針是否有任何后繼節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)成功三、所用儀器、材料（設(shè)備名稱、型號(hào)、規(guī)格等或使用軟件）1臺(tái)PC及VISUALC++6.0軟件四、實(shí)驗(yàn)方法、步驟（或：程序代碼或操作過程） 1、先創(chuàng)建項(xiàng)目，新建SourceFile文件：main.cpp。#include<iostream>#include"Node.h"#include"Queue.h"#include"Search.h"#include"Tree.h"voidCreateNode1(std::vector<int>&s){ s.push_back(2); s.push_back(8); s.push_back(3); s.push_back(1); s.push_back(0); s.push_back(4); s.push_back(7); s.push_back(6); s.push_back(5);}voidCreateNode4(std::vector<int>&d){ d.push_back(2); d.push_back(8); d.push_back(3); d.push_back(1); d.push_back(6); d.push_back(4); d.push_back(7); d.push_back(0); d.push_back(5);}voidCreateNode8(std::vector<int>&d){ d.push_back(0); d.push_back(2); d.push_back(3); d.push_back(1); d.push_back(8); d.push_back(4); d.push_back(7); d.push_back(6); d.push_back(5);}voidCreateNode20(std::vector<int>&d){ d.push_back(2); d.push_back(0); d.push_back(8); d.push_back(1); d.push_back(4); d.push_back(3); d.push_back(7); d.push_back(6); d.push_back(5);}voidCreateNode27(std::vector<int>&d){ d.push_back(1); d.push_back(2); d.push_back(3); d.push_back(8); d.push_back(0); d.push_back(4); d.push_back(7); d.push_back(6); d.push_back(5);}voidCreateNode_test1(std::vector<int>&d){ d.push_back(7); d.push_back(6); d.push_back(5); d.push_back(4); d.push_back(0); d.push_back(1); d.push_back(3); d.push_back(8); d.push_back(2);}voidtest_e*pand(){ std::vector<int>s; CreateNode1(s); std::vector<int>d; CreateNode4(d); Nodesource(s); Nodedest(d); source.Display(); Searchsearch(&source); std::cout<<source.E*pand(dest,search);}voidtest_search(){ std::vector<int>s; CreateNode1(s); std::vector<int>d; CreateNode4(d); Nodesource(s); Nodedest(d); source.Display(); dest.Display(); Searchsearch(&source); search.Find(&dest); search.DisplayRoute();}voidtest_search2level(){ std::vector<int>s; CreateNode1(s); std::vector<int>d; CreateNode8(d); Nodesource(s); Nodedest(d); source.Display(); dest.Display(); Searchsearch(&source); search.Find(&dest); search.DisplayRoute();}voidtest_search_lab1(){ std::vector<int>s; CreateNode1(s); std::vector<int>d; CreateNode27(d); Nodesource(s); Nodedest(d); source.Display(); dest.Display(); Searchsearch(&source); search.Find(&dest); search.DisplayRoute();}intmain(intargc,char**argv){ //test_e*pand(); //test_search(); //test_search2level(); //test_search_lab1(); std::vector<int>s; CreateNode1(s); std::vector<int>d; CreateNode27(d); Nodesource(s); Nodedest(d); source.Display(); dest.Display(); Searchsearch(&source); search.Find(&dest); search.DisplayRoute(); return0;}2、新建SourceFile文件：Node.cpp。#ifndefPROGECT_1_NODE#definePROGECT_1_NODE#include<vector>#include"Search.h"enumOP{ EMPTY, UP, DOWN, LEFT, RIGHT};boolIsOpposite(OPopa,OPopb);classNode{public: Node(std::vector<int>const&state); boolE*pand(Nodeconst&destNode,Search&search); voidDisplay()const; voidDisplayRoute()const; booloperator==(Nodeconst&v)const;private: Node*CreateChild(OPop); intFindEmptySpaceId()const; std::vector<OP>GenerateLegalOperators(intspaceId)const; intCalIdBasedOP(OPop,intspaceId)const; boolIsWithinRange(OPop,intspaceId)const; std::vector<int>m_state; Node*m_pParent; std::vector<Node*>m_children; OPm_op;};#endif//PROGECT_1_NODE3新建HeardFile文件：node.h。#include<iostream>#include<math.h>#include"Node.h"boolIsOpposite(OPopa,OPopb){ if(LEFT==opa&&RIGHT==opb) returntrue; if(RIGHT==opa&&LEFT==opb) returntrue; if(UP==opa&&DOWN==opb) returntrue; if(DOWN==opa&&UP==opb) returntrue; returnfalse;}Node::Node(std::vector<int>const&state): m_state(state), m_pParent(NULL), m_children(), m_op(EMPTY){}voidShowOP(OPop){ switch(op) { caseEMPTY: std::cout<<"EMPTY"; break; caseUP: std::cout<<"UP"; break; caseDOWN: std::cout<<"DOWN"; break; caseLEFT: std::cout<<"LEFT"; break; caseRIGHT: std::cout<<"RIGHT"; break; default: e*it(-1); }}voidShowOPs(std::vector<OP>const&ops){ for(intid=0;id<ops.size();++id) { ShowOP(ops[id]); std::cout<<""; } std::cout<<std::endl;}boolNode::E*pand(Nodeconst&destNode,Search&search){ intspaceId=FindEmptySpaceId(); std::cout<<"spaceisat"<<spaceId<<std::endl; std::vector<OP>legalOPs=GenerateLegalOperators(spaceId); ShowOPs(legalOPs); while(legalOPs.size()>0) { OPop=legalOPs[legalOPs.size()-1]; legalOPs.pop_back(); Node*pChild=CreateChild(op); if(*pChild==destNode) { search.SetDestPt(pChild); returntrue; } search.GetQueue().EnQueue(pChild); } returnfalse;}voidNode::Display()const{ for(inti=0;i<m_state.size();++i) { std::cout<<m_state[i]<<""; } std::cout<<std::endl; std::cout<<"pParent:"<<m_pParent<<std::endl; std::cout<<"op:"; ShowOP(m_op); std::cout<<std::endl; std::cout<<""; for(intj=0;j<m_children.size();++j) { std::cout<<m_children[j]<<""; } std::cout<<std::endl;}voidNode::DisplayRoute()const{ std::vector<OP>routeOps; Nodeconst*pNode=this; while(NULL!=pNode) { routeOps.push_back(pNode->m_op); pNode=pNode->m_pParent; } for(intid=routeOps.size()-2;id>=0;--id) { ShowOP(routeOps[id]); std::cout<<""; } std::cout<<std::endl;}boolNode::operator==(Nodeconst&v)const{ for(intid=0;id<m_state.size();++id) { if(m_state[id]!=v.m_state[id]) returnfalse; } returntrue;}Node*Node::CreateChild(OPop){ std::vector<int>childState=m_state; inte*changePos1=FindEmptySpaceId(); inte*changePos2=CalIdBasedOP(op,e*changePos1); inttemp=childState[e*changePos1]; childState[e*changePos1]=childState[e*changePos2]; childState[e*changePos2]=temp; Node*child=newNode(childState); child->m_pParent=this; child->m_op=op; m_children.push_back(child); returnchild;}intNode::FindEmptySpaceId()const{ for(intid=0;id<m_state.size();++id) { if(0==m_state[id]) { returnid; } } return-1;}std::vector<OP>Node::GenerateLegalOperators(intspaceId)const{ std::vector<OP>allPossibleOps; allPossibleOps.push_back(UP); allPossibleOps.push_back(DOWN); allPossibleOps.push_back(LEFT); allPossibleOps.push_back(RIGHT); std::vector<OP>ops; for(intid=0;id<allPossibleOps.size();++id) { OPop=allPossibleOps[id]; if(IsOpposite(op,m_op)) { continue; } if(IsWithinRange(op,spaceId)) { ops.push_back(op); } } returnops;}intNode::CalIdBasedOP(OPop,intspaceId)const{ switch(op) { caseUP: spaceId-=int(sqrt(m_state.size())); break; caseDOWN: spaceId+=int(sqrt(m_state.size())); break; caseLEFT: --spaceId; break; caseRIGHT: ++spaceId; break; default: return-1; } returnspaceId;}boolNode::IsWithinRange(OPop,intspaceId)const{ spaceId=CalIdBasedOP(op,spaceId); if(spaceId>=0&&spaceId<m_state.size()) { returntrue; } returnfalse;}4、新建SourceFile文件：Queue.cpp。#include"Queue.h"voidQueue::EnQueue(Node*pNode){ m_queue.push_back(pNode);}Node*Queue::DeQueue(){ if(m_queue.size()==0) { returnNULL; } Node*pNode=m_queue[0]; m_queue.pop_front(); returnpNode;}5、新建HeardFile文件：Queue.h。#ifndefPROGECT_1_QUEUE#definePROGECT_1_QUEUE#include<deque>classNode;classQueue{public: voidEnQueue(Node*pNode); Node*DeQueue();private: std::deque<Node*>m_queue;};#endif//PROGECT_1_QUEUE6、新建SourceFile文件：Search.cpp。#include"Search.h"#include"Node.h"Search::Search(Node*root): m_queue(), m_pDestNode(NULL){ m_queue.EnQueue(root);}Node*Search::Select(){ returnm_queue.DeQueue();}voidSearch::Find(Node*destNode){ boolisFound=false; while(!isFound) { Node*pNode=Select(); pNode->Display(); isFound