資源描述：
《人工智能實(shí)驗(yàn)報(bào)告,包括八數(shù)碼問(wèn)題八皇后問(wèn)題和tsp問(wèn)題.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、八數(shù)碼問(wèn)題（一）問(wèn)題描述在一個(gè)3*3的方棋盤(pán)上放置著1,2,3,4,5,6,7,8八個(gè)數(shù)碼,每個(gè)數(shù)碼占一格,且有一個(gè)空格。這些數(shù)碼可以在棋盤(pán)上移動(dòng)，其移動(dòng)規(guī)則是：與空格相鄰的數(shù)碼方格可以移入空格?，F(xiàn)在的問(wèn)題是：對(duì)于指定的初始棋局和目標(biāo)棋局，給出數(shù)碼的移動(dòng)序列。該問(wèn)題稱(chēng)八數(shù)碼難題或者重排九宮問(wèn)題。（二）問(wèn)題分析八數(shù)碼問(wèn)題是個(gè)典型的狀態(tài)圖搜索問(wèn)題。搜索方式有兩種基本的方式，即樹(shù)式搜索和線式搜索。搜索策略大體有盲目搜索和啟發(fā)式搜索兩大類(lèi)。盲目搜索就是無(wú)“向?qū)А钡乃阉鳎瑔l(fā)式搜索就是有“向?qū)А钡乃阉鳌?、啟發(fā)式搜索由于時(shí)間和空間資源
2、的限制，窮舉法只能解決一些狀態(tài)空間很小的簡(jiǎn)單問(wèn)題，而對(duì)于那些大狀態(tài)空間的問(wèn)題，窮舉法就不能勝任，往往會(huì)導(dǎo)致“組合爆炸”。所以引入啟發(fā)式搜索策略。啟發(fā)式搜索就是利用啟發(fā)性信息進(jìn)行制導(dǎo)的搜索。它有利于快速找到問(wèn)題的解。由八數(shù)碼問(wèn)題的部分狀態(tài)圖可以看出，從初始節(jié)點(diǎn)開(kāi)始，在通向目標(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ā)信息來(lái)擴(kuò)展節(jié)點(diǎn)的選擇，減少搜索范圍，提高搜索
3、速度。?啟發(fā)函數(shù)設(shè)定。對(duì)于八數(shù)碼問(wèn)題，可以利用棋局差距作為一個(gè)度量。搜索過(guò)程中，差距會(huì)逐漸減少，最終為零，為零即搜索完成，得到目標(biāo)棋局。（三）數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)該搜索為一個(gè)搜索樹(shù)。為了簡(jiǎn)化問(wèn)題，搜索樹(shù)節(jié)點(diǎn)設(shè)計(jì)如下：structChess//棋盤(pán){??????intcell[N][N];//數(shù)碼數(shù)組??????intValue;//評(píng)估值??????DirectionBelockDirec;//所屏蔽方向??????structChess*Parent;//父節(jié)點(diǎn)};intcell[N][N];???數(shù)碼數(shù)組：記錄棋局?jǐn)?shù)碼擺放
4、狀態(tài)。intValue;???????評(píng)估值：記錄與目標(biāo)棋局差距的度量值。DirectionBelockDirec;所屏蔽方向：一個(gè)屏蔽方向，防止回推。Direction：enumDirection{None,Up,Down,Left,Right};//方向枚舉structChess*Parent;?父節(jié)點(diǎn)：指向父親節(jié)點(diǎn)。下一步可以通過(guò)啟發(fā)搜索算法構(gòu)造搜索樹(shù)。1、局部搜索樹(shù)樣例：2、搜索過(guò)程?搜索采用廣度搜索方式，利用待處理隊(duì)列輔助，逐層搜索（跳過(guò)劣質(zhì)節(jié)點(diǎn)）。搜索過(guò)程如下：?（1）、把原棋盤(pán)壓入隊(duì)列；?（2）、從棋盤(pán)取出一個(gè)
5、節(jié)點(diǎn)；?（3）、判斷棋盤(pán)估價(jià)值，為零則表示搜索完成，退出搜索；?（4）、擴(kuò)展子節(jié)點(diǎn)，即從上下左右四個(gè)方向移動(dòng)棋盤(pán)，生成相應(yīng)子棋盤(pán)；（5）、對(duì)子節(jié)點(diǎn)作評(píng)估，是否為優(yōu)越節(jié)點(diǎn)（子節(jié)點(diǎn)估價(jià)值小于或等于父節(jié)點(diǎn)則為優(yōu)越節(jié)點(diǎn)），是則把子棋盤(pán)壓入隊(duì)列，否則拋棄；?（5）、跳到步驟（2）；3、算法的評(píng)價(jià)完全能解決簡(jiǎn)單的八數(shù)碼問(wèn)題，但對(duì)于復(fù)雜的八數(shù)碼問(wèn)題還是無(wú)能為力?，F(xiàn)存在的一些優(yōu)缺點(diǎn)。1、可以改變數(shù)碼規(guī)模（N），來(lái)擴(kuò)展成N*N的棋盤(pán)，即擴(kuò)展為N數(shù)碼問(wèn)題的求解過(guò)程。2、?3、?采用了屏蔽方向，有效防止往回搜索（節(jié)點(diǎn)的回推），但沒(méi)能有效防止循環(huán)搜索，所以不能應(yīng)用于復(fù)雜度較大的八數(shù)碼問(wèn)題；源碼：#include"stdio.h"#include"stdlib.h"#include"time.h"#include"string.h"#include#includeusingname
7、spacestd;constintN=3;//3*3棋盤(pán)constintMax_Step=30;//最大搜索深度enumDirection{None,Up,Down,Left,Right};//方向structChess//棋盤(pán){???intcell[N][N];//數(shù)碼數(shù)組???intValue;//評(píng)估值???DirectionBelockDirec;//所屏蔽方向???structChess*Parent;//父節(jié)點(diǎn)};//打印棋盤(pán)voidPrintChess(structChess*TheChess){???prin
8、tf("------------------------------------------------------------------------");???for(inti=0;i
