人工智能報(bào)告

1、人工智能課程報(bào)告推箱子小游戲的人工智能尋路 學(xué)院：姓名：學(xué)號(hào)：班級(jí)：指導(dǎo)教師： 人工智能課程報(bào)告一簡(jiǎn)介推箱子游戲簡(jiǎn)介經(jīng)典的推箱子是一個(gè)來(lái)自日本的古老游戲，目的是在訓(xùn)練你的邏輯思考能力。在一個(gè)狹小的倉(cāng)庫(kù)中，要求把木箱放到指定的位置，稍不小心就會(huì)出現(xiàn)箱子無(wú)法移動(dòng)或者通道被堵住的情況，所以需要巧妙的利用有限的空間和通道，合理安排移動(dòng)的次序和位置，才能順利的完成任務(wù)。勝利條件就是把所有的箱子都推到目的地。本程序的目標(biāo)就是利用啟發(fā)式搜索實(shí)現(xiàn)電腦自動(dòng)推箱子。推箱子游戲地圖程序采用手機(jī)中的推箱子小游戲的程序，地圖總共75張，難度由易到難，搜尋路徑的計(jì)算復(fù)雜度也會(huì)越來(lái)越高。每一張地圖都以文本文件的形式存儲(chǔ)起來(lái)

2、。地圖展示：（第1關(guān)）（第35關(guān)）（第56關(guān)）（第75關(guān)）保存到文本文件中的地圖代碼：推箱子中人的行為人只可以推箱子, 不可以拉, 而且一次只能推動(dòng)一個(gè)。即使是處于目的位置的箱子也可以推走。二基本概念啟發(fā)式搜索考慮一個(gè)普通的圖搜索問(wèn)題：給出初始狀態(tài)(節(jié)點(diǎn) s)和目標(biāo)狀態(tài)(節(jié)點(diǎn) t，可以不止一個(gè))以及 狀態(tài)的產(chǎn)生規(guī)則，求從 s 到 t 的一條路經(jīng)。搜索過(guò)程可描述如下：1待展開(kāi)的節(jié)點(diǎn)集合(OPEN 表)為 s，已展開(kāi)的節(jié)點(diǎn)集合(CLOSED 表)為 ，節(jié)點(diǎn) s 的層深為 g(s) = 0。2每次從 OPEN 表中取出一個(gè)節(jié)點(diǎn) n，根據(jù)規(guī)則擴(kuò)展產(chǎn)生一組節(jié)點(diǎn) mi，然后把 n 放入 CLOSED 表中

3、。節(jié)點(diǎn) mi 可能屬于下列三種情況之一：（1）新的節(jié)點(diǎn)，則把 mi 的源標(biāo)記為 n，層深 g(mi) = g(n) + 1，并放入 OPEN 表中。（2）已在 OPEN 表中存在的節(jié)點(diǎn)，并且層深 g(mi) > g(n) + 1，說(shuō)明從 s 到 mi 并且經(jīng)由 n 的路徑要比先前搜索得到的路徑要短。因此，把 mi 的源改記為 n，層深 g(mi) = g(n) + 1，仍放入 OPEN 表中。（3）已在 CLOSED 表中存在的節(jié)點(diǎn)，并且層深 g(mi) > g(n) + 1。同理，把 mi 的源改記為 n，層深 g(mi) = g

4、(n) + 1，并從 CLOSED 表中取出重新放入 OPEN 表中，留待以后重新搜索計(jì)算 mi 的子節(jié)點(diǎn)的層深。3不斷重復(fù)上一步操作，直到滿足下列條件之一：（1）n = t，搜索成功。（2）OPEN 表為空，搜索失敗。在以上過(guò)程中，如何從 OPEN 表中選取待擴(kuò)展的節(jié)點(diǎn)是關(guān)鍵。如果每次均選取層深 g(n) 最小的節(jié)點(diǎn)，以上過(guò)程就是寬度優(yōu)先搜索；如果每次均選取層深 g(n) 最大的節(jié)點(diǎn)，以上過(guò)程 就是深度優(yōu)先搜索。啟發(fā)式搜索算法A*的思想是，給節(jié)點(diǎn)定義一個(gè)評(píng)價(jià)函數(shù)f(n) = g(n) + h(n) (1)其中，g(n) 是節(jié)點(diǎn)的層深，即從 s 到 n 目前搜索已知的最短路

