人工智能報告

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

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

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

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

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

6、(證明略略，我也不完完全懂)：如果 h(n) 處在從 n 到 tt 的最短路路徑長度的真真實(shí)值 h*(n) 的的下界，即恒恒有 h(nn) = h*(n)，則則算法A*找到的一一定是從 ss 到 t 的最短路徑徑。此時算法法A*稱為算法法A*。可以想象，h(n) 越接接近真實(shí)值 h*(n)，它它所包含的啟啟發(fā)信息就越越多，搜索所所需擴(kuò)展的節(jié)節(jié)點(diǎn)數(shù)就越少少。如果對所有節(jié)點(diǎn)點(diǎn) ni和 nj(其中 nnj是 ni的子節(jié)點(diǎn))都有 h(ni) - hh(nj) = 1，則稱啟啟發(fā)函數(shù) hh(n) 滿滿足單調(diào)限制制條件。此時時，算法A*在選取節(jié)點(diǎn)點(diǎn) n 進(jìn)行行擴(kuò)展時，必必有 g(nn) = g*(n)，在

7、在搜索過程中中不會出現(xiàn)把把 mi從 CLOOSED 表表中取出重新新放入 OPPEN 表的的情況。三算法的設(shè)計計與實(shí)施推箱子游戲模塊塊推箱子游戲推箱子游戲初始化模塊畫圖模塊移動箱子模塊移動小人模塊功能控制模塊程序中定義的四四個函數(shù)：int ordderDowwn(NoddeInfoo *inffos, iint *oopens, consst intt &opeen_useed, innt rooot);堆的向下(從根根到葉)調(diào)整整，內(nèi)部使用用int ordderUp(NodeIInfo *infoss, intt *opeens, cconst int &open_used, int lea

8、f);堆的向上(從葉葉到根)調(diào)整整，內(nèi)部使用用templatte int kkey(Noode *nnodes, consst intt &hassh_sizze, coonst NNode &n);在散列數(shù)組中查查找節(jié)點(diǎn)templatte int ssolve(Node *nodees, innt hassh_sizze, Noode s);搜索函數(shù)，程序序的入口基于可重用性的的考慮，搜索索函數(shù) soolve 被被定義為模板板函數(shù)，它操操作的對象是是一個表示節(jié)節(jié)點(diǎn)的 模板板類。節(jié)點(diǎn)類類要求具有被被搜索函數(shù)使使用的一些基基本接口，這這些接口描述述了節(jié)點(diǎn)的基基本行為和屬屬性，而節(jié)點(diǎn)點(diǎn)的 具體意意

9、義(比如表表示推箱子的的某個狀態(tài))則隱藏在類類的實(shí)現(xiàn)細(xì)節(jié)節(jié)中。節(jié)點(diǎn)類類的基本接口口如下：int froom;節(jié)點(diǎn)的源，返回回目標(biāo)路徑時時使用Node();空節(jié)點(diǎn)的構(gòu)造函函數(shù)int posssibleeMovess() coonst;可能的擴(kuò)展節(jié)點(diǎn)點(diǎn)數(shù)int movve(intt sw);按第 sw 種種擴(kuò)展方式改改變節(jié)點(diǎn)int h() consst;啟發(fā)函數(shù)int isTTargett() coonst;判斷節(jié)點(diǎn)是否目目標(biāo)節(jié)點(diǎn)int isNNull() consst;判斷節(jié)點(diǎn)是否空空節(jié)點(diǎn)int hassh() cconst;散列函數(shù)friend int ooperattor = (connst

10、 Noode &lleft, constt Nodee &rigght);判斷兩個節(jié)點(diǎn)是是否同一void ouutput() connst;輸出為了提高速度，節(jié)節(jié)點(diǎn)的存儲和和查找使用開開地址散列，使使用簡單的線線性探測解決決沖突。程序序中的 Noode noodes 和 NoodeInffo inffos 是并列的兩兩個散列數(shù)組組，分別存儲儲所有已展開開的節(jié)點(diǎn) 和和節(jié)點(diǎn)的附加加信息(f 值和在 OOPEN 表表中的位置)。key 根據(jù)節(jié)點(diǎn)的的散列函數(shù) hash() 在散列列數(shù)組中查找找或分配節(jié)點(diǎn)點(diǎn)。OPEN 表實(shí)實(shí)際上是一個個優(yōu)先隊列，因因而采用堆的的方式實(shí)現(xiàn)。程程序中的 iint oppen

