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

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

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

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

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

5、(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); 結點放在OPENft的后面，使深度淺的結點可優(yōu)先擴展。廣度優(yōu)先搜索的源代碼如下：void Bfs()queue<Map> Queue;Queue.push(org);HashTable org.my

6、index = -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< 0 | tmp.position > 8 | ( k > 1 &&tmp.position / 3 != node.position /3 ) )continue;tmp.myindex = HashValue

7、( 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 ;實驗流程圖:開始#define DOWN 1三、所用儀器、材料（設備名稱、型號、規(guī)

8、格等或使用軟件）硬件: 個人計算機軟件: Microsoft Visual C+ 6.0四、實驗方法、步驟（或：程序代碼或操作過程）1. 實驗步驟（ 1）運行 Microsoft Visual C+ 6.0 軟件，新建工作空間，得文檔。（ 2）輸入源程序代碼，進行編譯，調試運行。（ 3） 運行結果，按提示要求輸入1 8 這八個數(shù)，進行程序測驗。2. 實驗源程序#include <stdio.h>#include <stdlib.h>#include <windows.h>#include <queue>#include <stack>

9、using namespace std;#define HashTableSize#define NOT !#define UP 0#define LEFT 2 #define RIGHT 3#define Bit chartypedef struct mapsBit detail9;int myindex;/ 記錄自己節(jié)點在hash 表中的位置Bit position;/ 記錄 空格（0）在序列中的位置Map,*PMap;Map org;/ 初始狀態(tài)int EndIndex;/ 目標 , 上移 ， 下移 ， 左移 ， 右移int const derection4 = -3 , 3 , -1

10、, 1 ;/ 可移動的四個方向int const Factorial9 = 40320 , 5040 , 720 , 120 , 24 , 6 ,2 , 1 , 1 ;int HashTableHashTableSize=0;/hash 表 , 其中記錄的是上一個父節(jié)點對應的位置/* 八數(shù)碼的輸入（在這里不做任何輸入檢查，均認為輸入數(shù)據是正確的 ） */void input（）int i,j;int sum , count ,index ;for(i = 0 ; i < 9 ; i + )scanf("%1d", &org.detail i );org.det

11、ail 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.detail org.detail i );for( i = 0 , index = 0 ; i < 9 ; i + ) / 計算初始狀態(tài)的hash 值for(j = 0 , count = 0 ; j < i ; j +)count += org.det

12、ail j > org.detail i ;index += Factorial org.detail i * count;org.myindex = index + 1 ;EndIndex = sum%2 ? :;/ 目標狀態(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 = P

13、arent.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

14、 ) ?( 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<Map> Queue;Queue

15、.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 < 0 | tmp.position > 8 | ( k >1 && tmp.position / 3 != node.position /3 ) )cont

16、inue;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

17、表中記錄的進行查找路徑*/void FindPath()int nowindex;int count =0 ;int nixu9, result9;int i, j , k ;stack<int> Stack;Stack.push(EndIndex);nowindex = EndIndex;while( -1 != HashTable nowindex )Stack.push(HashTable nowindex );nowindex = HashTable nowindex ;printf(" 共需： %d 步 n",Stack.size()-1);getch

18、ar();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("nJ 第姓n",+count);getchar();printf("nThe E