八數碼問題實驗報告一、實驗目的：熟練掌握啟發式搜索算法。二、實驗內容：使用啟發式搜索算法求解8數碼問題。編制程序實現求解8數碼問題算法，采用估價函數，其中：是搜索樹中結點的深度；為結點的數據庫中錯放的棋子個數；為結點的數據庫中每個棋子與其目標位置之間的距離總和。三、實驗原理：1. 問題描述：八數碼問題也稱為九宮問題。在33的棋盤，擺有八個棋子，每個棋子上標有1至8的某一數字，不同棋子上標的數字不相同。棋盤上還有一個空格（以數字0來表示），與空格相鄰的棋子可以移到空格中。要求解決的問題是：給出一個初始狀態和一個目標狀態，找出一種從初始轉變成目標狀態的移動棋子步數最少的移動步驟。所謂問題的一個狀態就是棋子在棋盤上的一種擺法。解八數碼問題實際上就是找出從初始狀態到達目標狀態所經過的一系列中間過渡狀態。2. 原理描述：啟發式搜索（1）原理啟發式搜索就是在狀態空間中的搜索對每一個搜索的位置進行評估，得到最好的位置，再從這個位置進行搜索直到目標。這樣可以省略大量無謂的搜索路徑，提高了效率。在啟發式搜索中，對位置的估價是十分重要的。采用了不同的估價可以有不同的效果。（2）估價函數計算一個節點的估價函數，可以分成兩個部分：1、 已經付出的代價（起始節點到當前節點）；2、 將要付出的代價（當前節點到目標節點）。節點n的估價函數定義為從初始節點、經過n、到達目標節點的路徑的最小代價的估計值，即 = + 。是從初始節點到達當前節點n的實際代價； 是從節點n到目標節點的最佳路徑的估計代價。所占的比重越大，越趨向于寬度優先或等代價搜索；反之，的比重越大，表示啟發性能就越強。（3）算法描述： 把起始節點S放到OPEN表中，并計算節點S的； 如果OPEN是空表，則失敗退出，無解； 從OPEN表中選擇一個值最小的節點。如果有幾個節點值相同，當其中有一個為目標節點時，則選擇此目標節點；否則就選擇其中任一個節點作為節點； 把節點從 OPEN 表中移出，并把它放入 CLOSED 的已擴展節點表中； 如果是個目標節點，則成功退出，求得一個解； 擴展節點，生成其全部后繼節點。對于的每一個后繼節點：計算；如果 既不在OPEN表中，又不在CLOCED表中，則用估價函數把它添入OPEN表中。從加一指向其父節點的指針，以便一旦找到目標節點時記住一個解答路徑；如果已在OPEN表或CLOSED表中，則比較剛剛對計算過的和前面計算過的該節點在表中的值。如果新的較小，則(I)以此新值取代舊值。(II)從指向，而不是指向他的父節點。(III)如果節點在CLOSED表中，則把它移回OPEN表中。 轉向，即GOTO。（3） 算法流程圖：4、 實驗結果輸入矩陣： 目標矩陣：2831231458047607655、 實驗小結通過本次試驗，我對啟發式搜索有了更加深入的了解。在實驗中，通過對兩種啟發式搜索所擴在的節點數來看，看來比更加有效，能在復雜情況下求得更加優質的解，避免不必要的節點的擴展。所以，要更好地定義一個估價函數還有待深入討論。源代碼：#includestdio.h#define num 3 /宏定義數碼的行列數為3/*顯示當前待調整數碼矩陣*/void show(int beginnumnum) for(int i = 0; i num; i+)for(int j = 0; j num; j+)printf(%d , beginij);printf(n);printf(n);/*交換數碼中的 beginrow_onecolumn_one 與 beginrow_twocolumn_two 這兩個數*/void exchange(int beginnumnum, int row_one, int column_one, int row_two, int column_two) int temp;temp = beginrow_twocolumn_two ;beginrow_twocolumn_two = beginrow_onecolumn_one;beginrow_onecolumn_one = temp;/*判斷待調整的數碼與最終數碼相比正確位置數碼的個數*/int judge(int beginnumnum, int endnumnum) int count=0; /count記錄數碼中正確位置的個數for(int i = 0; i num; i+) /檢查當前圖形的正確度for(int j = 0; j = 20)return 0;int node; /,node為標記int temp; /存儲當前待調整數碼正確的個數 for(int q=0; qjishu; q+) /檢查交換后的end圖形是否先前已經遍歷過了node = 1;for(int w=0; wnum & node; w+)for(int r=0; rnum & node; r+)if(ji_shuqwr != beginwr)node = 0;if(node = 1) /如果先前遍歷過，返回0 return 0;for(int i = 0; i num; i+) for(int j = 0; j 0 & biaoji != 0) /存儲0的位置不是在第一行exchange(begin, row - 1, column, row , column); /將0與其上面的元素交換存儲位置temp = judge(begin, end); if(temp = right) /如果交換后正確數碼的個數大于或等于原來正確數碼的個數temp_zhi = yidong(begin, end, temp, jishu+1, ji_shu, 2, row-1, column); if( temp_zhi = 1) /進行下一步的移動 return 1;exchange(begin, row - 1, column, row , column); /再將其交換回來if(column 0 & biaoji != 1) exchange(begin, row, column - 1, row , column); /將0與其左邊的元素交換存儲位置temp = judge(begin, end);if(temp = right)temp_zhi = yidong(begin, end, temp, jishu+1, ji_shu ,3, row, column - 1); if(temp_zhi = 1) return 1;exchange(begin, row, column - 1, row , column);if(row num-1 & biaoji != 2) exchange(begin, row + 1, column, row , column); /將0與其下面的元素交換存儲位置temp = judge(begin, end);if(temp = right)temp_zhi =yidong(begin, end, temp, jishu+1, ji_shu, 0, row+1, column); if(temp_zhi = 1) return 1; exchange(begin, row + 1, column, row , column);if(column num-1 & biaoji != 3) exchange(begin, row, column + 1, row , column); /將0與其右邊的元素交換存儲位置temp = judge(begin, end);if(temp = right) temp_zhi = yidong(begin, end, temp, jishu+1, ji_shu, 1, row, column+1);if(temp_zhi = 1) return 1;exchange(begin, row, column + 1, row , column);return 0; /移動失敗，返回0/*有用戶輸入待調整的數碼矩陣最初狀態的數，并將其存入到begin數組中*/void shuru(int beginnum,int blank) int temp, node, zero = 0;for (int i = 0; i num; i+)for(int j = 0; j num; j+)node = 1;printf(請輸入第%d行，第%d列的元素的值：, i+1, j+1); scanf(%d, &temp);for (int q = 0; q = i & node = 1; q+) /當輸入的值有重復的，提示重新輸入for (int w = 0; w j; w+)if(temp = beginqw)printf(輸入重復，請重新輸入n);node = 0;j-;break;if(temp num*num-1) /當輸入的值不是在數碼的區間范圍內時，提示重新輸入printf(請輸入從%d到%d的數n, zero, num*num-1);node = 0; j-;if(node = 1) /如果輸入滿足條件if(temp = 0) /如果輸入的值為零，由blank0記錄行號，blank1記錄列號blank0 = i;blank1 = j;beginij = temp;/將滿足條件的值存儲起來int main()int jishu = 0, ji_shu5033;/jishu存儲已經遍歷過的八數碼圖形的個數，jishu存儲已經遍歷過的八數碼圖形的形狀 int row; /存儲數字零的行數 int column; /存儲數字零的列數int beginnumnum, blank2,count=1; int endnumnum = 1, 2, 3, 8, 0, 4, 7, 6, 5; /給最終狀態的數碼矩陣賦值 printf (-%d數碼游戲開