1、真空吸塵器問題一實驗?zāi)康脑谌斯ぶ悄茴I(lǐng)域，有一個重要部分，是研究智能化智能體的。智能體可以被 視為通過傳感器感知所處環(huán)境并通過執(zhí)行器對該環(huán)境產(chǎn)生作用的東西。 本實驗分 析真空吸塵器這個簡單反射型智能體、環(huán)境以及它們之間的關(guān)系。驗證該吸塵器 是否是理性智能體（行為表現(xiàn)盡可能好的智能體）。二實驗內(nèi)容1 .智能體的描述智能體可以被視為通過傳感器感知所處環(huán)境并通過執(zhí)行器對該環(huán)境產(chǎn)生作 用的東西。人類智能體具有眼睛、耳朵和其它器官作為傳感器，也具有手、腿和 身體的其它部位作為執(zhí)行器。機器人智能體則可能用攝像頭、紅歪測距儀作為傳 感器，各種馬達作為執(zhí)行器。簡單放射型智能體直接對感知信息做出反應(yīng)。感知行動環(huán)境

2、圖21智能體通過傳感器和執(zhí)行器與環(huán)境進行交互2 .真空吸塵器的描述真空吸塵器屬于簡單智能體的一種，真空吸塵器世界只有兩個地點：A地點和B地點。一個吸塵器智能體可以感知它處于哪個方格中， 以及該地點是否有 灰塵。它可以選擇向左移動，向右移動，吸取灰塵，或者什么也不做。機器人所處位置有兩種選擇，要么在 A,要么在Bo A、B兩地點的狀態(tài)分別有兩種，干凈 或臟。A B兩地具體狀態(tài)及吸塵器的行動如下表：廳P吸塵器所處位置A地點狀態(tài)B地點狀態(tài)吸塵器的行動情況1A干凈干凈沒有地點需要清掃，吸塵器/、動2A干凈臟清掃B地點，吸塵器不動3A臟干凈清掃A地點，吸塵器不動4A臟臟先清掃A地點，再到達B 地點，并清

3、掃B地點5B干凈干凈沒有地點需要清掃6B臟干凈清掃A地點，吸塵器不動7B干凈臟清掃B地點，吸塵器不動8B臟臟先清掃B地點，再到達A 地點，并清掃A地點表21 A、B兩地具體狀態(tài)及吸塵器的行動3 .開發(fā)環(huán)境所使用的軟件：VC+6.0程序說明：在程序中吸塵器所處位置用1、2表示，分別表示 A B兩地。A B兩地的 狀態(tài)用0、1表示，分別表示干凈不需要清掃、臟需要清掃。通過吸塵器對環(huán)境 的判斷得知A、B兩地干凈與否，再來回移動進行清掃。4.吸塵器程序流程圖開始C清掃A地點C清掃B地點實驗結(jié)果分析圖22程序流程圖圖31狀態(tài)一圖31狀態(tài)二圖3-1狀態(tài)三圖31狀態(tài)四圖31狀態(tài)五開始說明機器人所處位置參數(shù)為

4、I和2時,分別表示機器人現(xiàn)在觸也.點、和E地點；地.點.狀忐夢非為口和 1時.芬刻表宗該地點不需要清掃和需要清掃.圖31狀態(tài)六圖3-1狀態(tài)七圖3-1狀態(tài)八四收獲與心得本實驗通過對簡單智能體一一真空吸塵器的研究，使我加深了對智能體、環(huán) 境、性能度量等概念的理解。通過傳感器的感知可以得到環(huán)境的感知信息，智能 體通過感知到的信息進行判斷，再通過執(zhí)行器行動，然后引起狀態(tài)的變化，再反 饋給環(huán)境。在這個過程中，性能度量即智能體成功程度標準的具體化是重要的。吸塵器是一個簡單的反射型智能體，它通過傳感器感知外面的環(huán)境是什么情況 的，然后我們點一下“確定”按鈕即執(zhí)行器，執(zhí)行行動，之后把狀態(tài)反饋給環(huán)境。 由此可見

