631306050110董涵+狀態(tài)空間搜索+啟發(fā)式搜索.docVIP

重慶交通大學(xué)計(jì)算機(jī)與信息學(xué)院驗(yàn)證性實(shí)驗(yàn)報(bào)告班 級(jí)： 軟件開(kāi)發(fā) 專(zhuān)業(yè)2013 級(jí)1 班 學(xué) 號(hào)： 631306050110 姓 名： 董涵 實(shí)驗(yàn)項(xiàng)目名稱(chēng)：基于空間狀態(tài)搜索的8數(shù)碼問(wèn)題實(shí)驗(yàn)項(xiàng)目性質(zhì)： 驗(yàn)證性實(shí)驗(yàn) 實(shí)驗(yàn)所屬課程： 人工智能 實(shí)驗(yàn)室(中心)：軟件中心實(shí)驗(yàn)室（語(yǔ)音樓8樓）指 導(dǎo) 教 師 ： 朱振國(guó) 實(shí)驗(yàn)完成時(shí)間： 2016 年 6 月 13 日評(píng)閱意見(jiàn)：實(shí)驗(yàn)成績(jī)： 簽名： 年 月 日一、實(shí)驗(yàn)?zāi)康?1. 熟悉人工智能系統(tǒng)中的問(wèn)題求解過(guò)程； 2. 熟悉狀態(tài)空間的盲目搜索的應(yīng)用； 3. 熟悉對(duì)八數(shù)碼問(wèn)題的建模、求解及編程語(yǔ)言的應(yīng)用。二、實(shí)驗(yàn)內(nèi)容及要求 在一個(gè)3*3的九宮中有1-8個(gè)數(shù)碼及一個(gè)空格隨即的擺放在其中的格子里，現(xiàn)在要求實(shí)驗(yàn)這個(gè)問(wèn)題：將該九宮格調(diào)整為某種有序的形式。調(diào)整的規(guī)則是，每次只能將與空格（上、下、左、右）相鄰的一個(gè)數(shù)字平移到空格中。三、實(shí)驗(yàn)設(shè)備及軟件 TC2.0 或 VC6.0 編程語(yǔ)言或其它編程語(yǔ)言四、設(shè)計(jì)方案 題目 基于狀態(tài)空間搜索的8數(shù)碼問(wèn)題 設(shè)計(jì)的主要思路 主要功能用選定的編程語(yǔ)言編寫(xiě)程序，利用不同的搜索策略進(jìn)行狀態(tài)空間搜索實(shí)現(xiàn)8數(shù)碼難題。5、 主要代碼 #include #include Node.h #include Queue.h #include Search.h#include Tree.h void CreateNode1(std:vector& 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); void CreateNode4(std:vector& 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); void CreateNode8(std:vector& 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); void CreateNode20(std:vector& 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); void CreateNode27(std:vector& 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); void CreateNode_test1(std:vector& 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); void test_expand() std:vector s; CreateNode1(s); std:vector d; CreateNode4(d); Node source(s); Node dest(d); source.Display(); Search search(&source); std:cout source.Expand(dest, search); void test_search() std:vector s; CreateNode1(s); std:vector d; CreateNode4(d); Node source(s); Node dest(d); source.Display(); dest.Display(); Search search(&source); search.Find( & dest); search.DisplayRoute(); void test_search2level() std:vector s; CreateNode1(s); std:vector d; CreateNode8(d); Node source(s); Node dest(d); source.Display(); dest.Display(); Search search(&source); search.Find( & dest); search.DisplayRoute(); void test_search_lab1() std:vector s;CreateNode1(s); std:vector d; CreateNode27(d); Node source(s); Node dest(d); source.Display(); dest.Display(); Search search(&source); search.Find( & dest); search.DisplayRoute(); int main(int argc, char* argv) / test_expand(); / test_search(); / test_search2level(); / test_search_lab1(); std:vector s; CreateNode1(s); std:vector d; CreateNode27(d); Node source(s); Node dest(d); source.Display(); dest.Display(); Search search(&source); search.Find( & dest); search.DisplayRoute(); return 0; Node函數(shù)： #include #include #include Node.h bool IsOpposite(OP opa, OP opb) if (LEFT=opa & RIGHT = opb) return true; if (RIGHT=opa & LEFT = opb) return true; if (UP=opa & DOWN = opb) return true; if (DOWN=opa & UP = opb) return true; return false; Node:Node(std:vector const& state) : m_state(state) , m_pParent(NULL) , m_children() , m_op(EMPTY) void ShowOP(OP op) switch (op) case EMPTY: std:cout EMPTY; break; case UP: std:cout UP; break; case DOWN: std:cout DOWN; break; case LEFT: std:cout LEFT; break; case RIGHT: std:cout RIGHT; break; default: exit(-1); void ShowOPs(std:vector const& ops) for (int id=0; idops.size(); +id) ShowOP(opsid); std:cout ; std:cout std:endl; bool Node:Expand(Node const& destNode, Search& search) int spaceId = FindEmptySpaceId(); std:cout space is at spaceId std:endl; std:vector legalOPs = GenerateLegalOperators(spaceId); ShowOPs(legalOPs); while ( legalOPs.size() 0 ) OP op = legalOPs legalOPs.size() - 1 ; legalOPs.pop_back(); Node* pChild = CreateChild(op); if ( *pChild = destNode ) search.SetDestPt(pChild); return true; search.GetQueue().EnQueue(pChild); return false; void Node:Display() const for(int i=0; im_state.size(); +i) std:cout m_statei ; Queue& GetQueue() return m_queue; void Find(Node* destNode); Node* Select(); void SetDestPt(Node* pDestNode) m_pDestNode = pDestNode; void DisplayRoute() const; private: Queue m_queue; Node* m_pDestNode; ; #endif / PROGECT_1_SEARCH Tree： #ifndef PROGECT_1_TREE #define PROGECT_1_TREE #endif / PROGECT_1_TREE六、測(cè)試結(jié)果及說(shuō)明 七、實(shí)驗(yàn)體會(huì)人工智能這門(mén)課讓我學(xué)到了很多有趣的東西，這次的實(shí)驗(yàn)讓我對(duì)人工智能也有了一些了解，今后想要了解時(shí)會(huì)更加輕松。重慶交通大學(xué)計(jì)算機(jī)與信息學(xué)院驗(yàn)證性實(shí)驗(yàn)報(bào)告班 級(jí)： 計(jì)算機(jī)軟件開(kāi)發(fā)專(zhuān)業(yè) 2013級(jí)1班 學(xué) 號(hào)： 631306050110 姓 名： 董涵 實(shí)驗(yàn)項(xiàng)目名稱(chēng)： 啟發(fā)式搜索 實(shí)驗(yàn)項(xiàng)目性質(zhì)： 驗(yàn)證性實(shí)驗(yàn) 實(shí)驗(yàn)所屬課程： 人工智能 實(shí)驗(yàn)室(中心)：軟件中心實(shí)驗(yàn)室（語(yǔ)音樓8樓）指 導(dǎo) 教 師 ： 朱振國(guó) 實(shí)驗(yàn)完成時(shí)間： 2016 年 6 月 13 日評(píng)閱意見(jiàn)：實(shí)驗(yàn)成績(jī)： 簽名： 年 月 日一、 實(shí)驗(yàn)?zāi)康睦斫夂驼莆誂*算法二、實(shí)驗(yàn)內(nèi)容及要求1實(shí)驗(yàn)內(nèi)容：在8數(shù)碼問(wèn)題中，利用策略函數(shù)判斷搜索，并使用A*算法減少搜索目標(biāo)。 2實(shí)驗(yàn)要求：用選定的編程語(yǔ)言編寫(xiě)程序，利用不同的搜索策略進(jìn)行狀態(tài)空間搜索（如寬度優(yōu)先搜索、深度優(yōu)先搜索、有界深度優(yōu)先搜索等）三、實(shí)驗(yàn)設(shè)備及軟件 一臺(tái)PC，VC6+四、設(shè)計(jì)方案 題目 啟發(fā)式搜索 A*算法 設(shè)計(jì)的主要思路搜索策略啟發(fā)式搜索技術(shù)（1） 原理：?jiǎn)l(fā)式搜索就是在狀態(tài)空間中的搜索對(duì)每一個(gè)搜索的位置進(jìn)行評(píng)估，得到最好的位置，再?gòu)倪@個(gè)位置進(jìn)行搜索直到目標(biāo)。這樣可以省略大量無(wú)謂的搜索路徑，提高了效率。在啟發(fā)式搜索中，對(duì)位置的估價(jià)是十分重要的。采用了不同的估價(jià)可以有不同的效果。（2） 估價(jià)函數(shù)計(jì)算一個(gè)節(jié)點(diǎn)的估價(jià)函數(shù)，可以分成兩個(gè)部分：1、 已經(jīng)付出的代價(jià)（起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)）；2、 將要付出的代價(jià)（當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)）。節(jié)點(diǎn)n的估價(jià)函數(shù)定義為從初始節(jié)點(diǎn)、經(jīng)過(guò)n、到達(dá)目標(biāo)節(jié)點(diǎn)的路徑的最小代價(jià)的估計(jì)值，即 = + 。是從初始節(jié)點(diǎn)到達(dá)當(dāng)前節(jié)點(diǎn)n的實(shí)際代價(jià)； 是從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的最佳路徑的估計(jì)代價(jià)，體現(xiàn)出搜索過(guò)程中采用的啟發(fā)式信息（背景知識(shí)），稱(chēng)之為啟發(fā)函數(shù)。所占的比重越大，越趨向于寬度優(yōu)先或等代價(jià)搜索；反之，的比重越大，表示啟發(fā)性能就越強(qiáng)。本實(shí)驗(yàn)中我們使用函數(shù)，其值是節(jié)點(diǎn)n與目標(biāo)狀態(tài)節(jié)點(diǎn)相比較，每個(gè)錯(cuò)位棋牌在假設(shè)不受阻攔的情況下，移動(dòng)到目標(biāo)狀態(tài)相應(yīng)位置所需走步（移動(dòng)次數(shù)）的總和。顯然比更接近于，因?yàn)椴粌H考慮了錯(cuò)位因素，還考慮了錯(cuò)位的距離。算法Begin：讀入初始狀態(tài)和目標(biāo)狀態(tài)，并計(jì)算初始狀態(tài)評(píng)價(jià)函數(shù)值f；根據(jù)初始狀態(tài)和目標(biāo)狀態(tài)，判斷問(wèn)題是否可解；If(問(wèn)題可解)把初始狀態(tài)假如open表中；While（未找到解&狀態(tài)表非空）在open表中找到評(píng)價(jià)值最小的節(jié)點(diǎn)，作為當(dāng)前結(jié)點(diǎn)；判斷當(dāng)前結(jié)點(diǎn)狀態(tài)和目標(biāo)狀態(tài)是否一致，若一致，跳出循環(huán)；否則跳轉(zhuǎn)到；對(duì)當(dāng)前結(jié)點(diǎn)，分別按照上、下、左、右方向移動(dòng)空格位置來(lái)擴(kuò)展新的狀態(tài)結(jié)點(diǎn)，并計(jì)算新擴(kuò)展結(jié)點(diǎn)的評(píng)價(jià)值f并記錄其父節(jié)點(diǎn)；對(duì)于新擴(kuò)展的狀態(tài)結(jié)點(diǎn)，判斷其是否重復(fù)，若不重復(fù)，把其加入到open表中；把當(dāng)前結(jié)點(diǎn)從open表中移除；End whileEnd if輸出結(jié)果；End五、主要代碼#include#include#include#define Overflow 1#define N 3int goalNN=1,2,3,8,0,4,7,6,5;int zero2,NodeQTY=0;int *z=zero;/記錄0的位置，zero0:r行；zero1:c列 typedef int Piece;struct Chessboard/棋盤(pán)信息 Piece posNN;/記錄每個(gè)數(shù)碼a的位置r行c列int d,f,move;/d:深度；f:啟發(fā)函數(shù)值 ；move:父節(jié)點(diǎn)移動(dòng)到該節(jié)點(diǎn)的方式 ;struct LNodeChessboard board;LNode *parent,*next;bool flag;typedef LNode* List;int* Findzero(LNode* &Node)int i,j,zr2;int *z=zr;for(i=0;iN;i+)for(j=0;jboard.posij=0)zr0=i+1;zr1=j+1;break;return z;int pick(LNode *Node)int w=0,i,j,ii,jj;for(i=0;iN;i+)for(j=0;jboard.posij!=goalij&Node-board.posij!=0)for(ii=0;iiN;ii+)for(jj=0;jjboard.posij=goaliijj) w=w+abs(ii-i)+abs(jj-j);break; return w;LNode* extend(LNode *Node,int depth,int zero2,int moveflag,int Choose)LNode* NewNode=new LNode;for(int i=0;iN;i+)for(int j=0;jboard.posij=Node-board.posij;switch(moveflag)case 1:/向左移，不能出界：zero1=2NewNode-board.poszero0-1zero1-1=NewNode-board.poszero0-1zero1-2;NewNode-board.poszero0-1zero1-2=0;break;case 2:/向右移，不能出界：zero1board.poszero0-1zero1-1=NewNode-board.poszero0-1zero1;NewNode-board.poszero0-1zero1=0;break;case 3:/向上移，不能出界：zero0=2NewNode-board.poszero0-1zero1-1=NewNode-board.poszero0-2zero1-1;NewNode-board.poszero0-2zero1-1=0;break;case 4:/向下移，不能出界：zero0board.poszero0-1zero1-1=NewNode-board.poszero0zero1-1;NewNode-board.poszero0zero1-1=0;break;NewNode-board.d=depth+1;switch(Choose)case 1:NewNode-board.f=NewNode-board.d+pick(NewNode);break; NewNode-board.move=moveflag;NewNode-parent=Node;NodeQTY+; return NewNode;void InitList(LNode* &Open,LNode* &Close)Open=(List)malloc(sizeof(LNode);Close=(List)malloc(sizeof(LNode);if(!Open&!Close)exit(Overflow);Open-next=NULL;Close-next=NULL;int ListInsert(List &L,LNode* NewNode)List p=L;while(p-next)p=p-next;NewNode-next=p-next;p-next=NewNode;return true;LNode* Getminf(List &L)List p=L,q=L-next,r=L,min;min=q;/p,q尋找f最小值的指針，r指向表L中min前一個(gè)元素 if(!q)return NULL;while(q)if(min-board.fq-board.f)r=p;min=q;p=q;q=q-next;r-next=min-next;min-next=NULL;return min;int main()int i,j,choose;List Open,Close;LNode *Best,*current;LNode *Start=new LNode;printf(ttt八 數(shù) 碼 問(wèn) 題 求 解n); printf(n請(qǐng)輸入初始狀態(tài)：);for(i=0;iN;i+)for(j=0;jboard.posij);printf(注:The flag of movement-1:左移;2:右移;3:上移;4:下移)n);printf(初始棋盤(pán)狀態(tài)：n); for(i=0;iN;i+)for(j=0;jboard.posij);printf(|n);InitList(Open,Close); printf(A*算法:); scanf(%d,&choose); Start-board.d=0;switch(choose)case 1:Start-board.f=Start-board.d+pick(Start);break; Start-board.move=0;Start-parent=NULL;Start-next=NULL;Start-flag=1;ListInsert(Open,Start);/將S加入到Open表中 while(Open-next)Best=Getminf(Open);ListInsert(Close,Best