人工智能報(bào)告

1、人工智能課課程報(bào)告推箱子子小游戲的的人工智能能尋路 學(xué)院：姓名：學(xué)號(hào)：班級(jí)：指導(dǎo)教師： 人工智能課課程報(bào)告一簡(jiǎn)介推箱子游戲戲簡(jiǎn)介經(jīng)典的推箱箱子是一個(gè)個(gè)來(lái)自 HYPERLINK /view/1554.htm 日本本的古老游游戲，目的的是在訓(xùn)練練你的 HYPERLINK /view/1838.htm 邏輯輯思考能力。在一個(gè)狹狹小的倉(cāng)庫(kù)庫(kù)中，要求求把木箱放放到指定的的位置，稍稍不小心就就會(huì)出現(xiàn)箱箱子無(wú)法移移動(dòng)或者通通道被堵住住的情況，所所以需要巧巧妙的利用用有限的空空間和通道道，合理安安排移動(dòng)的的次序和位位置，才能能順利的完完成任務(wù)。勝利條件件就是把所所有的箱子子都推到目目的地。本本程序的目目標(biāo)就是

2、利利用啟發(fā)式式搜索實(shí)現(xiàn)現(xiàn)電腦自動(dòng)動(dòng)推箱子。推箱子游戲戲地圖程序采用手手機(jī)中的推推箱子小游游戲的程序序，地圖總總共75張張，難度由由易到難，搜搜尋路徑的的計(jì)算復(fù)雜雜度也會(huì)越越來(lái)越高。每一張地地圖都以文文本文件的的形式存儲(chǔ)儲(chǔ)起來(lái)。地圖展示：（第1關(guān)）（第35關(guān)）（第56關(guān)關(guān)）（第775關(guān)）保存到文本本文件中的的地圖代碼碼：推箱子中人人的行為人只可以推推箱子, 不不可以拉, 而且一一次只能推推動(dòng)一個(gè)。即使是處處于目的位位置的箱子子也可以推推走。二基本概概念啟發(fā)式搜索索考慮一個(gè)普普通的圖搜搜索問(wèn)題：給出初始始狀態(tài)(節(jié)節(jié)點(diǎn) s)和目標(biāo)狀狀態(tài)(節(jié)點(diǎn)點(diǎn) t，可可以不止一一個(gè))以及及 狀態(tài)的的產(chǎn)生規(guī)則則，求從

3、 s 到 t 的一一條路經(jīng)。搜索過(guò)程程可描述如如下：1待展開(kāi)的的節(jié)點(diǎn)集合合(OPEEN 表)為 ss，已展展開(kāi)的節(jié)點(diǎn)點(diǎn)集合(CCLOSEED 表)為 ，節(jié)點(diǎn) s 的層層深為 gg(s) = 0。2每次從 OPENN 表中取取出一個(gè)節(jié)節(jié)點(diǎn) n，根根據(jù)規(guī)則擴(kuò)擴(kuò)展產(chǎn)生一一組節(jié)點(diǎn) mi，然后把把 n 放放入 CLLOSEDD 表中。節(jié)點(diǎn) mmi可能屬于于下列三種種情況之一一：（1）新的的節(jié)點(diǎn)，則則把 mii的源標(biāo)記記為 n，層層深 g(mi) = g(n) + 11，并放入入 OPEEN 表中中。（2）已在在 OPEEN 表中中存在的節(jié)節(jié)點(diǎn)，并且且層深 gg(mi) g(n) + 11，說(shuō)明從從 s

4、到到 mi并且經(jīng)由由 n 的的路徑要比比先前搜索索得到的路路徑要短。因此，把把 mi的源改記記為 n，層層深 g(mi) = g(n) + 11，仍放入入 OPEEN 表中中。（3）已在在 CLOOSED 表中存在在的節(jié)點(diǎn)，并并且層深 g(mii) g(n) + 11。同理，把把 mi的源改記記為 n，層層深 g(mi) = g(n) + 11，并從 CLOSSED 表表中取出重重新放入 OPENN 表中，留留待以后重重新搜索計(jì)計(jì)算 mii的子節(jié)點(diǎn)點(diǎn)的層深。3不斷重復(fù)復(fù)上一步操操作，直到到滿(mǎn)足下列列條件之一一：（1）n = tt，搜索成成功。（2）OPPEN 表表為空，搜搜索失敗。在以上過(guò)程程