5、，環(huán)境的變化引起智能體行動的變化， 反過來，智能體的行動對環(huán)境也 會產(chǎn)生影響，它們是聯(lián)系在一起的。這個程序的開發(fā)環(huán)境是 VC+6.0,這也使我對VC軟件的編程環(huán)境、編程方 法等有了進一步的了解。完成人工智能作業(yè)的同時，也學(xué)了一些 VC的知識，這 對我以后的學(xué)習(xí)會有很大幫助，也增強學(xué) VC的信心。收獲的同時，我也發(fā)現(xiàn)了自己學(xué)習(xí)中的不足，在以后的學(xué)習(xí)生活中一定改正。 另外，在實驗的過程中，我得到了老師耐心細致的指導(dǎo)和同學(xué)熱心的幫助，在這 里對她們表示感謝！八數(shù)碼問題一 “八數(shù)碼問題”的描述八數(shù)碼問題一般描述：在3X3的方格棋盤上，分別放置標有數(shù)字1、2、3、 4、5、6、7、8的八張牌，第九張牌不

6、標數(shù)字，記為空格，空格用 0表示，空格 周圍的棋子可以移動到空格中。給定一種初始狀態(tài)和目標狀態(tài)，通過移動空格， 使得棋盤從初始狀態(tài)向目標狀態(tài)轉(zhuǎn)換（其中操作空格可用的操作有：左移、上移、 右移、下移，但不能移出棋盤之外），通過搜索策略尋找從初始狀態(tài)到目標狀態(tài) 的解路徑。二“八數(shù)碼問題”是否有解的判斷1 .“八數(shù)碼問題”是否有解的判斷的目的：有的八數(shù)碼排列順序是無解的，如果再進行搜索就會浪費很多時間， 最終還 得不到結(jié)果。為了避免無解的情況下盲目搜索，判斷是否有解是必要的。2 .八數(shù)碼問題有解無解的結(jié)論：一個狀態(tài)表示成一維的形式，求出除0之外所有數(shù)字的逆序數(shù)之和，也就是 每個數(shù)字前面比它大的數(shù)字的

7、個數(shù)的和， 稱為這個狀態(tài)的逆序。若兩個狀態(tài)的逆 序奇偶性相同，則可相互到達，否則不可相互到達。可以證明，八碼問題有解的 充分必要條件是兩個狀態(tài)的逆序列奇偶性相同。為此，無解判定問題轉(zhuǎn)化為計算兩個狀態(tài)的逆序列奇偶性問題，由于原始狀態(tài)的逆序為0 （偶數(shù)），則逆序為偶數(shù)的狀態(tài)有解。也就是說，逆序的奇偶將所有的狀態(tài)分為了兩個等價類，同一個等價類中的狀態(tài)都可相互到達。3 .簡要說明：當左右移動空格時，逆序不變。當上下移動空格時，相當于將一個數(shù)字向前 （或向后）移動兩格，跳過的這兩個數(shù)字要么都比它大（小），逆序可能土 2;要 么一個較大一個較小，逆序不變。所以可得結(jié)論：只要是相互可達的兩個狀態(tài)， 它們的逆

8、序奇偶性相同。“八數(shù)碼問題”的搜索方法原理也是模擬仿真中研究的一般性問題，是搜索是人工智能中的一個基本問題,推理不可分割的一部分。 現(xiàn)實世界中的大多數(shù)問題都是結(jié)構(gòu)不良或非結(jié)構(gòu)化的 問題，一般不存在現(xiàn)成的求解方法，而只能利用已有的知識一步步地摸索著前進。解決八數(shù)碼問題的常用方法為圖搜索法， 可用無信息搜索算法（包括廣度優(yōu) 先搜索、代價一致搜索、深度優(yōu)先搜索、深度有限搜索、迭代深入搜索、雙向搜 索）和有信息搜索算法（包括貪婪最佳優(yōu)先搜索、A*算法、遞歸最佳優(yōu)先搜索）實現(xiàn)，其中A*算法又因評價函數(shù)的不同而有著不同的搜索時間。1 .無信息搜索（盲目搜索 Uninformed search）,即問題中提

