八數(shù)碼問題實(shí)驗(yàn)報(bào)告.doc

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