5、中，如何何從 OPPEN 表表中選取待待擴(kuò)展的節(jié)節(jié)點(diǎn)是關(guān)鍵鍵。如果每每次均選取取層深 gg(n) 最小的節(jié)節(jié)點(diǎn)，以上上過(guò)程就是是寬度優(yōu)先先搜索；如如果每次均均選取層深深 g(nn) 最大大的節(jié)點(diǎn)，以以上過(guò)程 就是深度度優(yōu)先搜索索。啟發(fā)式式搜索算法法A*的思想想是，給節(jié)節(jié)點(diǎn)定義一一個(gè)評(píng)價(jià)函函數(shù)f(n) = g(n) + h(nn)(11)其中，g(n) 是是節(jié)點(diǎn)的層層深，即從從 s 到到 n 目目前搜索已已知的最短短路徑長(zhǎng)度度，h(nn) 是節(jié)節(jié)點(diǎn) n 到目標(biāo)節(jié)節(jié)點(diǎn) t 的最短路路徑長(zhǎng)度的的估計(jì)值，稱(chēng)稱(chēng)為啟發(fā)函函數(shù)。擁有有最小 ff(n) 值的節(jié)點(diǎn)點(diǎn)有希望成成為從 ss 到 tt 的最短短路徑上

6、的的一個(gè)節(jié)點(diǎn)點(diǎn)，因而被被取出并擴(kuò)擴(kuò)展。啟發(fā)函數(shù) h(n) 具有下下列一些性性質(zhì)(證明明略，我也也不完全懂懂)：如果 h(n) 處處在從 nn 到 tt 的最短短路徑長(zhǎng)度度的真實(shí)值值 h*(n) 的下界，即即恒有 hh(n) = hh*(n)，則則算法A*找到的一一定是從 s 到 t 的最最短路徑。此時(shí)算法法A*稱(chēng)為算算法A*?？梢韵胂螅琱h(n) 越接近真真實(shí)值 hh*(n)，它它所包含的的啟發(fā)信息息就越多，搜搜索所需擴(kuò)擴(kuò)展的節(jié)點(diǎn)點(diǎn)數(shù)就越少少。如果對(duì)所有有節(jié)點(diǎn) nni和 nj(其中 nj是 ni的子節(jié)點(diǎn)點(diǎn))都有 h(nii) - h(njj) = 1，則則稱(chēng)啟發(fā)函函數(shù) h(n) 滿(mǎn)滿(mǎn)足單調(diào)限限

7、制條件。此時(shí)，算算法A*在選取取節(jié)點(diǎn) nn 進(jìn)行擴(kuò)擴(kuò)展時(shí)，必必有 g(n) = g*(n)，在在搜索過(guò)程程中不會(huì)出出現(xiàn)把 mmi從 CLLOSEDD 表中取取出重新放放入 OPPEN 表表的情況。三算法的的設(shè)計(jì)與實(shí)實(shí)施推箱子游戲戲模塊推箱子游戲初始化模塊畫(huà)圖模塊移動(dòng)箱子模塊移動(dòng)小人模塊功能控制模塊程序中定義義的四個(gè)函函數(shù)：int oorderrDownn(NoddeInffo *iinfoss, innt *oopenss, coonst int &opeen_ussed, int roott);堆的向下(從根到葉葉)調(diào)整，內(nèi)內(nèi)部使用int oorderrUp(NNodeIInfo *inff

8、os, int *opeens, consst innt &oopen_usedd, innt leeaf);堆的向上(從葉到根根)調(diào)整，內(nèi)內(nèi)部使用templlate intt keyy(Nodde *nnodess, coonst int &hassh_siize, consst Noode &n);在散列數(shù)組組中查找節(jié)節(jié)點(diǎn)templlate intt sollve(NNode *noddes, int hashh_sizze, NNode s);搜索函數(shù)，程程序的入口口基于可重用用性的考慮慮，搜索函函數(shù) soolve 被定義為為模板函數(shù)數(shù)，它操作作的對(duì)象是是一個(gè)表示示節(jié)點(diǎn)的 模板類(lèi)。節(jié)點(diǎn)類(lèi)