9、供的定義之外沒 有任何關(guān)于狀態(tài)的附加信息。可以做的事情只能是生成后繼，并區(qū)分目標狀態(tài)與 非目標狀態(tài)。（1）廣度優(yōu)先搜索（Broadth First Search BFS）:首先擴展根節(jié)點，接著擴展根節(jié)點的所有后繼，然后再擴展它們的后繼，依 此類推。通常，在下一層的任何節(jié)點擴展之前搜索樹上層深度的所有節(jié)點都已經(jīng) 擴展過了。圖21 廣度優(yōu)先搜索搜索順序該算法可以使用FIFO隊列實現(xiàn)，初始時將開始結(jié)點放入隊列中，每次取隊 頭結(jié)點，判斷是否為終結(jié)點，不是則將其所有子結(jié)點放入隊列尾， 直到隊列為空 或者找到目標結(jié)點為止。如果目標結(jié)點在深度d ,那么該算法擴展完深度小于d 的結(jié)點后就將找到目標結(jié)點。而且，

10、顯然這是最優(yōu)的容易觀察到，在根節(jié)點的第一子層有b個結(jié)點，第二子層有b2,然后b3,以此類推。在最壞情況下，我們將擴展為目標結(jié)點前的所有結(jié)點，在 d + 1層 擴展bd+1-b 個，那么將總共擴展：b + b2 + b3 + + bd + (bd+-b) = O(bd+1) 由此可見，該算法的空間要求是相當高的。廣度優(yōu)先搜索算法偽代碼描述如下(隊列實現(xiàn))：Status BFS()Push_back(begin);doCurrentState=Top();Pop();if(Solution(CurrentState)return Success;for each successor of Curr

11、entState doif(!Exist(successor)Push_back(successor);while(!Empty();Return NoAnswer;(2)深度優(yōu)先搜索(Depth First Searc h, DFS):總是擴展搜索樹當前邊緣中最深的節(jié)點。搜索直接推進到搜索樹的最深層， 那里的節(jié)點沒有后繼節(jié)點。當那些節(jié)點擴展完之后，它們被從邊緣中去掉，然后 搜索算法“向上回到”下一個還有未擴展后繼節(jié)點的稍淺的節(jié)點。0圖22深度優(yōu)先搜索搜索順序深度優(yōu)先算法偽代碼描述如下(堆棧實現(xiàn))：Status DFS()Push(begin);doCurrentstate = Pop();i

12、f(Solution(CurrentState)return Success;for each successor of CurrentState doif( !Exist(successor)Push(successor);while(!Empty();return NoAnswer;深度有限搜索：(Depth Limited Search, DLS):無邊界的搜索樹問題可以通過對深度優(yōu)先搜索提供一個預(yù)先設(shè)定的深度限 制L來解決。就是說，深度為L的節(jié)點被當作沒有后繼的節(jié)點對待。2 .有信息搜索，是一種在問題本身定義之外還利用問題的特定知識的搜索策 略一如何能夠比無信息的搜索策略更有效地找到解

13、。A*搜索算法：最佳優(yōu)先搜索最廣為人知的形式稱為A*搜索，它把到達節(jié)點的耗散g(n)和從該節(jié)點到目標節(jié)點的消耗h(n)結(jié)合起來，對節(jié)點進行評價：f(n)= g(n) +h(n)。因 此，此搜索策略是基于每個擴展點的評價函數(shù)進行選擇，即評選出最佳的節(jié)點擴展搜索。A*算法屬于一種啟發(fā)式搜索，它擴展結(jié)點的次序類似于廣度優(yōu)先搜索，但 不同的是每生成一個子結(jié)點需要計算估價函數(shù)f,以估算起始結(jié)點的約束經(jīng)過該結(jié)點至達目標結(jié)點的最佳路徑代價；每當擴展結(jié)點時，意是在所有待擴展結(jié)點中選 擇具有最小f值的結(jié)點做為擴展對象，以便使搜索盡量沿最有希望的方向進行。A*算法只要求產(chǎn)生問題的全部狀態(tài)空間的部分結(jié)點及關(guān)系，就可

14、以求解問題了，搜索效率較高。A*搜索算法偽代碼描述如下(優(yōu)先隊列實現(xiàn)-priority_queue): Status Greedy-Search ()priority_queue Q;begin.f = h(begin);Q.Push_back(begin);doCurrentState = Q.Top();Q.Pop();if(Solution(CurrentState) ) return Success;for each successor of CurrentState doif( !Exist(successor) )successor.f = successor.g + h(succ

15、essor);Q.Push_back(successor);一while(!Q.Empty() ); return NoAnswer; 四所用程序相關(guān)說明1 .使用軟件：VC+6.02 .具體內(nèi)容：在這個程序中，分別用廣度優(yōu)先、深度優(yōu)先和A*算法實現(xiàn)了八數(shù)碼問題，初始狀態(tài)值和目標狀態(tài)值自己任意設(shè)定，空格周圍的棋子可以移動到空格中，一步一步往下進行，直至達到目標狀態(tài)，搜索過程中的每一步都有 顯示，這樣更便于理解每一步的運行情況。另外，此程序除了實現(xiàn)了八數(shù)碼問題求解外，還推廣應(yīng)用于16數(shù)碼問題，即在4X4的方格棋盤上，分別放置標有數(shù)字 1、2、3、4、5、6、7、8、9、 A、B、C、D、E、F的

16、十五張牌，第十六張牌不標數(shù)字，記為空格，空格用 0 表示，空格周圍的棋子可以移動到空格中。 五實驗結(jié)果分析1.實驗結(jié)果圖如下:搜索算法；|廣度優(yōu)先二:鬻1.4*4-初始狀態(tài)pF 丁 F F |2" F F b-目標狀態(tài)F F F 濟W廣 pF 肉T深度估討士 1000開始搜索圖5-1廣度優(yōu)先搜索算法（無解情況）Chess -無標置搜索算法:深度估注1項初始犍r r r b目懶態(tài)爐灰F F圖5-2廣度優(yōu)先搜索算法（八數(shù)碼）搜索算法:初始狀態(tài)DC目標狀態(tài)HH|F T |b-6 5 0|T|F深度估計：000k* Chess -無標盞文件 編輯舊查看 幫助也）f 口3JMil開始搜索9&#

17、187;>ai£IUa文件更）編輯I查看也 幫助第齊耀嘉!i_.iis_.iis_.iis_-.iir|r* Chess -無標題支伴g編輯（1）查看 幫助如r r f 瓦目標狀態(tài)|F TF圖5-5深度優(yōu)先搜索算法（八數(shù)碼）-無標題深度估計：1 wormraaiiiBB Him iihii ii畫搜索算法：1深度優(yōu)先二；警' 4*4一初始狀態(tài)一Ir r r r|T|FF F FF目標狀態(tài)一f |e |5 卜F F FFH H搜索算法:A*算法* 3*34*4-初始狀態(tài)-|T T F目標狀態(tài)H ,H 7 1F深度估計：000開始搜索圖5-7 A*搜索算法（無解情況）les

18、s - 5ESS深度估訊1000ffiSi初始蟋|F目標精FFF FFF蜴算法:初始狀態(tài)一 F |T |T B 目標腦一 F底/H|T |? |6 |5 |0 |T fT |T |T深度估計：loooFH12 14圖5-9 A*搜索算法（十六數(shù)碼）2.三種算法的優(yōu)缺點簡評：三種算法在一定條件下均可得到八數(shù)碼問題的解。前兩種是經(jīng)典的無信息（盲目）搜索算法，后一種是經(jīng)典的有信息（啟發(fā)式）搜索算法。從本文的實驗可以看出，廣度優(yōu)先搜索是一種完備策略，即只要問題有解， 它就一定可以找到解。 并且，廣度優(yōu)先搜索找到的解，還一定是路徑最短的解。 這些都是廣度優(yōu)先搜索的優(yōu)點。當然，廣度優(yōu)先搜索也存在很多缺點，主