人工智能試驗(yàn)指導(dǎo)書

1、人工智能實(shí)驗(yàn)指導(dǎo)書人工智能實(shí)驗(yàn)指導(dǎo)書專業(yè) 年級(jí) 姓名 學(xué)號(hào)指導(dǎo)老師實(shí)驗(yàn)室使用日期實(shí)驗(yàn)一啟發(fā)式搜索一、實(shí)驗(yàn)?zāi)康模菏煜ず驼莆諉l(fā)式搜索的定義、估價(jià)函數(shù)和算法過程，并利用A算法求解九宮問題，理解求解流程和搜索順序。二、實(shí)驗(yàn)方法：1.先熟悉啟發(fā)式搜索算法；2.用C、C+或 JAVA三、實(shí)驗(yàn)背景知識(shí)：1估價(jià)函數(shù)在對(duì)問題的狀態(tài)空間進(jìn)行搜索時(shí)，為提高搜索效率需要 和被解問題的解有關(guān)的大量控制性知識(shí)作為搜索的輔助性 策略。這些控制信息反映在估價(jià)函數(shù)中。估價(jià)函數(shù)的任務(wù)就是估計(jì)待搜索節(jié)點(diǎn)的重要程度，給這 些節(jié)點(diǎn)排定次序。估價(jià)函數(shù)可以是任意一種函數(shù)，如有的定 義它是節(jié)點(diǎn)x處于最佳路徑的概率上，或是 x節(jié)點(diǎn)和目標(biāo)節(jié)

2、點(diǎn)之間的距離等等。 在此，我們把估價(jià)函數(shù)f(n)定義為從初 始節(jié)點(diǎn)經(jīng)過n節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)的最小代價(jià)路徑的代價(jià)估計(jì) 值，它的一般形式是：f(n) = g(n) + h(n)其中g(shù)(n)是從初始節(jié)點(diǎn)到節(jié)點(diǎn) n的實(shí)際代價(jià)，g(n)可以 根據(jù)生成的搜索樹實(shí)際計(jì)算出來；h(n)是從n到目標(biāo)節(jié)點(diǎn)的最佳路徑的代價(jià)估計(jì)，h(n)主要體現(xiàn)了搜索的啟發(fā)信息。語言編程實(shí)現(xiàn)實(shí)驗(yàn)內(nèi)容。2. 啟發(fā)式搜索過程的特性可采納性當(dāng)一個(gè)搜索算法在最短路徑存在的時(shí)候能保證能找到它，我們就稱該算法是可采納的。所有A*算法都是可采納的。單調(diào)性一個(gè)啟發(fā)函數(shù)h是單調(diào)的，如果a)對(duì)所有的狀態(tài)ni和nj ，其中nj是ni的子孫，h(ni )-

3、h(nj ) cost(ni,nj ), 其中 cost(ni,nj ) 是從 ni 至U nj 實(shí)際代價(jià)。b)目標(biāo)狀態(tài)的啟發(fā)函數(shù)值為0，即h(Goal)=0.具有單調(diào)性的啟發(fā)式搜索算法在對(duì)狀態(tài)進(jìn)行擴(kuò)展時(shí)能保證所有被擴(kuò)展的狀態(tài)的f值是單調(diào)遞增。信息性比較兩個(gè)啟發(fā)策略 hl和h2,如果對(duì)搜索空間中的任何一個(gè)狀態(tài)n都有h1(n) h2(n),就說h2比hl具有更多的信息性。一般而言，若搜索策略h2比hl有更多的信息性，則h2 比hl考察的狀態(tài)要少。但必須注意的是更多信息性需要更 多的計(jì)算時(shí)間，從而有可能抵消減少搜索空間所帶來的益處。3. 常用的啟發(fā)式搜索算法局部擇優(yōu)搜索算法瞎子爬山法是最簡單的啟發(fā)

4、式算法之一。該算法在搜索 過程中擴(kuò)展當(dāng)前節(jié)點(diǎn)并估價(jià)它的子節(jié)點(diǎn)。最優(yōu)的子節(jié)點(diǎn)別選 擇并進(jìn)一步擴(kuò)展；該子節(jié)點(diǎn)的兄弟節(jié)點(diǎn)和父節(jié)點(diǎn)都不再被保留。當(dāng)搜 索到達(dá)一種狀態(tài)，該狀態(tài)比它的所有子狀態(tài)都要好，則搜索 停止。因此，該算法的估價(jià)函數(shù)可表示為f(n) = h(n)。在一個(gè)限定的環(huán)境下，瞎子爬山法可能會(huì)極大的提高搜 索的效率，但是對(duì)整個(gè)搜索空間而言，可能得不到全局最優(yōu) 解。最好優(yōu)先搜索法該算法的估價(jià)函數(shù)采用 f(n) = g(n) + h(n) ，在搜索過 程中算法使用OPEN表和CLOSE表來記錄節(jié)點(diǎn)信息：OPEN表 中保留所有已生成而未考察的節(jié)點(diǎn)；CLOSE表中保留所有已訪問過的節(jié)點(diǎn)。算法在每一次搜索

5、過程中都會(huì)對(duì)OPEN表中的節(jié)點(diǎn)按照每個(gè)節(jié)點(diǎn)的f值進(jìn)行排序，選擇f值最小節(jié)點(diǎn)進(jìn) 行擴(kuò)展。算法的描述如下： 把起始節(jié)點(diǎn)S放到OPEN表中，計(jì)算f(S),并把其值 與節(jié)點(diǎn)S聯(lián)系起來。 若OPEN是個(gè)空表，則算法失敗退出，無解。 從OPEN表中選擇一個(gè)f值最小的節(jié)點(diǎn)i。結(jié)果有幾個(gè)節(jié)點(diǎn)合格，當(dāng)其中有一個(gè)為目標(biāo)節(jié)點(diǎn)時(shí)，貝y選擇此目標(biāo)節(jié)點(diǎn)，否則就選擇其中任一個(gè)節(jié)點(diǎn)作為節(jié)點(diǎn)i 。 把節(jié)點(diǎn)i從OPEN表中移出，并把它放入到 CLOSED 的擴(kuò)展節(jié)點(diǎn)表中。 若節(jié)點(diǎn)i是個(gè)目標(biāo)節(jié)點(diǎn)，則成功退出，求得一個(gè)解。擴(kuò)展i，生成其全部后繼節(jié)點(diǎn)。對(duì) i的每個(gè)后繼節(jié)點(diǎn)j : 計(jì)算f(j)。如果j既不在OPEN表中，也不在 CLOSE表中，貝U用估 價(jià)函數(shù)f將其添加到OPEN表。從j加一指向其父輩節(jié)點(diǎn)i 的指針，以便一旦找到目標(biāo)節(jié)點(diǎn)時(shí)記住一個(gè)解答路徑。女口果j已則OPEN表中或CLOSED表中，貝吐匕較剛剛對(duì)j計(jì)算過的f值和前面計(jì)算過的該節(jié)點(diǎn)在表中的f的值。若新的f值較小，則以此值取代舊值。從j指向i，而不是指向它的父輩節(jié)點(diǎn)。若節(jié)點(diǎn)j在CLOSED!中，則把它移回 OPEN表。轉(zhuǎn)向。 四、實(shí)驗(yàn) 內(nèi)容：問題描述：用啟發(fā)式搜索方法求解下