9、要要求具有被被搜索函數(shù)數(shù)使用的一一些基本接接口，這些些接口描述述了節(jié)點(diǎn)的的基本行為為和屬性，而而節(jié)點(diǎn)的 具體意義義(比如表表示推箱子子的某個(gè)狀狀態(tài))則隱隱藏在類(lèi)的的實(shí)現(xiàn)細(xì)節(jié)節(jié)中。節(jié)點(diǎn)點(diǎn)類(lèi)的基本本接口如下下：int ffrom;節(jié)點(diǎn)的源，返返回目標(biāo)路路徑時(shí)使用用Node();空節(jié)點(diǎn)的構(gòu)構(gòu)造函數(shù)int ppossiibleMMovess() cconstt;可能的擴(kuò)展展節(jié)點(diǎn)數(shù)int mmove(int sw);按第 sww 種擴(kuò)展展方式改變變節(jié)點(diǎn)int hh() cconstt;啟發(fā)函數(shù)int iisTarrget() coonst;判斷節(jié)點(diǎn)是是否目標(biāo)節(jié)節(jié)點(diǎn)int iisNulll() conss

10、t;判斷節(jié)點(diǎn)是是否空節(jié)點(diǎn)點(diǎn)int hhash() coonst;散列函數(shù)friennd innt opperattor = (cconstt Nodde &lleft, connst NNode &rigght);判斷兩個(gè)節(jié)節(jié)點(diǎn)是否同同一void outpput() connst;輸出為了提高速速度，節(jié)點(diǎn)點(diǎn)的存儲(chǔ)和和查找使用用開(kāi)地址散散列，使用用簡(jiǎn)單的線(xiàn)線(xiàn)性探測(cè)解解決沖突。程序中的的 Nodde noodes 和 NodeeInfoo inffos 是并列列的兩個(gè)散散列數(shù)組，分分別存儲(chǔ)所所有已展開(kāi)開(kāi)的節(jié)點(diǎn) 和節(jié)點(diǎn)的的附加信息息(f 值值和在 OOPEN 表中的位位置)。kkey 根根據(jù)節(jié)點(diǎn)的的

11、散列函數(shù)數(shù) hassh() 在散列數(shù)數(shù)組中查找找或分配節(jié)節(jié)點(diǎn)。OPEN 表實(shí)際上上是一個(gè)優(yōu)優(yōu)先隊(duì)列，因因而采用堆堆的方式實(shí)實(shí)現(xiàn)。程序序中的 iint oopenss 是是以數(shù)組(完全二叉叉樹(shù))存儲(chǔ)儲(chǔ)的堆，數(shù)數(shù)組元素表表示節(jié)點(diǎn)在在散列數(shù)組組中的位置置，最小 f 值的的節(jié)點(diǎn)可以以在 堆的的根即 oopenss0 處中給出出。ordderDoown 和和 ordderUpp 是調(diào)整整堆的需要要。推箱子應(yīng)用通用程程序求解推推箱子問(wèn)題題，關(guān)鍵是是節(jié)點(diǎn)類(lèi)的的實(shí)現(xiàn)。狀態(tài)的劃分分推箱子的狀狀態(tài)由人和和箱子的位位置決定?？紤]到人人可以在墻墻壁和箱子子圍成的連連通區(qū)域內(nèi)內(nèi)任意行走走 而不會(huì)會(huì)對(duì)局面產(chǎn)產(chǎn)生實(shí)質(zhì)性性的

