人工智能作業(yè)一

1、作業(yè)一1. 對于下列活動，分別給出任務(wù)環(huán)境的PEAS描述，并按照2.3.2節(jié)列出的性質(zhì)進行分析:(a) 在互聯(lián)網(wǎng)購買AI舊書Performance MeasureEnvironmentActuatorsSensors購買的舊書性價比高，搜索快速（貨比三家），付款的安全性，好的交互功能（與賣家或其他買家溝通）互聯(lián)網(wǎng)，賣家，其他買家購書平臺（終端），計算機AI舊書價位比對系統(tǒng)(b) 對著墻壁練網(wǎng)球Performance MeasureEnvironmentActuatorsSensors動作準確度，反應(yīng)迅速，動作連貫性，力度控制的精確度，對球落點控制的精確度訓(xùn)練場地，其他訓(xùn)練者，場地管理人員機械臂

2、，球拍壓力傳感器，視覺傳感器（判斷球落點）(c) 在一次拍賣中對一個物體投標Performance MeasureEnvironmentActuatorsSensors對物體價值評估的準確性，反應(yīng)迅速，制定投標價格的合理性被投標物體，其他競投者，拍賣現(xiàn)場計算器（統(tǒng)計、計算），機械臂（用于投標）聽覺傳感器（感知其他競投著報價），語音傳感器（自己報價）2. 先建立一個完整的搜索樹，起點是S,終點是G,如下圖,節(jié)點旁的數(shù)字表示到達目標狀態(tài)的距離，然后用以下方法表示如何進行搜索。圖一首先，我們畫出圖一對應(yīng)的完整的搜索樹(按節(jié)點字母從小到大順序依次畫出)：(a).深度優(yōu)先:我們知道深度優(yōu)先搜索是無信息搜

3、索，按照編程的習慣，下圖中深度優(yōu)先搜索的順序是按照節(jié)點的A-G的排序進行的(b).廣度優(yōu)先:我們知道一般的廣度優(yōu)先搜索也是無信息搜索，按照編程的習慣，下圖中廣度優(yōu)先搜索的順序同樣是是按照節(jié)點的A-G的排序進行的(c).爬山法:對于爬山法我們需要了解的是，它是簡單的循環(huán)過程，不斷向最優(yōu)方向移動。該算法不需要維護搜索樹，當前的節(jié)點的數(shù)據(jù)結(jié)構(gòu)只需要記錄當前狀態(tài)和目標函數(shù)值。此外，爬山法不會考慮與當前狀態(tài)不相鄰的狀態(tài)。從S出發(fā)，與S鄰近最佳的狀態(tài)為B，依次往下，一旦找到目標狀態(tài)則算法終止，這也就是為什么爬山法容易陷入局部最優(yōu)。(d).最佳優(yōu)先:最佳優(yōu)先算法的結(jié)點是基于評價函數(shù)f(n)去擴展的，評估價值

4、最低的結(jié)點首先選擇進行擴展。最佳優(yōu)先算法和一致代價搜索算法實現(xiàn)類似，不同的是最佳優(yōu)先是根據(jù)f值而不是根據(jù)g值對優(yōu)先級隊列排隊。3. 圖二是一棵部分展開的搜索樹，其中樹的邊記錄了對應(yīng)的單步代價，葉子節(jié)點標注了到達目標結(jié)點的啟發(fā)式函數(shù)的代價值，假定當前狀態(tài)位于結(jié)點A。圖二(a) 用下列的搜索方法來計算下一步需要展開的葉子節(jié)點。注意必須要有完整的計算過程，同時必須對擴展該葉子節(jié)點之前的節(jié)點順序進行記錄：1. 貪婪最佳優(yōu)先搜索：首先，貪婪最佳優(yōu)先算法是試圖擴展離目標最近的節(jié)點，它只用到啟發(fā)信息，也就是f(n)=h(n)。如圖，h(B)是未知的，但是根據(jù)三角不等式，我們可以知道7<=h(B)<

5、;=13。因此，先擴展C結(jié)點。2. 一致代價搜索一致性代價搜索擴展的是路徑消耗最小的結(jié)點。所以一致代價搜索接下來擴展結(jié)點的順序為BDEFGHC3. A*樹搜索A*搜索對結(jié)點的評估結(jié)合了g(n)，即到達此結(jié)點已經(jīng)花費的代價，和h(n)，從該結(jié)點到目標結(jié)點所花的代價:f(n)=g(n)+h(n)。由于都是從A結(jié)點開始擴展，所以對于下一步可擴展的結(jié)點的f(D)=18，f(C)=21, 10<=f(B)<=16。因此，當先擴展B結(jié)點，否則先擴展D結(jié)點。(b) 討論以上三種算法的完備性和最優(yōu)性。貪婪最佳優(yōu)先搜索試圖擴展離目標最近的結(jié)點，理由是這樣可以很快找到解。貪婪最佳優(yōu)先搜索于深度優(yōu)先搜索

6、類似，即使是有限狀態(tài)空間，他也是不完備的，容易陷入死胡同或者導(dǎo)致死循環(huán)；一致代價搜索按結(jié)點的最優(yōu)路徑順序擴展結(jié)點，這是對任何單步代價函數(shù)都是最優(yōu)的算法，它不再擴展深度最淺的結(jié)點。一致代價搜索與寬度優(yōu)先搜索類似，是完備的；A*搜索是完備的，此外，A*算法對于任何給定的一致的啟發(fā)函數(shù)都是效率最優(yōu)的。4. 給定一個啟發(fā)式函數(shù)滿足h(G)=0,其中G是目標狀態(tài)，證明如果h是一致的，那么它是可采納的。一致性（單調(diào)性）的定義：如果對于每個結(jié)點n和通過任意行動a生成的n的每個后繼結(jié)點n，從結(jié)點n到達目標的估計代價不大于從n到n單步的代價與從n到達目標的估計代價之和：h(n)<=c(n,a,n)+h(n)可采納性的定義：f(n)=g(n)+h(n)可采納行要求f(n)永遠不會超過結(jié)點n的解的實際代價證明：真實代價:f(n)=g(n)+c(n,a1,n1)+ c(n1,a2,n2)+ c(n2,a3,n3)+ c(nm,a(m+1),G)評估代價: f(n)=g(n)+h(n)即證明 f(n)<=f(n)根據(jù)一致性的定義，有f(n)=g(n)+h(n)<= g(n)+ c(n,a1,n1)+h(n1) <= g(n)+ c(n,a1,