1、真空吸塵器問題一實驗目的在人工智能領域，有一個重要部分，是研究智能化智能體的。智能體可以被 視為通過傳感器感知所處環境并通過執行器對該環境產生作用的東西。 本實驗分 析真空吸塵器這個簡單反射型智能體、環境以及它們之間的關系。驗證該吸塵器 是否是理性智能體（行為表現盡可能好的智能體）。二實驗內容1 .智能體的描述智能體可以被視為通過傳感器感知所處環境并通過執行器對該環境產生作 用的東西。人類智能體具有眼睛、耳朵和其它器官作為傳感器，也具有手、腿和 身體的其它部位作為執行器。機器人智能體則可能用攝像頭、紅歪測距儀作為傳 感器，各種馬達作為執行器。簡單放射型智能體直接對感知信息做出反應。感知行動環境

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

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

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

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

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

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

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

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

10、顯然這是最優的容易觀察到，在根節點的第一子層有b個結點，第二子層有b2,然后b3,以此類推。在最壞情況下，我們將擴展為目標結點前的所有結點，在 d + 1層 擴展bd+1-b 個，那么將總共擴展：b + b2 + b3 + + bd + (bd+-b) = O(bd+1) 由此可見，該算法的空間要求是相當高的。廣度優先搜索算法偽代碼描述如下(隊列實現)：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)深度優先搜索(Depth First Searc h, DFS):總是擴展搜索樹當前邊緣中最深的節點。搜索直接推進到搜索樹的最深層， 那里的節點沒有后繼節點。當那些節點擴展完之后，它們被從邊緣中去掉，然后 搜索算法“向上回到”下一個還有未擴展后繼節點的稍淺的節點。0圖22深度優先搜索搜索順序深度優先算法偽代碼描述如下(堆棧實現)：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):無邊界的搜索樹問題可以通過對深度優先搜索提供一個預先設定的深度限 制L來解決。就是說，深度為L的節點被當作沒有后繼的節點對待。2 .有信息搜索，是一種在問題本身定義之外還利用問題的特定知識的搜索策 略一如何能夠比無信息的搜索策略更有效地找到解

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

14、以求解問題了，搜索效率較高。A*搜索算法偽代碼描述如下(優先隊列實現-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; 四所用程序相關說明1 .使用軟件：VC+6.02 .具體內容：在這個程序中，分別用廣度優先、深度優先和A*算法實現了八數碼問題，初始狀態值和目標狀態值自己任意設定，空格周圍的棋子可以移動到空格中，一步一步往下進行，直至達到目標狀態，搜索過程中的每一步都有 顯示，這樣更便于理解每一步的運行情況。另外，此程序除了實現了八數碼問題求解外，還推廣應用于16數碼問題，即在4X4的方格棋盤上，分別放置標有數字 1、2、3、4、5、6、7、8、9、 A、B、C、D、E、F的

16、十五張牌，第十六張牌不標數字，記為空格，空格用 0 表示，空格周圍的棋子可以移動到空格中。 五實驗結果分析1.實驗結果圖如下:搜索算法；|廣度優先二:鬻1.4*4-初始狀態pF 丁 F F |2" F F b-目標狀態F F F 濟W廣 pF 肉T深度估討士 1000開始搜索圖5-1廣度優先搜索算法（無解情況）Chess -無標置搜索算法:深度估注1項初始犍r r r b目懶態爐灰F F圖5-2廣度優先搜索算法（八數碼）搜索算法:初始狀態DC目標狀態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 瓦目標狀態|F TF圖5-5深度優先搜索算法（八數碼）-無標題深度估計：1 wormraaiiiBB Him iihii ii畫搜索算法：1深度優先二；警' 4*4一初始狀態一Ir r r r|T|FF F FF目標狀態一f |e |5 卜F F FFH H搜索算法:A*算法* 3*34*4-初始狀態-|T T F目標狀態H ,H 7 1F深度估計：000開始搜索圖5-7 A*搜索算法（無解情況）les

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