八數(shù)碼算法解析

（一）問題描述在一個(gè)3*3的方棋盤上放置著123,4,5,6,7,8八個(gè)數(shù)碼，每個(gè)數(shù)碼占一格，且有一個(gè)空格。這些數(shù)碼可以在棋盤上移動(dòng)，其移動(dòng)規(guī)則是：與空格相鄰的數(shù)碼方格可以移入空格?，F(xiàn)在的問題是：對(duì)于指定的初始棋局和目標(biāo)棋局，給出數(shù)碼的移動(dòng)序列。該問題稱八數(shù)碼難題或者重排九宮問題。（二） 啟發(fā)式搜索由八數(shù)碼問題的部分狀態(tài)圖可以看出，從初始節(jié)點(diǎn)開始，在通向目標(biāo)節(jié)點(diǎn)的路徑上，各節(jié)點(diǎn)的數(shù)碼格局同目標(biāo)節(jié)點(diǎn)相比較，其數(shù)碼不同的位置個(gè)數(shù)在逐漸減少，最后為零。所以，這個(gè)數(shù)碼不同的位置個(gè)數(shù)便是標(biāo)志一個(gè)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)距離遠(yuǎn)近的一個(gè)啟發(fā)性信息，利用這個(gè)信息就可以指導(dǎo)搜索。即可以利用啟發(fā)信息來擴(kuò)展節(jié)點(diǎn)的選擇，減少搜索范圍，提高搜索速度。啟發(fā)函數(shù)設(shè)定。對(duì)于八數(shù)碼問題，可以利用棋局差距作為一個(gè)度量。搜索過程中，差距會(huì)逐漸減少，最終為零，為零即搜索完成，得到目標(biāo)棋局。（三） 搜索過程描述搜索采用廣度搜索方式，利用待處理隊(duì)列輔助，逐層搜索（跳過劣質(zhì)節(jié)點(diǎn)）。搜索過程如下：（1） 、把原棋盤壓入隊(duì)列；（2） 、從棋盤取出一個(gè)節(jié)點(diǎn)；（3） 、判斷棋盤估價(jià)值，為零則表示搜索完成，退岀搜索；（4） 、擴(kuò)展子節(jié)點(diǎn)，即從上下左右四個(gè)方向移動(dòng)棋盤，生成相應(yīng)子棋盤；（5）、對(duì)子節(jié)點(diǎn)作評(píng)估，是否為優(yōu)越節(jié)點(diǎn)（子節(jié)點(diǎn)估價(jià)值小于或等于父節(jié)點(diǎn)則為優(yōu)越節(jié)點(diǎn)），是則把子棋盤壓入隊(duì)列，否則拋棄；（6）、跳到步驟（2）；

下一步可以通過啟發(fā)搜索算法構(gòu)造搜索樹。局部搜索樹樣例:□□00a□□□HrHH□□L00□□□0□H□0□S□0□□N算法的評(píng)價(jià)：1、可以改變數(shù)碼規(guī)模（N）,來擴(kuò)展成N*N的棋盤，即擴(kuò)展為N數(shù)碼問題的求解過程。2、內(nèi)存泄漏。由于采用倒鏈表的搜索樹結(jié)構(gòu)，簡(jiǎn)化了數(shù)據(jù)結(jié)構(gòu)，但有部分被拋棄節(jié)點(diǎn)的內(nèi)存沒有很好的處理，所以會(huì)造成內(nèi)存泄漏;3、采用了屏蔽方向，有效防止往回搜索（