人工智能報告_第1頁
人工智能報告_第2頁
人工智能報告_第3頁
人工智能報告_第4頁
人工智能報告_第5頁
已閱讀5頁,還剩4頁未讀 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

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

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

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

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

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

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

7、制條件。此時,算算法A*在選取取節(jié)點 nn 進行擴擴展時,必必有 g(n) = g*(n),在在搜索過程程中不會出出現(xiàn)把 mmi從 CLLOSEDD 表中取取出重新放放入 OPPEN 表表的情況。三算法的的設(shè)計與實實施推箱子游戲戲模塊推箱子游戲初始化模塊畫圖模塊移動箱子模塊移動小人模塊功能控制模塊程序中定義義的四個函函數(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é)點templlate intt sollve(NNode *noddes, int hashh_sizze, NNode s);搜索函數(shù),程程序的入口口基于可重用用性的考慮慮,搜索函函數(shù) soolve 被定義為為模板函數(shù)數(shù),它操作作的對象是是一個表示示節(jié)點的 模板類。節(jié)點類

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

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

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

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

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

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

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

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

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

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論