12、影響，規(guī)規(guī)定人必須須位于他所所處的連通通區(qū)域的左左上角?？伎紤]到箱子子的全同性性，箱子的的 坐標(biāo)應(yīng)應(yīng)從小到大大排序。這這些都在構(gòu)構(gòu)造函數(shù) Box() 或者者節(jié)點(diǎn)擴(kuò)展展函數(shù) mmove(sw) 中完成。這時(shí)，判判斷 兩個(gè)個(gè)狀態(tài)是否否相等只需需分別比較較每個(gè)箱子子和人的坐坐標(biāo)是否相相等即可。節(jié)點(diǎn)的擴(kuò)展展每個(gè)箱子可可以推向四四個(gè)方向，因因此總的可可能的擴(kuò)展展節(jié)點(diǎn)數(shù)是是箱子數(shù)的的四倍?？伎紤]到人的的 可到達(dá)達(dá)范圍(wway)的限制制，某些箱箱子的某些些方向(ppush_direectioons)是不可可到達(dá)的。另外，地地圖中 還還存在一些些“死位置置”(deead_pposittionss)，比比如墻

13、角、兩個(gè)箱子子并列在墻墻邊等等。還有，箱箱子的背后后 可能是是墻壁或者者另一個(gè)箱箱子。這些些不可能的的情況都可可以在節(jié)點(diǎn)點(diǎn)擴(kuò)展函數(shù)數(shù) movve(sww) 中予予以拒絕。啟發(fā)函數(shù)可以計(jì)算所所有箱子離離最近的目目標(biāo)的距離離之和作為為啟發(fā)函數(shù)數(shù) h() 的返回回值。不難難看出，此此定義的 啟發(fā)函數(shù)數(shù)滿(mǎn)足算法法A*的下界界條件，因因而找到的的目標(biāo)路徑徑一定是最最優(yōu)解。A*算法的的偽代碼如如下：創(chuàng)建兩個(gè)表表，OPEEN表保存存所有已生生成而未考考察的節(jié)點(diǎn)點(diǎn)，CLOOSED表表中記錄已已訪(fǎng)問(wèn)過(guò)的的節(jié)點(diǎn)。算起點(diǎn)點(diǎn)的估價(jià)值值;將起點(diǎn)點(diǎn)放入OPPEN表;whiile(OOPEN!=NULLL) 從OPPEN表

14、中中取估價(jià)值值f最小的的節(jié)點(diǎn)n; if(n節(jié)點(diǎn)=目標(biāo)節(jié)節(jié)點(diǎn)) breeak;forr(當(dāng)前節(jié)節(jié)點(diǎn)n 的的每個(gè)子節(jié)節(jié)點(diǎn)X) 算X的的估價(jià)值; if(X inn OPEEN) if( X的估估價(jià)值小于于OPENN表的估價(jià)價(jià)值 ) 把n設(shè)設(shè)置為X的的父親; 更新OOPEN表表中的估價(jià)價(jià)值; /取最小小路徑的估估價(jià)值if(X innCLOSSE) if( X的估估價(jià)值小于于CLOSSE表的估估價(jià)值 ) 把n設(shè)設(shè)置為X的的父親; 更新CCLOSEE表中的估估價(jià)值; 把X節(jié)節(jié)點(diǎn)放入OOPEN /取最最小路徑的的估價(jià)值if(X noot innbothh) 把n設(shè)設(shè)置為X的的父親; 求X的的估價(jià)值; 并將X

15、X插入OPPEN表中中; /還沒(méi)有排排序/end for 將n節(jié)節(jié)點(diǎn)插入CCLOSEE表中; 按照估估價(jià)值將OOPEN表表中的節(jié)點(diǎn)點(diǎn)排序; /實(shí)際際上是比較較OPENN表內(nèi)節(jié)點(diǎn)點(diǎn)f的大小小，從最小小路徑的節(jié)節(jié)點(diǎn)向下進(jìn)進(jìn)行。/end whille(OPPEN!=NULLL)保存路路徑，即 從終點(diǎn)開(kāi)開(kāi)始，每個(gè)個(gè)節(jié)點(diǎn)沿著著父節(jié)點(diǎn)移移動(dòng)直至起起點(diǎn)，這就就是你的路路徑；哈希函數(shù)可以將所有有箱子的坐坐標(biāo)移位相相加再平方方取中，得得到哈希函數(shù) hashh() 的的返回值。以上是我的的推箱子程程序的主要要思路，如如果你感興興趣，請(qǐng)進(jìn)進(jìn)一步閱讀讀我的程序序。(可能能不太好讀讀。)四調(diào)試分分析我的程序在在電腦配置

