資源描述:
《人工智能實(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