人工智能57657238

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

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

3、掃B地點(diǎn)5B干凈干凈沒有地點(diǎn)需要清掃6B臟干凈清掃A地點(diǎn)，吸塵器不動(dòng)7B干凈臟清掃B地點(diǎn)，吸塵器不動(dòng)8B臟臟先清掃B地點(diǎn)，再到達(dá)A地點(diǎn)，并清掃A地點(diǎn)表21 A、B兩地具體狀態(tài)及吸塵器的行動(dòng)3.開發(fā)環(huán)境所使用的軟件：VC+6.0程序說明：在程序中吸塵器所處位置用1、2表示，分別表示A、B兩地。A、B兩地的狀態(tài)用0、1表示，分別表示干凈不需要清掃、臟需要清掃。通過吸塵器對(duì)環(huán)境的判斷得知A、B兩地干凈與否，再來回移動(dòng)進(jìn)行清掃。4.吸塵器程序流程圖A干凈？C清掃B地點(diǎn)不用打掃C不動(dòng)C在A點(diǎn)？C清掃A地點(diǎn)B干凈？B干凈？不用打掃C不動(dòng)A干凈？B干凈？A干凈？C清掃B地點(diǎn)C清掃A地點(diǎn)C從A到BC從B到A結(jié)

4、束開始否是否否否否否否是是是是是是圖22 程序流程圖三 實(shí)驗(yàn)結(jié)果分析圖31 狀態(tài)一圖31 狀態(tài)二 圖31 狀態(tài)三 圖31 狀態(tài)四圖31 狀態(tài)五 圖31 狀態(tài)六圖31 狀態(tài)七 圖31 狀態(tài)八四 收獲與心得 本實(shí)驗(yàn)通過對(duì)簡(jiǎn)單智能體真空吸塵器的研究，使我加深了對(duì)智能體、環(huán)境、性能度量等概念的理解。通過傳感器的感知可以得到環(huán)境的感知信息，智能體通過感知到的信息進(jìn)行判斷，再通過執(zhí)行器行動(dòng)，然后引起狀態(tài)的變化，再反饋給環(huán)境。在這個(gè)過程中，性能度量即智能體成功程度標(biāo)準(zhǔn)的具體化是重要的。吸塵器是一個(gè)簡(jiǎn)單的反射型智能體，它通過傳感器感知外面的環(huán)境是什么情況的，然后我們點(diǎn)一下“確定”按鈕即執(zhí)行器，執(zhí)行行動(dòng)，之后把

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

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

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

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

9、外沒有任何關(guān)于狀態(tài)的附加信息?？梢宰龅氖虑橹荒苁巧珊罄^，并區(qū)分目標(biāo)狀態(tài)與非目標(biāo)狀態(tài)。(1)廣度優(yōu)先搜索（Broadth First Search，BFS）：首先擴(kuò)展根節(jié)點(diǎn)，接著擴(kuò)展根節(jié)點(diǎn)的所有后繼，然后再擴(kuò)展它們的后繼，依此類推。通常，在下一層的任何節(jié)點(diǎn)擴(kuò)展之前搜索樹上層深度的所有節(jié)點(diǎn)都已經(jīng)擴(kuò)展過了。圖21 廣度優(yōu)先搜索搜索順序該算法可以使用 FIFO 隊(duì)列實(shí)現(xiàn)，初始時(shí)將開始結(jié)點(diǎn)放入隊(duì)列中，每次取隊(duì)頭結(jié)點(diǎn)，判斷是否為終結(jié)點(diǎn)，不是則將其所有子結(jié)點(diǎn)放入隊(duì)列尾，直到隊(duì)列為空或者找到目標(biāo)結(jié)點(diǎn)為止。如果目標(biāo)結(jié)點(diǎn)在深度 d，那么該算法擴(kuò)展完深度小于 d 的結(jié)點(diǎn)后就將找到目標(biāo)結(jié)點(diǎn)。而且，顯然這是最優(yōu)的。容

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

