八數(shù)碼難題的搜索求解演示.doc

人工智能實(shí)驗(yàn)報(bào)告 學(xué) 院：信息科學(xué)與工程學(xué)院班 級(jí)： 自動(dòng)化0901班 學(xué) 號(hào)： 0909090316 姓 名： 孫錦崗指導(dǎo)老師： 劉麗玨 日 期：2011年12月20日一、 實(shí)驗(yàn)名稱、目的及內(nèi)容實(shí)驗(yàn)名稱： 八數(shù)碼難題的搜索求解演示實(shí)驗(yàn)?zāi)康模杭由顚?duì)圖搜索策略概念的理解，掌握搜索算法。實(shí)驗(yàn)內(nèi)容要求：以八數(shù)碼難題為例演示廣度優(yōu)先或深度優(yōu)先搜索、A算法（本實(shí)驗(yàn)使用的是廣度優(yōu)先搜索）的搜索過程，爭(zhēng)取做到直觀、清晰地演示算法。八數(shù)碼難題：在33方格棋盤上，分別放置了標(biāo)有數(shù)字1,2,3,4,5,6,7,8的八張牌，初始狀態(tài)S0，目標(biāo)狀態(tài)如圖所示，可以使用的操作有:空格上移，空格左移，空格右移，空格下移。試編一程序?qū)崿F(xiàn)這一搜索過程。二、實(shí)驗(yàn)原理及基本技術(shù)路線圖實(shí)驗(yàn)原理：八數(shù)碼問題中，程序產(chǎn)生的隨機(jī)排列轉(zhuǎn)換成目標(biāo)共有兩種可能，而且這兩種不可能同時(shí)成立，也就是奇數(shù)排列和偶數(shù)排列。我們可以把一個(gè)隨機(jī)排列的數(shù)組從左到右從上到下用一個(gè)數(shù)組表示，例如，其中代表空格。它在奇序列位置上。在這個(gè)數(shù)組中我們首先計(jì)算它能夠重排列出來的結(jié)果，公式就是：（），其中（），就是一個(gè)數(shù)他前面比這個(gè)數(shù)小的數(shù)的個(gè)數(shù)，為奇數(shù)和偶數(shù)個(gè)有一種解法。那么上面的數(shù)組我們就可以解出它的結(jié)果。數(shù)據(jù)結(jié)構(gòu)：本實(shí)驗(yàn)使用的數(shù)據(jù)結(jié)構(gòu)是隊(duì)列，應(yīng)用隊(duì)列先進(jìn)先出的特點(diǎn)來實(shí)現(xiàn)對(duì)節(jié)點(diǎn)的保存和擴(kuò)展。首先建立一個(gè)隊(duì)列，將初始結(jié)點(diǎn)入隊(duì)，并設(shè)置隊(duì)列頭和尾指，然后取出隊(duì)列（頭指針?biāo)福┑慕Y(jié)點(diǎn)進(jìn)行擴(kuò)展，從它擴(kuò)展出子結(jié)點(diǎn)，并將這些結(jié)點(diǎn)按擴(kuò)展的順序加入隊(duì)列，然后判斷擴(kuò)展出的新結(jié)點(diǎn)與隊(duì)列中的結(jié)點(diǎn)是否重復(fù)，如果重復(fù)則，否則記錄其父結(jié)點(diǎn)，并將它加入隊(duì)列，更新隊(duì)列尾指針，然后判斷擴(kuò)展出的結(jié)點(diǎn)是否是目標(biāo)結(jié)點(diǎn)，如果是則顯示路徑，程序結(jié)束。否則如果隊(duì)列頭的結(jié)點(diǎn)可以擴(kuò)展，直接返回第二步。否則將隊(duì)列頭指針指向下一結(jié)點(diǎn)，再返回第二步，知道擴(kuò)展出的結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn)結(jié)束，并顯示路徑。算法分析：九宮問題的求解方法就是交換空格（）位置，直至到達(dá)目標(biāo)位置為止。如圖所示：2 8316475 8715263487152346 8715263487152346 因此可知：九宮的所以排列有！種，也就是種排法，數(shù)據(jù)量是非常大的，我使用廣度搜索，需要記住每一個(gè)結(jié)點(diǎn)的排列形式，要是用數(shù)組記錄的話會(huì)占用很多的內(nèi)存，我們把數(shù)據(jù)進(jìn)行適當(dāng)?shù)膲嚎s。使用形式保存，壓縮形式是每個(gè)數(shù)字用位表示，這樣就是個(gè)字節(jié)，由于的二進(jìn)制表示形式，不能用位表示，我使用了一個(gè)小技巧就是將表示位，然后用多出來的個(gè)字表示所在的位置，就可以用表示了。用移位和或操作將數(shù)據(jù)逐個(gè)移入，比乘法速度要快點(diǎn)。定義了幾個(gè)結(jié)果來存儲(chǔ)遍歷到了結(jié)果和搜索完成后保存最優(yōu)路徑。算法描述：過程 BREADTH-SEARCH(1) G:=G0(G0=s),OPEN:=(s),CLOSE:=( );(2) LOOP:IF OPEN=( ) THEN EXIT(FAIL);(3) N:=FIRST(OPEN);(4) IF GOAL(n) THEN EXIT(SUCCESS);(5) RENMOVE(n,OPEN),ADD(n,CLOSED);(6) EXPAND(n)mi,G:=ADD(mi,G);(7) 結(jié)點(diǎn)放在OPEN表的后面，使深度淺的結(jié)點(diǎn)可優(yōu)先擴(kuò)展。廣度優(yōu)先搜索的源代碼如下：void Bfs() queue Queue; Queue.push(org); HashTable org.myindex = -1; while( NOT Queue.empty() ) Map node = Queue.front(); Queue.pop(); for(int k =0 ; k 4; k + ) Map tmp = node; tmp.position = node.position + derectionk; if(tmp.position 8 | ( k 1 & tmp.position / 3 != node.position /3 ) ) continue; tmp.myindex = HashValue( node , k ); if(0 != HashTabletmp.myindex ) continue; tmp.detail node.position = tmp.detail tmp.position ; / 移動(dòng)空格 tmp.detail tmp.position = 0 ; HashTabletmp.myindex = node.myindex; / 狀態(tài)記錄到hashtable中 if( node.myindex = EndIndex ) return ; Queue.push( tmp ); return ; 實(shí)驗(yàn)流程圖：開始輸入要排序的08數(shù)碼序列建立一個(gè)隊(duì)列，將初始結(jié)點(diǎn)入隊(duì)，并設(shè)置隊(duì)列頭和尾指針取出隊(duì)列頭（頭指針?biāo)福┑慕Y(jié)點(diǎn)進(jìn)行擴(kuò)展，從它擴(kuò)展出子結(jié)點(diǎn)，并將這些結(jié)點(diǎn)按擴(kuò)展的順序加入隊(duì)列判斷擴(kuò)展出的新結(jié)點(diǎn)與隊(duì)列中的結(jié)點(diǎn)是否重復(fù)結(jié)點(diǎn)，并將這些結(jié)點(diǎn)按擴(kuò)展的順序加入隊(duì)列否記錄其父結(jié)點(diǎn)，并將它加入隊(duì)列，更新隊(duì)列尾指針擴(kuò)展出子結(jié)點(diǎn)，并將這些結(jié)點(diǎn)按擴(kuò)展的順序加入隊(duì)列隊(duì)列頭的結(jié)點(diǎn)可以擴(kuò)展，直接返回第二步。否則將隊(duì)列頭指針指向下一結(jié)點(diǎn)，再返回第二步。判斷擴(kuò)展出的結(jié)點(diǎn)是否是目標(biāo)結(jié)點(diǎn)，是是否顯示路徑程序結(jié)束三、所用儀器、材料（設(shè)備名稱、型號(hào)、規(guī)格等或使用軟件）硬件:個(gè)人計(jì)算機(jī) 軟件: Microsoft Visual C+ 6.0 四、實(shí)驗(yàn)方法、步驟（或：程序代碼或操作過程）1.實(shí)驗(yàn)步驟（1）運(yùn)行Microsoft Visual C+ 6.0軟件，新建工作空間，得文檔。（2）輸入源程序代碼，進(jìn)行編譯，調(diào)試運(yùn)行。（3）運(yùn)行結(jié)果，按提示要求輸入18這八個(gè)數(shù)，進(jìn)行程序測(cè)驗(yàn)。2.實(shí)驗(yàn)源程序#include #include #include #include #include using namespace std; #define HashTableSize 362881 #define NOT ! #define UP 0 #define DOWN 1 #define LEFT 2 #define RIGHT 3 #define Bit char typedef struct maps Bit detail9; int myindex; / 記錄自己節(jié)點(diǎn)在hash表中的位置 Bit position; / 記錄 空格（0）在序列中的位置 Map,*PMap; Map org; / 初始狀態(tài) int EndIndex; /目標(biāo),上移 ，下移 ， 左移 ，右移 int const derection4 = -3 , 3 , -1 , 1 ;/ 可移動(dòng)的四個(gè)方向 int const Factorial9 = 40320 , 5040 , 720 , 120 , 24 , 6 , 2 , 1 , 1 ; int HashTableHashTableSize=0;/hash表,其中記錄的是上一個(gè)父節(jié)點(diǎn)對(duì)應(yīng)的位置 /*八數(shù)碼的輸入（在這里不做任何輸入檢查，均認(rèn)為輸入數(shù)據(jù)是正確的）*/void input() int i,j; int sum , count ,index ; for(i = 0 ; i 9 ; i + ) scanf(%1d, &org.detail i ); org.detail i | (org.position = i) ; for(i = 0 ; i 9 ; i + ) /計(jì)算逆序 if( 0 = org.detail i ) continue; for(j = 0 ; j i; j + ) sum += ( 0 != org.detail j & org.detail j org.detail i ); for( i = 0 , index = 0 ; i 9 ; i + ) / 計(jì)算初始狀態(tài)的hash值 for(j = 0 , count = 0 ; j org.detail i ; index += Factorial org.detail i * count; org.myindex = index + 1 ; EndIndex = sum%2 ? 161328:322561; / 目標(biāo)狀態(tài)的hash值 return; /*hash值的計(jì)算*Parent:父狀態(tài)的hash值*direct:移動(dòng)的方向*/ inline int HashValue(Map& Parent , int& direct ) int i = Parent.position ; int newindex = Parent.myindex ; Bit *p = Parent.detail; switch(direct) case UP : newindex -= 3*40320 ; newindex += ( p i - 2 p i - 3 ) ? ( Factorial p i - 3 ) : ( - Factorial p i - 2 ); newindex += ( p i - 1 p i - 3 ) ? ( Factorial p i - 3 ) : ( - Factorial p i - 1 ); break; case DOWN : newindex += 3*40320 ; newindex -= ( p i + 2 p i + 3 ) ? ( Factorial p i + 3 ) : ( - Factorial p i + 2 ); newindex -= ( p i + 1 p i + 3 ) ? ( Factorial p i + 3 ) : ( - Factorial p i + 1 ); break; case LEFT : return newindex - 40320; break; case RIGHT : return newindex + 40320; break; return newindex; /* * * 廣度優(yōu)先搜索*/ void Bfs() queue Queue; Queue.push(org); HashTable org.myindex = -1; while( NOT Queue.empty() ) Map node = Queue.front(); Queue.pop(); for(int k =0 ; k 4; k + ) Map tmp = node; tmp.position = node.position + derectionk; if(tmp.position 8 | ( k 1 & tmp.position / 3 != node.position /3 ) ) continue; tmp.myindex = HashValue( node , k ); if(0 != HashTabletmp.myindex ) continue; tmp.detail node.position = tmp.detail tmp.position ; / 移動(dòng)空格 tmp.detail tmp.position = 0 ; HashTabletmp.myindex = node.myindex; / 狀態(tài)記錄到hashtable中 if( node.myindex = EndIndex ) return ; Queue.push( tmp ); return ; /* 通過hash表中記錄的進(jìn)行查找路徑*/ void FindPath() int nowindex; int count =0 ; int nixu9, result9; int i, j , k ; stack Stack; Stack.push(EndIndex); nowindex = EndIndex; while( -1 != HashTable nowindex ) Stack.push(HashTable nowindex ); nowindex = HashTable nowindex ; printf(共需： %d 步n,Stack.size()-1); getchar(); while( NOT Stack.empty() nowindex = Stack.top() - 1 ; Stack.pop(); for( i = 0 ; i 9; i + ) / 計(jì)算出逆序 nixui = nowindex / Factorial i ; nowindex %= Factorial i ; memset( result , -1 , 9 *sizeof(int); for( i =0 ; i 9 ; i + ) / 根據(jù)逆序計(jì)算排列 for( j = 0 , k = nixui ; j 9 ; j + ) if(resultj = -1 ) k -; if( k 0 ) break; resultj = i ; for( i =0 ; i 9 ; i + ) printf(%3d,resulti); if( 2 = i % 3 ) printf(n); if(0 != Stack.size() ) printf(n 第%d步n,+count); getchar(); printf(nThe End!n); ret