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