16、置較低的條條件下(需需要根據(jù)情情況修改程程序中 HHASH_SIZEE 和 HHEAP_SIZEE 的設(shè)置置)基本上上可以解六六個(gè)箱子之之內(nèi)的關(guān)，八八到十個(gè)箱箱子的關(guān)或或者特別復(fù)復(fù)雜的六個(gè)個(gè)箱子的關(guān)關(guān)解起來(lái)會(huì)會(huì) 比較費(fèi)費(fèi)勁，特別別復(fù)雜的八八個(gè)箱子以以上的關(guān)基基本上就解解不了了。啟發(fā)式搜搜索雖然可可以在很大大程度上 縮小搜索索空間，但但是無(wú)法根根本解決指指數(shù)爆炸的的問(wèn)題。目目前我能想想到一些改改進(jìn)措施是是：如果不苛求求最優(yōu)解，可可以適當(dāng)增增大上文提提到的啟發(fā)發(fā)函數(shù)值。事實(shí)上，所所有箱子離離最近的目目標(biāo)的 距距離之和與與實(shí)際到達(dá)達(dá)目標(biāo)所需需的步數(shù)之之間有很大大的差距，因因而擴(kuò)展生生成了許多多無(wú)關(guān)的

17、節(jié)節(jié)點(diǎn)。增大大啟發(fā)函數(shù)數(shù) 值，例例如人為的的給它乘以以二，以犧犧牲最優(yōu)解解為代價(jià)更更快地到達(dá)達(dá)目標(biāo)。用另一種方方式計(jì)算每每個(gè)箱子到到達(dá)目標(biāo)所所需的步數(shù)數(shù)。考慮一一個(gè)箱子緊緊挨著一個(gè)個(gè)目標(biāo)的情情況，因?yàn)闉?地圖和和人的位置置關(guān)系，箱箱子很可能能根本無(wú)法法一步推到到目標(biāo)上，這這時(shí)簡(jiǎn)單的的以箱子和和目標(biāo)的距距離計(jì)算就就 不太合合適了。一一種可能的的辦法是，在在正式搜索索之前先搜搜索得出一一個(gè)箱子從從不同的位位置出發(fā)推推到目標(biāo)所所需的 步步數(shù)。不過(guò)過(guò)，這點(diǎn)改改進(jìn)對(duì)搜索索的性能能能有多大提提高還是一一個(gè)未知數(shù)數(shù)。刪除搜索樹(shù)樹(shù)上的“死死”分枝。這點(diǎn)屬于于對(duì)啟發(fā)式式搜索通用用程序的改改進(jìn)，與推推箱子無(wú)關(guān)關(guān)。

18、但是 測(cè)試表明明，在推箱箱子的搜索索過(guò)程中，“死”分枝枝的比例一一般只占總總節(jié)點(diǎn)數(shù)的的一半左右右。因此，這這點(diǎn)改進(jìn)帶帶來(lái) 的效效果估計(jì)也也不會(huì)很明明顯。五結(jié)論（包包括結(jié)果）結(jié)論：?jiǎn)l(fā)發(fā)式搜索可可以比較好好的解決推推箱子問(wèn)題題。運(yùn)行結(jié)果：點(diǎn)擊運(yùn)行程程序，顯示示如下圖：可選擇關(guān)卡卡，選擇完完關(guān)卡后點(diǎn)點(diǎn)擊“確定”，然后點(diǎn)點(diǎn)擊“演示”，則程序序進(jìn)入自動(dòng)動(dòng)演示狀態(tài)態(tài)，每點(diǎn)擊擊一下鼠標(biāo)標(biāo)，電腦便便會(huì)自動(dòng)移移動(dòng)一步，如如下圖：當(dāng)顯示“演演示完畢”時(shí)，演示示結(jié)束，電電腦便會(huì)給給出最終結(jié)結(jié)果：六心得體體會(huì)通過(guò)這次上上機(jī)實(shí)習(xí)，不不僅讓我對(duì)對(duì)人工智能能有了一定定的了解，更更重要的還還讓我學(xué)會(huì)會(huì)了、或者者說(shuō)是驗(yàn)證證了“做事一定定要有次序序和對(duì)事物物的總體把把握”這句話(huà)。開(kāi)始我一