11、s 是以數(shù)組組(完全二叉叉樹)存儲的的堆，數(shù)組元元素表示節(jié)點(diǎn)點(diǎn)在散列數(shù)組組中的位置，最最小 f 值值的節(jié)點(diǎn)可以以在 堆的根根即 opeens0 處中給出出。ordeerDownn 和 orrderUpp 是調(diào)整堆堆的需要。推箱子應(yīng)用通用程序求求解推箱子問問題，關(guān)鍵是是節(jié)點(diǎn)類的實(shí)實(shí)現(xiàn)。狀態(tài)的劃分推箱子的狀態(tài)由由人和箱子的的位置決定?？伎紤]到人可以以在墻壁和箱箱子圍成的連連通區(qū)域內(nèi)任任意行走 而而不會對局面面產(chǎn)生實(shí)質(zhì)性性的影響，規(guī)規(guī)定人必須位位于他所處的的連通區(qū)域的的左上角。考考慮到箱子的的全同性，箱箱子的 坐標(biāo)標(biāo)應(yīng)從小到大大排序。這些些都在構(gòu)造函函數(shù) Boxx() 或者者節(jié)點(diǎn)擴(kuò)展函函數(shù) movv

12、e(sw) 中完成。這這時，判斷 兩個狀態(tài)是是否相等只需需分別比較每每個箱子和人人的坐標(biāo)是否否相等即可。節(jié)點(diǎn)的擴(kuò)展每個箱子可以推推向四個方向向，因此總的的可能的擴(kuò)展展節(jié)點(diǎn)數(shù)是箱箱子數(shù)的四倍倍?？紤]到人人的 可到達(dá)達(dá)范圍(waay)的的限制，某些些箱子的某些些方向(puush_diirectiions)是不可到到達(dá)的。另外外，地圖中 還存在一些些“死位置”(dead_posittions)，比如如墻角、兩個個箱子并列在在墻邊等等。還還有，箱子的的背后 可能能是墻壁或者者另一個箱子子。這些不可可能的情況都都可以在節(jié)點(diǎn)點(diǎn)擴(kuò)展函數(shù) move(sw) 中中予以拒絕。啟發(fā)函數(shù)可以計算所有箱箱子離最近的的目

13、標(biāo)的距離離之和作為啟啟發(fā)函數(shù) hh() 的返返回值。不難難看出，此定定義的 啟發(fā)發(fā)函數(shù)滿足算算法A*的下界條條件，因而找找到的目標(biāo)路路徑一定是最最優(yōu)解。A*算法的偽代代碼如下：創(chuàng)建兩個表，OOPEN表保保存所有已生生成而未考察察的節(jié)點(diǎn)，CCLOSEDD表中記錄已已訪問過的節(jié)節(jié)點(diǎn)。算起點(diǎn)的估估價值;將起點(diǎn)放入入OPEN表表;whilee(OPENN!=NULLL) 從從OPEN表表中取估價值值f最小的節(jié)節(jié)點(diǎn)n; iif(n節(jié)點(diǎn)點(diǎn)=目標(biāo)節(jié)節(jié)點(diǎn)) bbreak;for(當(dāng)當(dāng)前節(jié)點(diǎn)n 的每個子節(jié)節(jié)點(diǎn)X) 算算X的估價值值; iif(X iin OPEEN) iif( X的的估價值小于于OPEN表表的估

14、價值 ) 把把n設(shè)置為XX的父親; 更更新OPENN表中的估價價值; /取最小路徑徑的估價值if(X inCLOOSE) iif( X的的估價值小于于CLOSEE表的估價值值 ) 把nn設(shè)置為X的的父親; 更新新CLOSEE表中的估價價值; 把XX節(jié)點(diǎn)放入OOPEN /取最小路路徑的估價值值if(X not iinbothh) 把把n設(shè)置為XX的父親; 求求X的估價值值; 并并將X插入OOPEN表中中; /還還沒有排序/ennd forr 將將n節(jié)點(diǎn)插入入CLOSEE表中; 按按照估價值將將OPEN表表中的節(jié)點(diǎn)排排序; /實(shí)際上是比比較OPENN表內(nèi)節(jié)點(diǎn)ff的大小，從從最小路徑的的節(jié)點(diǎn)向下進(jìn)進(jìn)

15、行。/ennd whiile(OPPEN!=NNULL)保存路徑，即即 從終點(diǎn)開開始，每個節(jié)節(jié)點(diǎn)沿著父節(jié)節(jié)點(diǎn)移動直至至起點(diǎn)，這就就是你的路徑徑；哈希函數(shù)可以將所有箱子子的坐標(biāo)移位位相加再平方方取中，得到到哈希函數(shù) hhash() 的返回值值。以上是我的推箱箱子程序的主主要思路，如如果你感興趣趣，請進(jìn)一步步閱讀我的程程序。(可能能不太好讀。)四調(diào)試分析我的程序在電腦腦配置較低的的條件下(需需要根據(jù)情況況修改程序中中 HASHH_SIZEE 和 HEEAP_SIIZE 的設(shè)設(shè)置)基本上上可以解六個個箱子之內(nèi)的的關(guān)，八到十十個箱子的關(guān)關(guān)或者特別復(fù)復(fù)雜的六個箱箱子的關(guān)解起起來會 比較較費(fèi)勁，特別別復(fù)雜