11、entState do if(!Exist(successor) Push_back(successor);while(!Empty();Return NoAnswer; (2)深度優(yōu)先搜索（Depth First Search，DFS）：總是擴(kuò)展搜索樹當(dāng)前邊緣中最深的節(jié)點(diǎn)。搜索直接推進(jìn)到搜索樹的最深層，那里的節(jié)點(diǎn)沒有后繼節(jié)點(diǎn)。當(dāng)那些節(jié)點(diǎn)擴(kuò)展完之后，它們被從邊緣中去掉，然后搜索算法“向上回到”下一個(gè)還有未擴(kuò)展后繼節(jié)點(diǎn)的稍淺的節(jié)點(diǎn)。圖22 深度優(yōu)先搜索搜索順序深度優(yōu)先算法偽代碼描述如下（堆棧實(shí)現(xiàn)）：Status DFS()Push(begin);doCurrentState = Pop();if

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

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

14、以求解問題了,搜索效率較高。A*搜索算法偽代碼描述如下(優(yōu)先隊(duì)列實(shí)現(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(succes

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

16、的十五張牌，第十六張牌不標(biāo)數(shù)字，記為空格，空格用0表示，空格周圍的棋子可以移動(dòng)到空格中。五 實(shí)驗(yàn)結(jié)果分析1.實(shí)驗(yàn)結(jié)果圖如下：圖5-1 廣度優(yōu)先搜索算法（無解情況）圖5-2 廣度優(yōu)先搜索算法（八數(shù)碼）圖5-3 廣度優(yōu)先搜索算法（十六數(shù)碼） 圖5-4 深度優(yōu)先搜索算法（無解情況）圖5-5 深度優(yōu)先搜索算法（八數(shù)碼）圖5-6 深度優(yōu)先搜索算法（十六數(shù)碼）圖5-7 A*搜索算法（無解情況）圖5-8 A*搜索算法（八數(shù)碼）圖5-9 A*搜索算法（十六數(shù)碼）2.三種算法的優(yōu)缺點(diǎn)簡(jiǎn)評(píng)：三種算法在一定條件下均可得到八數(shù)碼問題的解。前兩種是經(jīng)典的無信息（盲目）搜索算法，后一種是經(jīng)典的有信息（啟發(fā)式）搜索算法。從

17、本文的實(shí)驗(yàn)可以看出，廣度優(yōu)先搜索是一種完備策略，即只要問題有解，它就一定可以找到解。 并且，廣度優(yōu)先搜索找到的解，還一定是路徑最短的解。 這些都是廣度優(yōu)先搜索的優(yōu)點(diǎn)。當(dāng)然，廣度優(yōu)先搜索也存在很多缺點(diǎn)，主要缺點(diǎn)是盲目性較大，尤其是當(dāng)目標(biāo)行點(diǎn)距初始節(jié)點(diǎn)較遠(yuǎn)時(shí)，將產(chǎn)生許多無用的節(jié)點(diǎn)，因此其搜索效率較低，雖然相對(duì)于計(jì)算機(jī)飛速發(fā)展的運(yùn)算速度來講，這已經(jīng)不是關(guān)鍵問題，但仍是下一步有待改進(jìn)的方面。對(duì)于八數(shù)碼問題，深度優(yōu)先搜索對(duì)內(nèi)存的需求很少，它的缺點(diǎn)是它有可能錯(cuò)誤地選擇一條分支并且沿著一條很長(zhǎng)的（甚至是無限的）路徑一直走下去，因此，它是不完備的，不是最優(yōu)的，一般不能保證得到最優(yōu)解。A* 搜索是完備的，與使用無信息搜索相比，使用好的啟發(fā)式還是能節(jié)省大量的時(shí)間和空間。但它又與其啟發(fā)式函數(shù)息息相關(guān)，無法保證得到最優(yōu)解。A*算法可以消耗較少的空間解決問題，但是由于每次選擇均需要尋找評(píng)價(jià)函數(shù)最小的節(jié)點(diǎn)，因此當(dāng)深度增加相應(yīng)的節(jié)點(diǎn)數(shù)目增加時(shí)，