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

1、人工智能實驗報告學院：信息科學與工程學院班級：自動化 0901 班學號：姓名：孫錦崗指導老師：劉麗玨日期：2011 年 12 月 20 日實驗名稱、目的及內(nèi)容實驗名稱：八數(shù)碼難題的搜索求解演示實驗目的：加深對圖搜索策略概念的理解，掌握搜索算法。實驗內(nèi)容要求：以八數(shù)碼難題為例演示廣度優(yōu)先或深度優(yōu)先搜索、 A 算法（本實 驗使用的是廣度優(yōu)先搜索）的搜索過程，爭取做到直觀、清晰地演示 算法。八數(shù)碼難題：在3 X 3方格棋盤上，分別放置了標有數(shù)字123,4,5,6,7,8的八張牌，初始狀態(tài)SO,目標狀態(tài)如圖所示，可以使用的操作有 : 空格上移，空格左移，空格右移，空格下移。試編一 程序?qū)崿F(xiàn)這一搜索過程

2、。二、實驗原理及基本技術(shù)路線圖實驗原理：八數(shù)碼問題中,程序產(chǎn)生的隨機排列轉(zhuǎn)換成目標共有兩種可能,而 且這兩種不可能同時成立,也就是奇數(shù)排列和偶數(shù)排列。我們可以把 一個隨機排列的數(shù)組從左到右從上到下用一個數(shù)組表示，例如8,7,1,5,2,6,3,4,0其中0代表空格。它在奇序列位 置上。在這個數(shù)組中我們首先計算它能夠重排列出來的結(jié)果，公式就是：刀 (F(X)=Y，其中F (X),就是一個數(shù)他前面比這個數(shù)小的 數(shù)的個數(shù)，Y為奇數(shù)和偶數(shù)個有一種解法。那么上面的數(shù)組我們就可 以解出它的結(jié)果。數(shù)據(jù)結(jié)構(gòu)：本實驗使用的數(shù)據(jù)結(jié)構(gòu)是隊列，應(yīng)用隊列先進先出的特點來實 現(xiàn)對節(jié)點的保存和擴展。首先建立一個隊列，將初始

3、結(jié)點入隊，并設(shè) 置隊列頭和尾指，然后取出隊列(頭指針所指)的結(jié)點進行擴展，從 它擴展出子結(jié)點，并將這些結(jié)點按擴展的順序加入隊列， 然后判斷擴 展出的新結(jié)點與隊列中的結(jié)點是否重復， 如果重復則，否則記錄其父 結(jié)點，并將它加入隊列，更新隊列尾指針，然后判斷擴展出的結(jié)點是 否是目標結(jié)點，如果是則顯示路徑，程序結(jié)束。否則如果隊列頭的結(jié) 點可以擴展，直接返回第二步。否則將隊列頭指針指向下一結(jié)點，再 返回第二步，知道擴展出的結(jié)點是目標結(jié)點結(jié)束，并顯示路徑。算法分析：九宮問題的求解方法就是交換空格(0)位置，直至到達目標位置為止。如圖所示:2 8316475871526348715 I2I 63487152

4、34687152346因此可知：九宮的所以排列有9!種，也就是種排法，數(shù)據(jù)量是 非常大的，我使用廣度搜索，需要記住每一個結(jié)點的排列形式，要是 用數(shù)組記錄的話會占用很多的內(nèi)存，我們把數(shù)據(jù)進行適當?shù)膲嚎s。使 用DWORD形式保存，壓縮形式是每個數(shù)字用3位表示，這樣就是 3X9 = 27個字節(jié)，由于8的二進制表示形式1 0 0 0,不能用3 位表示，我使用了一個小技巧就是將8表示位0 0 0,然后用多出來 的5個字表示8所在的位置，就可以用DWORD表示了。用移位和 或操作將數(shù)據(jù)逐個移入，比乘法速度要快點。定義了幾個結(jié)果來存儲 遍歷到了結(jié)果和搜索完成后保存最優(yōu)路徑。算法描述：過程 BREADTH-S

5、EARCH(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(nmi,G:二ADD(mi,G); 結(jié)點放在OPEN表的后面，使深度淺的結(jié)點可優(yōu)先擴展。廣度優(yōu)先搜索的源代碼如下：void Bfs() queue Queue; Queue.push(org); HashTable org.myindex = -

6、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 ) con

7、tinue; 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 ;實驗流程圖:三、所用儀器、材料（設(shè)備名稱、型號、規(guī)格等或使用軟件）硬件: 個人計算機軟件 : Microsoft Visual C+ 6.0 四、實驗方法、步驟（或：程

8、序代碼或操作過程）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#define NOT !#define UP 0#define DOWN 1#define LEFT 2 #define RIGHT 3 #define Bit char typedef

9、 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 表

10、 , 其中記錄的是上一個父節(jié)點對應(yīng)的位置/* 八數(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) ;/ 計算逆序org.detail j for(i = 0 ; i 9 ; i + )if( 0 = org.detail i )continue;for(j = 0 ; j i; j + )sum += ( 0 != org.

11、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 ? :;/ 目標狀態(tài)的 hash 值移動的方向 */ p i - 3 ) ?return;/*hash 值的計算 *Parent: 父狀態(tài)的 hash 值 *direct: inline int Ha

12、shValue(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 ( Factorial p i - 3 ) : ( - Factorial

13、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; b

14、reak;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.p

15、osition /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 );

16、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()

17、;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;re

18、sultj = i ;for( i =0 ; i 9 ; i + )printf(%3d,resulti);if( 2 = i % 3 ) printf(n);if(0 != Stack.size() )printf(nJ 第眇n,+count);getchar();printf(nThe End!n);return ;int main()input(); / 輸入要排序的序列 0-8long time =GetTickCount();Bfs();printf( 計算用時： %dMSn,GetTickCount()-time);FindPath();return 0; / 返回結(jié)果五、實驗過程原始記錄 ( 測試數(shù)據(jù)、圖表、計算等 )結(jié)