16、的八個個箱子以上的的關(guān)基本上就就解不了了。啟啟發(fā)式搜索雖雖然可以在很很大程度上 縮小搜索空空間，但是無無法根本解決決指數(shù)爆炸的的問題。目前前我能想到一一些改進(jìn)措施施是：如果不苛求最優(yōu)優(yōu)解，可以適適當(dāng)增大上文文提到的啟發(fā)發(fā)函數(shù)值。事事實(shí)上，所有有箱子離最近近的目標(biāo)的 距離之和與與實(shí)際到達(dá)目目標(biāo)所需的步步數(shù)之間有很很大的差距，因因而擴(kuò)展生成成了許多無關(guān)關(guān)的節(jié)點(diǎn)。增增大啟發(fā)函數(shù)數(shù) 值，例如如人為的給它它乘以二，以以犧牲最優(yōu)解解為代價更快快地到達(dá)目標(biāo)標(biāo)。用另一種方式計計算每個箱子子到達(dá)目標(biāo)所所需的步數(shù)?？伎紤]一個箱子子緊挨著一個個目標(biāo)的情況況，因為 地地圖和人的位位置關(guān)系，箱箱子很可能根根本無法一步步

17、推到目標(biāo)上上，這時簡單單的以箱子和和目標(biāo)的距離離計算就 不不太合適了。一一種可能的辦辦法是，在正正式搜索之前前先搜索得出出一個箱子從從不同的位置置出發(fā)推到目目標(biāo)所需的 步數(shù)。不過過，這點(diǎn)改進(jìn)進(jìn)對搜索的性性能能有多大大提高還是一一個未知數(shù)。刪除搜索樹上的的“死”分枝枝。這點(diǎn)屬于于對啟發(fā)式搜搜索通用程序序的改進(jìn)，與與推箱子無關(guān)關(guān)。但是 測測試表明，在在推箱子的搜搜索過程中，“死死”分枝的比比例一般只占占總節(jié)點(diǎn)數(shù)的的一半左右。因因此，這點(diǎn)改改進(jìn)帶來 的的效果估計也也不會很明顯顯。五結(jié)論（包括括結(jié)果）結(jié)論：啟發(fā)式搜搜索可以比較較好的解決推推箱子問題。運(yùn)行結(jié)果：點(diǎn)擊運(yùn)行程序，顯顯示如下圖：可選擇關(guān)卡，選

18、選擇完關(guān)卡后后點(diǎn)擊“確定”，然后點(diǎn)擊擊“演示”，則程序進(jìn)進(jìn)入自動演示示狀態(tài)，每點(diǎn)點(diǎn)擊一下鼠標(biāo)標(biāo)，電腦便會會自動移動一一步，如下圖圖：當(dāng)顯示“演示完完畢”時，演示結(jié)結(jié)束，電腦便便會給出最終終結(jié)果：六心得體會通過這次上機(jī)實(shí)實(shí)習(xí)，不僅讓讓我對人工智智能有了一定定的了解，更更重要的還讓讓我學(xué)會了、或或者說是驗證證了“做事一定要要有次序和對對事物的總體體把握”這句話。開開始我一味的的進(jìn)行調(diào)試，急急切的想僥幸幸調(diào)試出來，但但由于沒有進(jìn)進(jìn)行深入的考考慮，我調(diào)試試了很久都沒沒沒有成功，我我仔細(xì)的分析析材料，在原原由的基礎(chǔ)上上我進(jìn)行了改改正，終于調(diào)調(diào)試成功了，雖雖然這個過程程還是經(jīng)過了了一翻努力，當(dāng)當(dāng)然汗水還是是留的很值，這這次編程報告告，不僅讓我我對人工智能能這門課程有有了更深入的的研究、對很很多重要的概概念有了鞏固固和掌握，還還給了我今后后做事的啟示示。做事要塌塌實(shí)，不能想想著一步登天天，要有計劃劃，有目的的的進(jìn)行做事。我我們應(yīng)該認(rèn)真真找到自己的的缺點(diǎn)并且及及時改正。此此時此刻，我我心里多了些些成就感。這這是我整個學(xué)學(xué)習(xí)過程中的的一次經(jīng)驗、一一次總結(jié)，我我