1、1實 驗 報 告實驗名稱：實驗名稱：8 8 位數碼難題的問題求解位數碼難題的問題求解實驗目的和要求：實驗目的和要求：目的：目的：1.1.理解和掌握解決實際問題的搜索算法或策略；理解和掌握解決實際問題的搜索算法或策略；2.2.能夠用選定的編程語言實現搜索算法；能夠用選定的編程語言實現搜索算法；要求：要求：1.1.隨機輸入隨機輸入 1-81-8 數字；數字；2.2.采用所學過的搜索算法采用所學過的搜索算法（算法不限算法不限，但需要有注釋但需要有注釋，采用算法之采用算法之一，或幾種算法實現）；一，或幾種算法實現）；3.3.要求輸出算法執行的過程結果；要求輸出算法執行的過程結果；4.4.按順序輸出按順

2、序輸出 1-81-8 數字；數字；實驗軟硬件要求：網絡計算機，實驗軟硬件要求：網絡計算機，c+c+編程環境編程環境實驗內容、方法和步驟（可附頁）實驗內容、方法和步驟（可附頁）我們將八數碼難題分布在我們將八數碼難題分布在 3 33 3 方格棋盤上，分別放置了標有數方格棋盤上，分別放置了標有數字字1,2,3,4,5,6,7,81,2,3,4,5,6,7,8 的八張牌，初始狀態的八張牌，初始狀態 S0S0，目標狀態如圖所示，可以使，目標狀態如圖所示，可以使用的操作有用的操作有: :空格上移空格上移，空格左移空格左移，空格右移空格右移，空格下移空格下移。我們將是用廣我們將是用廣度優先搜索算法來解決這一

3、問題。度優先搜索算法來解決這一問題。我們先擬定初始數列為我們先擬定初始數列為 0 0 3 3 5 5 2 2 1 1 4 4 8 8 7 7 6 6（0 0 表示空位）表示空位）2算法流程圖：初始狀態算法流程圖：初始狀態35214876結果結果數據結構：數據結構：本實驗使用的數據結構是隊列，應用隊列先進先出的特點來實現本實驗使用的數據結構是隊列，應用隊列先進先出的特點來實現對節點的保存和擴展。對節點的保存和擴展。首先首先建立一個隊列，將初始結點入隊，并設置隊建立一個隊列，將初始結點入隊，并設置隊列頭和尾指列頭和尾指，然后，然后取出隊列（頭指針所指）的結點進行擴展，從它擴展取出隊列（頭指針所指）

4、的結點進行擴展，從它擴展出子結點，并將這些結點按擴展的順序加入隊列出子結點，并將這些結點按擴展的順序加入隊列，然后判斷，然后判斷擴展出的新擴展出的新結點與隊列中的結點結點與隊列中的結點是否是否重復重復，如果重復則，否則，如果重復則，否則記錄其父結點，并將記錄其父結點，并將它加入隊列它加入隊列， 更新隊列尾指針更新隊列尾指針， 然后判斷然后判斷擴展出的結點是擴展出的結點是否是否是目標結點目標結點，如果是則顯示路徑，程序結束。否則如果如果是則顯示路徑，程序結束。否則如果隊列頭的結點可以擴展，直接隊列頭的結點可以擴展，直接返回第二步。否則將隊列頭指針指向下一結點，再返回第二步返回第二步。否則將隊列頭

5、指針指向下一結點，再返回第二步，知道擴，知道擴展出的結點是目標結點結束，并顯示路徑。展出的結點是目標結點結束，并顯示路徑。123847653代碼如下：代碼如下：#include #include #include #include #include using namespace std;#define HashTableSize 362881#define NOT!#define UP0#define DOWN1#define LEFT2#define RIGHT3#define Bitchartypedef struct mapsBit detail9;int myindex;/ 記錄自己

6、節點在記錄自己節點在 hash 表中的位置表中的位置Bit position;/ 記錄記錄 空格（空格（0）在序列中的位置）在序列中的位置Map,*PMap;Maporg;/初始狀態初始狀態intEndIndex;/目標目標,上移上移 ，下移，下移 ，左移左移，右移，右移4int const derection4 = -3,3,-1,1 ;/ 可移動的四個方向可移動的四個方向int const Factorial9 = 40320 , 5040 , 720 , 120 , 24, 6 , 2 , 1 , 1 ;intHashTableHashTableSize=0;/hash 表表,其中記其中

7、記錄的是上一個父節點對應的位置錄的是上一個父節點對應的位置/*八數碼的輸入八數碼的輸入（在這里不做任何輸入檢查在這里不做任何輸入檢查，均認為輸入數據是均認為輸入數據是正確的）正確的）*/void input()int i,j;int sum , count ,index ;printf(輸入九個數輸入九個數： n);/必須輸入一個必須輸入一個 0 作為空作為空值值for(i = 0 ; i 9 ; i + )scanf(%1d, &org.detail i );org.detail i | (org.position = i) ;for(i = 0 ; i 9 ; i + )/計算逆序

8、計算逆序5if( 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

9、 ? 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;6switch(direct)case UP:newindex -= 3*40320 ;newindex += ( p i

10、- 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 ) ?( Fac

11、torial p i + 3 ) : ( - Factorial p i + 1 );break;case LEFT:return newindex - 40320; break;case RIGHT :return newindex + 40320; break;7return newindex;/* * *廣度優先搜索廣度優先搜索*/void Bfs()queue Queue;Queue.push(org);HashTable org.myindex = -1;while( NOT Queue.empty() )Map node= Queue.front();Queue.pop();for

12、(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 ;8/ 移動空格移動空格tm

13、p.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);nowi

14、ndex = EndIndex;while( -1 != HashTable nowindex )9Stack.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

15、%= 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 ;10for( 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(nFinish!n);return ;int main()input();/輸入要排序的序列輸入要排序的序列 0-8long time =GetTickCount();Bfs();pr