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

人工智能實驗報告 學 院：信息科學與工程學院班 級： 自動化0901班 學 號： 0909090316 姓 名： 孫錦崗指導老師： 劉麗玨 日 期：2011年12月20日一、 實驗名稱、目的及內(nèi)容實驗名稱： 八數(shù)碼難題的搜索求解演示實驗目的：加深對圖搜索策略概念的理解，掌握搜索算法。實驗內(nèi)容要求：以八數(shù)碼難題為例演示廣度優(yōu)先或深度優(yōu)先搜索、A算法（本實驗使用的是廣度優(yōu)先搜索）的搜索過程，爭取做到直觀、清晰地演示算法。八數(shù)碼難題：在33方格棋盤上，分別放置了標有數(shù)字1,2,3,4,5,6,7,8的八張牌，初始狀態(tài)S0，目標狀態(tài)如圖所示，可以使用的操作有:空格上移，空格左移，空格右移，空格下移。試編一程序?qū)崿F(xiàn)這一搜索過程。二、實驗原理及基本技術(shù)路線圖實驗原理：八數(shù)碼問題中，程序產(chǎn)生的隨機排列轉(zhuǎn)換成目標共有兩種可能，而且這兩種不可能同時成立，也就是奇數(shù)排列和偶數(shù)排列。我們可以把一個隨機排列的數(shù)組從左到右從上到下用一個數(shù)組表示，例如，其中代表空格。它在奇序列位置上。在這個數(shù)組中我們首先計算它能夠重排列出來的結(jié)果，公式就是：（），其中（），就是一個數(shù)他前面比這個數(shù)小的數(shù)的個數(shù)，為奇數(shù)和偶數(shù)個有一種解法。那么上面的數(shù)組我們就可以解出它的結(jié)果。數(shù)據(jù)結(jié)構(gòu)：本實驗使用的數(shù)據(jù)結(jié)構(gòu)是隊列，應用隊列先進先出的特點來實現(xiàn)對節(jié)點的保存和擴展。首先建立一個隊列，將初始結(jié)點入隊，并設置隊列頭和尾指，然后取出隊列（頭指針所指）的結(jié)點進行擴展，從它擴展出子結(jié)點，并將這些結(jié)點按擴展的順序加入隊列，然后判斷擴展出的新結(jié)點與隊列中的結(jié)點是否重復，如果重復則，否則記錄其父結(jié)點，并將它加入隊列，更新隊列尾指針，然后判斷擴展出的結(jié)點是否是目標結(jié)點，如果是則顯示路徑，程序結(jié)束。否則如果隊列頭的結(jié)點可以擴展，直接返回第二步。否則將隊列頭指針指向下一結(jié)點，再返回第二步，知道擴展出的結(jié)點是目標結(jié)點結(jié)束，并顯示路徑。算法分析：九宮問題的求解方法就是交換空格（）位置，直至到達目標位置為止。如圖所示：2 8316475 8715263487152346 8715263487152346 因此可知：九宮的所以排列有！種，也就是種排法，數(shù)據(jù)量是非常大的，我使用廣度搜索，需要記住每一個結(jié)點的排列形式，要是用數(shù)組記錄的話會占用很多的內(nèi)存，我們把數(shù)據(jù)進行適當?shù)膲嚎s。使用形式保存，壓縮形式是每個數(shù)字用位表示，這樣就是個字節(jié)，由于的二進制表示形式，不能用位表示，我使用了一個小技巧就是將表示位，然后用多出來的個字表示所在的位置，就可以用表示了。用移位和或操作將數(shù)據(jù)逐個移入，比乘法速度要快點。定義了幾個結(jié)果來存儲遍歷到了結(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é)點放在OPEN表的后面，使深度淺的結(jié)點可優(yōu)先擴展。廣度優(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 ; / 移動空格 tmp.detail tmp.position = 0 ; HashTabletmp.myindex = node.myindex; / 狀態(tài)記錄到hashtable中 if( node.myindex = EndIndex ) return ; Queue.push( tmp ); return ; 實驗流程圖：開始輸入要排序的08數(shù)碼序列建立一個隊列，將初始結(jié)點入隊，并設置隊列頭和尾指針取出隊列頭（頭指針所指）的結(jié)點進行擴展，從它擴展出子結(jié)點，并將這些結(jié)點按擴展的順序加入隊列判斷擴展出的新結(jié)點與隊列中的結(jié)點是否重復結(jié)點，并將這些結(jié)點按擴展的順序加入隊列否記錄其父結(jié)點，并將它加入隊列，更新隊列尾指針擴展出子結(jié)點，并將這些結(jié)點按擴展的順序加入隊列隊列頭的結(jié)點可以擴展，直接返回第二步。否則將隊列頭指針指向下一結(jié)點，再返回第二步。判斷擴展出的結(jié)點是否是目標結(jié)點，是是否顯示路徑程序結(jié)束三、所用儀器、材料（設備名稱、型號、規(guī)格等或使用軟件）硬件:個人計算機 軟件: Microsoft Visual C+ 6.0 四、實驗方法、步驟（或：程序代碼或操作過程）1.實驗步驟（1）運行Microsoft Visual C+ 6.0軟件，新建工作空間，得文檔。（2）輸入源程序代碼，進行編譯，調(diào)試運行。（3）運行結(jié)果，按提示要求輸入18這八個數(shù)，進行程序測驗。2.實驗源程序#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é)點在hash表中的位置 Bit position; / 記錄 空格（0）在序列中的位置 Map,*PMap; Map org; / 初始狀態(tài) int EndIndex; /目標,上移 ，下移 ， 左移 ，右移 int const derection4 = -3 , 3 , -1 , 1 ;/ 可移動的四個方向 int const Factorial9 = 40320 , 5040 , 720 , 120 , 24 , 6 , 2 , 1 , 1 ; int HashTableHashTableSize=0;/hash表,其中記錄的是上一個父節(jié)點對應的位置 /*八數(shù)碼的輸入（在這里不做任何輸入檢查，均認為輸入數(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 + ) /計算逆序 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 + ) / 計算初始狀態(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; / 目標狀態(tài)的hash值 return; /*hash值的計算*Parent:父狀態(tài)的hash值*direct:移動的方向*/ 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 ; / 移動空格 tmp.detail tmp.position = 0 ; HashTabletmp.myindex = node.myindex; / 狀態(tài)記錄到hashtable中 if( node.myindex = EndIndex ) return ; Queue.push( tmp ); return ; /* 通過hash表中記錄的進行查找路徑*/ 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 + ) / 計算出逆序 nixui = nowindex / Factorial i ; nowindex %= Factorial i ; memset( result , -1 , 9 *sizeof(int); for( i =0 ; i 9 ; i + ) / 根據(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