5、徑長(zhǎng)度，h(n) 是節(jié)點(diǎn) n 到目標(biāo)節(jié)點(diǎn) t 的最短路徑長(zhǎng)度的估計(jì)值，稱為啟發(fā)函數(shù)。擁有最小 f(n) 值的節(jié)點(diǎn)有希望成為從 s 到 t 的最短路徑上的一個(gè)節(jié)點(diǎn)，因而被取出并擴(kuò)展。啟發(fā)函數(shù) h(n) 具有下列一些性質(zhì)(證明略，我也不完全懂)：如果 h(n) 處在從 n 到 t 的最短路徑長(zhǎng)度的真實(shí)值 h*(n) 的下界，即恒有 h(n) <= h*(n)，則算法A*找到的一定是從 s 到 t 的最短路徑。此時(shí)算法A*稱為算法A*?？梢韵胂?，h(n) 越接近真實(shí)值 h*(n)，它所包含的啟發(fā)信息就越多，搜索所需擴(kuò)展的節(jié)點(diǎn)數(shù)就越少。如果對(duì)所有節(jié)點(diǎn) ni 和 nj (其中

6、nj 是 ni 的子節(jié)點(diǎn))都有 h(ni) - h(nj) <= 1，則稱啟發(fā)函數(shù) h(n) 滿足單調(diào)限制條件。此時(shí)，算法A*在選取節(jié)點(diǎn) n 進(jìn)行擴(kuò)展時(shí)，必有 g(n) = g*(n)，在搜索過(guò)程中不會(huì)出現(xiàn)把 mi 從 CLOSED 表中取出重新放入 OPEN 表的情況。三算法的設(shè)計(jì)與實(shí)施推箱子游戲模塊推箱子游戲初始化模塊畫(huà)圖模塊移動(dòng)箱子模塊移動(dòng)小人模塊功能控制模塊程序中定義的四個(gè)函數(shù)：int orderDown(NodeInfo *infos, int *opens, const int &open_used, int root);堆的向下(從根到

7、葉)調(diào)整，內(nèi)部使用int orderUp(NodeInfo *infos, int *opens, const int &open_used, int leaf);堆的向上(從葉到根)調(diào)整，內(nèi)部使用template <class Node> int key(Node *nodes, const int &hash_size, const Node &n);在散列數(shù)組中查找節(jié)點(diǎn)template <class Node> int solve(Node *nodes, int hash_size, Node s);搜索函數(shù)，程序的入口基于可重用性的考慮

8、，搜索函數(shù) solve 被定義為模板函數(shù)，它操作的對(duì)象是一個(gè)表示節(jié)點(diǎn)的 模板類。節(jié)點(diǎn)類要求具有被搜索函數(shù)使用的一些基本接口，這些接口描述了節(jié)點(diǎn)的基本行為和屬性，而節(jié)點(diǎn)的 具體意義(比如表示推箱子的某個(gè)狀態(tài))則隱藏在類的實(shí)現(xiàn)細(xì)節(jié)中。節(jié)點(diǎn)類的基本接口如下：int from;節(jié)點(diǎn)的源，返回目標(biāo)路徑時(shí)使用Node();空節(jié)點(diǎn)的構(gòu)造函數(shù)int possibleMoves() const;可能的擴(kuò)展節(jié)點(diǎn)數(shù)int move(int sw);按第 sw 種擴(kuò)展方式改變節(jié)點(diǎn)int h() const;啟發(fā)函數(shù)int isTarget() const;判斷節(jié)點(diǎn)是否目標(biāo)節(jié)點(diǎn)int isNull() const;判斷

