八數(shù)碼實(shí)驗(yàn)報(bào)告人工智能課設(shè)報(bào)告

1、2402070333 張輝學(xué)生實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)課名稱(chēng)：人工智能 實(shí)驗(yàn)名 稱(chēng) : 八數(shù)碼專(zhuān) 業(yè) 名 稱(chēng)：計(jì)算機(jī)科學(xué)與技術(shù)班 級(jí)：學(xué) 號(hào)：學(xué) 生 姓 名： 教 師 姓 名： 2010 年 10 月 20日 一 實(shí)驗(yàn)內(nèi)容 用open表和closed表解決搜索問(wèn)題。二實(shí)驗(yàn)題目 采用啟發(fā)式算法（如a*算法）求解八數(shù)碼問(wèn)題。三實(shí)驗(yàn)要求1. 必須使用open表和closed表。2. 明確給出問(wèn)題描述。系統(tǒng)初始狀態(tài)。目標(biāo)狀態(tài)和啟發(fā)式函數(shù)。3. 除了初始狀態(tài)以外，至少搜索四層。4. 給出解路徑（解圖）。四 實(shí)驗(yàn)過(guò)程 問(wèn)題：初始狀態(tài)到目標(biāo)狀態(tài)是否可解如何判斷？ 答：實(shí)驗(yàn)過(guò)程自己給出的初始狀態(tài)使用a*算法求解，并不是所

2、有的初始狀態(tài)都可解到達(dá)目標(biāo)狀態(tài)。因?yàn)榘藬?shù)碼問(wèn)題其實(shí)是09的一個(gè)排列，而排列有奇排列和偶排列，從奇排列不能轉(zhuǎn)化為偶排列或者相反。例如： 函數(shù)f(s)表示s前比s小的數(shù)字的數(shù)目（s不等于0）.13428657則f(7)=6, f(5)=4,f(6)=4,f(8)=4,f(2)=1,f(4)=2,f(3)=1,f(1)=0當(dāng)f(a8)+f(a7)+f(a1)為偶數(shù)時(shí)才能重排成，所以嘛,上面那個(gè)有解的.問(wèn)題描述：在3x3的九宮格棋盤(pán)上，擺有8個(gè)將牌，每一個(gè)將牌都刻有18數(shù)碼中的某一個(gè)數(shù)碼。棋盤(pán)中留有一個(gè)空格，允許周?chē)哪骋粋€(gè)將牌向空格移動(dòng)，這樣通過(guò)移動(dòng)將牌就可以不斷地改變將牌的布局。這種游戲的求解的問(wèn)

3、題是：給定一種處世的將牌布局或結(jié)構(gòu)和一個(gè)目標(biāo)的布局，問(wèn)如何移動(dòng)將牌，實(shí)現(xiàn)從從初始狀態(tài)到目標(biāo)狀態(tài)的轉(zhuǎn)變。下面給出初始狀態(tài)和目標(biāo)狀態(tài)：28316475初始狀態(tài)：12384765 目標(biāo)狀態(tài)： 評(píng)價(jià)函數(shù)f(n)形式為：f(n)=g(n)+h(n),其中g(shù)(n)是節(jié)點(diǎn)所處的深度，h(n)是啟發(fā)式函數(shù)，這里啟發(fā)式函數(shù)h(n)表示“不在位”的將牌個(gè)數(shù)，這時(shí)f(n)可估計(jì)出通向目標(biāo)結(jié)點(diǎn)的希望的程度。注意：移動(dòng)規(guī)則為左-à上à右à下。搜索過(guò)程：如下圖-1為八數(shù)碼問(wèn)題的搜索樹(shù)：s(4)圖-128s0316475s1s3283164752831647528314765s2a(6)b(4

4、)c(6)s4s628314765s52318476528314765d(5)f(6)e(5)s7s8s9s108g(6)321476528h(7)3714652i(5)31847652318j(7)476512384765s11k(5)s131238476512378465s12l(5)m(7) 表1 搜索過(guò)程的open表和closed表open表closed表初始化 （s(4)）（）第1循環(huán)結(jié)束 （b(4),a(6),c(6)）（s(4)）第2循環(huán)結(jié)束 （d(5),e(5),a(6),c(6),f(6)）（s(4),b(4)）第3循環(huán)結(jié)束 （e(5),a(6),c(6),f(6),g(6)

5、,h(7)）（s(4),b(4),d(5)）第4循環(huán)結(jié)束 （i(5),a(6),c(6),f(6),g(6),h(7),j(7)）（s(4),b(4),d(5),e(5)）第5循環(huán)結(jié)束 （k(5),a(6),c(6),f(6),g(6),h(7),j(7)）（s(4),b(4),d(5),e(5),i(5)）第6循環(huán)結(jié)束 （l(5),a(6),c(6),f(6),g(6),h(7),j(7),m(7)）（s(4),b(4),d(5),e(5),i(5),k(5)）第7循環(huán)結(jié)束 成功退出因此可得解路徑：s(4)àb(4)àd(5)àe(5)ài(5)àk(5)àl(5).得到open表和closed表 open表結(jié)點(diǎn)父結(jié)點(diǎn)編號(hào)評(píng)價(jià)函數(shù)f(n)s04s106s204s306s415s515s616s726s827s935s1037s1145s1255s1357 closed表編號(hào)結(jié)點(diǎn)父結(jié)點(diǎn)編號(hào)評(píng)價(jià)函數(shù)f(n)0s041s2042s4153s5154s9355s11456s1255結(jié)論：由以上分析,可以從closed表中可知從初始狀態(tài)到結(jié)束狀態(tài)的搜索路徑為：s0às2às5às9às11às12.五、實(shí)驗(yàn)體會(huì) 通過(guò)本次實(shí)驗(yàn)又將課本內(nèi)容熟悉了一遍，而且通過(guò)互聯(lián)網(wǎng)了解