9、節(jié)點(diǎn)是否空節(jié)點(diǎn)int hash() const;散列函數(shù)friend int operator = (const Node &left, const Node &right);判斷兩個(gè)節(jié)點(diǎn)是否同一void output() const;輸出為了提高速度，節(jié)點(diǎn)的存儲(chǔ)和查找使用開(kāi)地址散列，使用簡(jiǎn)單的線性探測(cè)解決沖突。程序中的 Node nodes 和 NodeInfo infos 是并列的兩個(gè)散列數(shù)組，分別存儲(chǔ)所有已展開(kāi)的節(jié)點(diǎn) 和節(jié)點(diǎn)的附加信息(f 值和在 OPEN 表中的位置)。key 根據(jù)節(jié)點(diǎn)的散列函數(shù) hash() 在散列數(shù)組中查找或分配節(jié)點(diǎn)。OPEN 表實(shí)際上是一個(gè)優(yōu)先隊(duì)列

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

11、否相等只需分別比較每個(gè)箱子和人的坐標(biāo)是否相等即可。節(jié)點(diǎn)的擴(kuò)展每個(gè)箱子可以推向四個(gè)方向，因此總的可能的擴(kuò)展節(jié)點(diǎn)數(shù)是箱子數(shù)的四倍。考慮到人的 可到達(dá)范圍(way)的限制，某些箱子的某些方向(push_directions)是不可到達(dá)的。另外，地圖中 還存在一些“死位置”(dead_positions)，比如墻角、兩個(gè)箱子并列在墻邊等等。還有，箱子的背后 可能是墻壁或者另一個(gè)箱子。這些不可能的情況都可以在節(jié)點(diǎn)擴(kuò)展函數(shù) move(sw) 中予以拒絕。啟發(fā)函數(shù)可以計(jì)算所有箱子離最近的目標(biāo)的距離之和作為啟發(fā)函數(shù) h() 的返回值。不難看出，此定義的 啟發(fā)函數(shù)滿足算法A*的下界條件，因而找到的目標(biāo)路徑一定是

12、最優(yōu)解。A*算法的偽代碼如下：創(chuàng)建兩個(gè)表，OPEN表保存所有已生成而未考察的節(jié)點(diǎn)，CLOSED表中記錄已訪問(wèn)過(guò)的節(jié)點(diǎn)。算起點(diǎn)的估價(jià)值;將起點(diǎn)放入OPEN表;while(OPEN!=NULL) 從OPEN表中取估價(jià)值f最小的節(jié)點(diǎn)n; if(n節(jié)點(diǎn)=目標(biāo)節(jié)點(diǎn)) break;for(當(dāng)前節(jié)點(diǎn)n 的每個(gè)子節(jié)點(diǎn)X) 算X的估價(jià)值; if(X in OPEN) if( X的估價(jià)值小于OPEN表的估價(jià)值 ) 把n設(shè)置為X的父親; 更新OPEN表中的估價(jià)值; /取最小路徑的估價(jià)值if(X inCLOSE) if( X的估價(jià)值小于CLOSE表的估價(jià)值 ) 把n設(shè)置為X的父親; 更新CLOSE表中的估價(jià)值; 把X

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

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

15、計(jì)算每個(gè)箱子到達(dá)目標(biāo)所需的步數(shù)?？紤]一個(gè)箱子緊挨著一個(gè)目標(biāo)的情況，因?yàn)?地圖和人的位置關(guān)系，箱子很可能根本無(wú)法一步推到目標(biāo)上，這時(shí)簡(jiǎn)單的以箱子和目標(biāo)的距離計(jì)算就 不太合適了。一種可能的辦法是，在正式搜索之前先搜索得出一個(gè)箱子從不同的位置出發(fā)推到目標(biāo)所需的 步數(shù)。不過(guò)，這點(diǎn)改進(jìn)對(duì)搜索的性能能有多大提高還是一個(gè)未知數(shù)。刪除搜索樹(shù)上的“死”分枝。這點(diǎn)屬于對(duì)啟發(fā)式搜索通用程序的改進(jìn)，與推箱子無(wú)關(guān)。但是 測(cè)試表明，在推箱子的搜索過(guò)程中，“死”分枝的比例一般只占總節(jié)點(diǎn)數(shù)的一半左右。因此，這點(diǎn)改進(jìn)帶來(lái) 的效果估計(jì)也不會(huì)很明顯。五結(jié)論（包括結(jié)果）結(jié)論：?jiǎn)l(fā)式搜索可以比較好的解決推箱子問(wèn)題。運(yùn)行結(jié)果：點(diǎn)擊運(yùn)行程

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