哈工大人工智能原理習題homework-1

1、人工智能原理練習題 -1從習題中選擇自己感興趣的題目進行思考和解答，任何嘗試都是有益的。必要時，仔細閱讀教科書當中的某些章節(jié)。對于加星號的習題，應該編寫程序來完成。第 1 章 人工智能概述1用自己的語言定義：（a）智能，（b）人工智能，（c）智能體。2 用你自己的話定義下列術語：智能體、智能體函數(shù)、智能體程序、理性、自主、反射型智能體、基于模型的智能體、基于目標的智能體、基于效用的智能體、學習智能體。3 對于下列智能體，分別給出任務環(huán)境PEAS 描述：a. 機器人足球運動員；b. 因特網(wǎng)購書智能體；c. 自主的火星漫游者；d. 數(shù)學家的定理證明助手。4 檢查 AI 的文獻，去發(fā)現(xiàn)下列任務現(xiàn)在計

2、算機是否能夠解決：a. 打正規(guī)的乒乓球比賽。b. 在開羅市中心開車。c. 在市場購買可用一周的雜貨。d. 在萬維網(wǎng)上購買可用一周的雜貨。e. 參加正規(guī)的橋牌競技比賽。f. 發(fā)現(xiàn)并證明新的數(shù)學定理。g. 寫一則有內涵的有趣故事。h. 在特定的法律領域提供令人滿意的法律建議。i. 從英語到西班牙語的口語實時翻譯。j. 完成復雜的外科手術。對于現(xiàn)在不可實現(xiàn)的任務，試著找出困難所在，并預測如果可能的話它們什么時候能被克服。5 Loebner 獎每年頒發(fā)給最接近天通過某個版本圖靈測試的程序。查找和匯報Loebner 獎最近的得主。它使用了什么技術？它對AI 目前的發(fā)展水平有什么推動？6 這道習題要探討的

3、是智能體函數(shù)與智能體程序的區(qū)別：a. 是否有不止一個智能體程序可以實現(xiàn)給定的智能體函數(shù)？請舉例，或者說明為什么不可能。b. 有沒有無法用任何智能體程序實現(xiàn)的智能體函數(shù)。c.給定一個機器體系結構，能使每個智能體程序剛好實現(xiàn)一個智能體函數(shù)嗎？d. 給定一個存儲量為n 比特的體系結構，可以有多少種可能的不同智能體程序？7 有一些類眾所周知的難題對計算機而言是難以解決的困難，其它類問題是不能判定的。這是否意味著AI 是不可能的？是如何不精確的？我會搞錯我怎么想的嗎？請討論。8 內省 匯報自己的內心想法 第 2 章 搜索技術1 解釋為什么問題的形式化必須在目標的形式化之后。2 有限的狀態(tài)空間總是導致有限

4、的搜索樹嗎？是樹結構的有限空間呢？你能更精確地說出什么類型的狀態(tài)空間總是導致有限的搜索樹嗎？（改編自Bender， 1996）2 給出下列問題的初始狀態(tài)、目標測試、后繼函數(shù)和耗散函數(shù)。選擇精確得足以實現(xiàn)的形式化。a. 只用四種顏色對平面地圖染色，要求每兩個相鄰的地區(qū)不能染成相同的顏色。b. 一間屋子里有一只3 英尺的猴子，屋子的房頂上掛著一串香蕉，離地面8 英尺 .屋子里有兩個可疊放起來、可移動、可攀登的3 英尺高的箱子。猴子很想得到香蕉。c. 有一個程序，當送入一個特定文件的輸入記錄時會輸出“不合法的輸入記錄”。已知每個記錄的處理獨立于其它記錄。要求找出哪個記錄不合法。d. 有三個水壺，容量

5、分別為12 加侖、 8 加侖和 3 加侖，還有一個水龍頭?？梢园褖匮b滿或者倒空，從一個壺倒進另一個壺或者倒在地上。要求量出剛好1 加侖水。*3 傳教士和野人問題通常描述如下：三個傳教士和三個野人在河的一邊，還有一條能載一個人或者兩個人的船。找到一個辦法讓所有的人都渡到河的另一岸，要求在任何地方野人數(shù)都不能多于傳教士的人數(shù)（可以只有野人沒有傳教士）。 這個問題在AI 領域中很著名，因為它是第一篇從分析的觀點探討問題形式化的論文的主題（Amarel,1968 ）a. 精確地形式化該問題，只描述確保該問題有解所必需的特性。畫出該問題的完全狀態(tài)空間圖。b. 用一個合適的搜索算法實現(xiàn)和最優(yōu)地求解該問題。

6、檢查重復狀態(tài)是個好主意嗎？c. 這個問題的狀態(tài)空間如此簡單，你認為為什么人們求解它卻很困難？*4編寫一個程序，當輸入兩個網(wǎng)頁的URL （鏈接地址）后能找到從一個網(wǎng)頁到另一個網(wǎng)頁的鏈接路徑。什么樣的搜索策略是適合的？雙向搜索是好主意嗎？能用搜索引擎實現(xiàn)一個前輩函數(shù)嗎？5 考慮一個狀態(tài)空間，它的初始狀態(tài)編號為1 ，狀態(tài) n 的后繼函數(shù)返回兩個狀態(tài)，編號為2n 和2n+1 。a. 畫出狀態(tài)1 到 15 的部分狀態(tài)空間圖。b. 假設目標狀態(tài)為11。 列出用以下算法訪問節(jié)點的順序：廣度優(yōu)先搜索，深度限制為3的深度有限搜索，以及迭代深入搜索。c. 雙向搜索是否適合這個問題？如果合適的話，詳細地描述它是怎樣

7、工作的。d. 在雙向搜索中每個方向上的分支因子是什么？e.對（c）的回答是否能提出問題的一種重新形式化，使你可以幾乎不用搜索來求解從狀態(tài)1到達目標狀態(tài)的問題？*6 實現(xiàn)兩種八數(shù)碼游戲的后繼函數(shù)：一種通過復制和編輯八數(shù)碼游戲的數(shù)據(jù)結構立刻生成它的生成一個全部后繼；另一種每次調用的時候通過直接修改父狀態(tài)(需要的話可以撤消修改)新后繼。寫出使用這兩種后繼函數(shù)的迭代深入算法和深度優(yōu)先算法并比較它們的性能。7證明用于GRAPH-SEARCH算法是，單步耗散為常數(shù)的代價一致搜索和廣度優(yōu)先搜索是最優(yōu)的。給出一個單步消耗為常數(shù)的狀態(tài)空間，在其中使用迭代深入的GRAPH-SEARCH 算法會找到非最優(yōu)解。8描述

8、一個狀態(tài)空間，在其中迭代深入搜索比深度優(yōu)先搜索的性能要差很多(例如，一個是O(n2),另一個是 O (n)。*9在下圖中所示的平面上有兩個點，之間有很多凸多邊形障礙物，考慮尋找這兩個點之間的最短路很的問題。這是機器人在擁擠的環(huán)境中求解道路導航問題的一種理想化情況。a.假設狀態(tài)狀態(tài)空間由平面上所有的點( x,y )組成。共有多少個狀態(tài)？共有多少條到達目 標的路徑？b.簡要解釋為什么在這個場景中從一個多邊形的頂點到另一個頂點的最短距離必然由連接 某些多邊形的頂點的直線段組成?，F(xiàn)在定義一個良好的狀態(tài)空間。 這個狀態(tài)空間有多大?c.定義必要的函數(shù)來實現(xiàn)這個搜索問題，包括把一個頂點作為輸入的后繼函數(shù)，它

9、返回從 該頂點出發(fā)能夠通過直線段到達的頂點集合。(不要忘記該頂點所在的多邊形的相鄰頂點。)用直線段的長度作為啟發(fā)函數(shù)。d.應用本章中的一種或多種搜索算法來求解這個領或內的一定范圍的問題，并評價它們的 性能。10跟蹤A*搜索算法用直線距離啟發(fā)式求解從Lugoj到Bucharest問題的過程。按順序列出算法擴展的節(jié)點和每個節(jié)點的f, g, h值。11啟發(fā)式路徑算法 是一個最佳優(yōu)先搜索，它的目標函數(shù)是f(n) = (2 - w) g(n) + w h(n)。算法中w取什么值能保證算法是最優(yōu)的？當 w = 0時，這個算法是什么搜索？w = 1呢？ w = 2呢？12設計一個狀態(tài)空間，在其中用GRAPH

10、-SEARCH的A*算法返回的不是最優(yōu)解，如果它的啟發(fā)函數(shù)h(n)是可采納的但不是一致的。13在第4.2.2節(jié)，我們定義了松弛的八數(shù)碼游戲，其中如果 B是空的，一個棋子可以直接從方 格A移到方格B。這個問題的精確解定義了Gaschnig啟發(fā)式(Gaschnig, 1979)。解釋為什么Gaschnig啟發(fā)式至少和h1 （不在位棋子數(shù)） 一樣精確，并說明它比 %和卜2 （曼哈頓距離） 更精確的情況。你能給出一個有效計算Gaschnig啟發(fā)式的方法嗎？14根據(jù)下面的特殊情況給出算法的名稱：a. k = 1的局部剪枝搜索。b. k = 8的局部剪枝搜索。c.所有時刻T =。的模擬退火搜索。d.種群大

11、小為N = 1的遺傳算法。15有些情況下一個問題找不到好的評價函數(shù)，但是有一個好的比較方法：即只是指出一個節(jié)點是否優(yōu)于另一個節(jié)點而不需要指出它們實際的評價數(shù)值。證明這對于最佳優(yōu)先搜索就已經足夠了。A*算法是否類似？16假設一個智能體在一個教科書中圖4.18所示的3X3大小的迷宮里（如下圖）。智能體知道它的起始位置是（1, 1）,目標位置是（3, 3）,四種行動Up （上），Down （下），Left （左），Right （右）通常可以發(fā)揮效果，除非遇到有墻阻礙。智能體不知道迷宮內部的墻在哪些地 方。在任何給定的狀態(tài)，智能體知道合法行動集合；它也知道一個狀態(tài)是已經訪問過的狀態(tài) 還是新狀態(tài)。GS1

12、23圖4.18 一個簡單的迷宮問題。智能體從狀態(tài)S出發(fā)到達狀態(tài)G,但是智能體對環(huán)境一無所知a.解釋這個聯(lián)機搜索問題如何可以視為在信念狀態(tài)空間中的脫機搜索問題，初始的信念狀態(tài)包括所有可能的環(huán)境布局。初始信念狀態(tài)有多大？信念狀態(tài)空間有多大？b.在初始狀態(tài)可能有多少個不同的感知信息？c.描述這個問題的偶發(fā)性計劃的頭幾個分支。完整的計劃（大約）有多大？注意這個偶發(fā)性計劃是符合給定描述的每個可能環(huán)境的解決方案。因此，即使在未知環(huán)境下搜索和行動的交叉也不是嚴格必需的了。*17在本題中，我們將在機器人導航問題中考察爬山法，以第9題中圖示（教科書圖 3.22）的環(huán)境為例。a.用爬山法算法重復習題 9。智能體會

13、卡在局部最小值上嗎？可能遇到被凸障礙物卡住的情 況嗎？b.構造一個非凸多邊形的環(huán)境，智能體在其中會被卡住。c.修改爬山法算法，在決定下一步的時候不用深度為1的搜索，而用深度為 k的搜索。它將找到最好的k步路徑并且沿著該路徑走一步，然后重復這個過程。d.有沒有某個k使得新的算法保證能避免局部極小值？e.解釋LRT A*是怎樣使新的算法能夠在這種情況下避免局部極小值的。18用你自己的話定義約束滿足問題、約束、回溯搜索、弧相容、后向跳轉和最小沖突。19圖5.1 （澳大利亞地圖）所示的地圖染色問題一共有多少個解？20解釋為什么在 CSP搜索中，一個好的啟發(fā)式選擇變量的時候應該選擇約束最多的變量，而選擇

14、值得時候應該選擇造成約束最少的。21對以下兩個問題給出精確的約束滿足問題的形式化：a.直線地面規(guī)劃：在一個大的矩形里找到不重疊放置許多小的矩形的方法。b.授課日程安排：給定了固定數(shù)量的教授和教室，一個可提供課程的清單，以及可能安排課 程的時間段清單。每個教授有他（或她）能教的課程列表。22分別用回溯算法、前向檢驗算法、MRV和最少約束值啟發(fā)式算法手工求解下圖（圖5.2）中10的密碼算術問題。(b)(a)圖5.2 （a） 一個密碼算術游戲。每個字母表示一個不同的數(shù)字：目標是找到能使加法式子成立的代替字母的數(shù)字，附加約束是前面的數(shù)字不能是0o （b）密碼算術游戲的約束超圖，表示了 Alldiff約

15、束和每列相加的約束。每個約束在圖中用方塊表示，連接到它所約束的變量23 考慮下述的邏輯問題：有5 所不同顏色的房子，住著5 個來自不同國家的人，每個人都喜歡一種不同牌子的香煙、不同牌子的飲料和不同的寵物。給定下列已知條件，請回答問題“斑馬住在哪兒？以及哪所房子里的人喜歡喝水？”：英國人住在紅色的房子里。西班牙人養(yǎng)的是狗。挪威人住在最左邊的第一所房子里。住在黃色房子里的人喜歡抽Kools 牌香煙。喜歡抽Chesterfields牌香煙的人住在養(yǎng)狐貍的人旁邊。挪威人住在藍色房子旁邊。喜歡抽Winston 牌香煙的人養(yǎng)了一只蝸牛。喜歡抽Lucky Strike牌香煙的人喜歡喝橙汁。烏克蘭人喜歡喝茶。

16、日本人喜歡抽Parliaments 牌香煙。喜歡抽 Kools 牌香煙的人住在養(yǎng)馬的人的隔壁。住在中間房子里的人喜歡喝牛奶。討論把這個問題表示成CSP 問題的不同方法。你認為哪種比較好，為什么？24這道習題以井字棋（圈與十字游戲）為例子，練習博弈中的基本概念。我們定義Xn為恰好有n 個 X 而沒有 O 的行、列或者對角線的數(shù)目。同樣On 為正好有n 個 O 的行、列或者對角線的數(shù)目。效用函數(shù)給X3=1 的局部賦值+1，給O3=1 的局部賦值-1。所有其它終止局面效用值為 0。對于非終止局面，我們使用線性的評價函數(shù)，定義為Eval （s） = 3X2 （s） + Xi （s） - （3。2 （s

17、） + Oi （s）。a. 估算大約總共有多少種可能的井字棋局面？b. 考慮到對稱性，給出從空棋盤開始到深度為2 的完整博弈樹（例如，在棋盤上一個X 和一個 O 的局面）c. 標出深度為2 的所有局面的評價值。d. 使用極小極大值算法標出深度為i 和 0 的局面的回傳值，并根據(jù)這些值選出最佳的起始步。e.假設節(jié)點按對a - 3剪枝的最優(yōu)順序生成，圈出如果使用a - 3剪枝將被剪掉的深度為2的節(jié)點。25證明下面的斷言：對于每棵博弈樹，MAX使用極小極大值算法對抗非最優(yōu)招數(shù)的MIN得到的效用值不會比對抗最優(yōu)招數(shù)的MIN得到的效用值低。你能構造出一棵博弈樹，使得MA刖非最優(yōu)策略對抗非最優(yōu) MIN可以

18、做得比使用最優(yōu)策略更好嗎？26考慮圖6.14 （下頁圖）中描述的兩人游戲。a. 用下面的約定，畫出完整的博弈樹：每個狀態(tài)用（Sa, Sb）表示，其中Sa和Sb表示棋子的位置。每個終止狀態(tài)外面畫方框，并在圓圈里寫出它的博弈值。把循環(huán)狀態(tài)（已經在到根節(jié)點的路徑上出現(xiàn)過的狀態(tài)）放在雙方框內。由于不清楚怎樣給循環(huán)狀態(tài)賦值，在圓圈里標記一個“？”。b. 現(xiàn)在給每個節(jié)點標記回傳得極小極大值（也標記在圓圈里）。解釋怎樣處理“？”值和為什么。c.解釋標準的極小極大值算法為什么在這棵博弈樹中會失敗，簡要地勾畫你可能如何改進 它，并在問題（b）的圖上畫出你的答案。你的改進算法對于所有包含循環(huán)的游戲都能給 出最優(yōu)決

19、策嗎？d.這個4-方格游戲可以推廣到 n個方格，對于任意n2。證明如果n是偶數(shù)，A一定能贏;而n是奇數(shù)，A 一定會輸。圖6.14 一個簡單游戲的初始局面。游戲者A先走。然后兩個游戲者輪流走棋，每個人必須把自己的棋子移動到任一個方向上的相鄰空位中。如果對方的棋子占據(jù)著相鄰的位置，你可以跳過對方的棋子到下一個空位，如果有空位的話。（例如，A在位置3, B在位置2,那么A可以移回1。）當一方的棋子移動到對方的棋盤端點時游戲結束。如果A先到達位置4, A的游戲值為+1;如果B先到位置1, A的游戲值-1。27給出一個關于 -3剪枝正確性的形式化證明。要做到這個，考慮圖 6.15中的情況。問題為 是否要

20、剪掉節(jié)點 nj,它是一個 MAX節(jié)點，也是 小的一個后代?；镜乃悸肥钱斍覂H當m的極小極大值可以被證明獨立于 nj的值時，才剪枝。圖6.15考慮是否剪掉節(jié)點nj時的情形a. n i的值由下面公式給出ni = min （n2,n 21, , , n2b2）為n2找到類似的表達式，因此得到用nj表示ni的表達式。b.節(jié)點ni的極小極大值已知，li是在節(jié)點ni左側深度為i的節(jié)點的極小值（或者極大值）。 同樣，m是在ni右側深度為i的未探索過的節(jié)點的極小值（或者極大值）。用li和ri的值重寫你的ni表達式。c.現(xiàn)在調整你的表達式來說明為了影響ni, nj必須不超出由li值得到的一個特定界限。d.對于n

21、是MIN節(jié)點的情況重復上面的過程。28描述把標準的博弈方法運用到連續(xù)的物理狀態(tài)空間中進行的游戲，諸如網(wǎng)球、臺球和門球, 效果會如何？29對于下列問題試用深度優(yōu)先、廣度優(yōu)先、A*算法分別解決，如果步驟太多，可以擇要加以討論。（1）有2n個硬幣，其中除一個略重外，其余2n-1個都一樣重，如果有一架無祛碼的天平，請求出：至少稱多少次才能把略重的那個硬幣找出來？（提示：把2n個硬幣對應于一個 2n維狀態(tài)向量，其中每個硬幣對應于（1）未知（2）略重（3）正常三種狀態(tài)。）（2）下圖是一張西極洲地圖， 共14個國家，試用上述3種狀態(tài)搜索法來解該圖的四色問題。（提示：可把狀態(tài)設計為一個別14個維向量，每個分量

22、可為紅、黃、藍、綠四色之一。任意選擇一個向量，例如全紅，為初始狀態(tài)，每步改變其中的一個顏色，直到相鄰國家顏色都不同為止）（3）下圖是由四個圓環(huán)組成的盤面，每個圓環(huán)都可以獨立地繞中心轉動，每次轉動90°。圖中所示的是初始狀態(tài)，要達到目標狀態(tài)是每條半徑上的數(shù)字總和為12。試用上述3種狀態(tài)搜索法搜索，并寫出搜索步驟。(4)有四個正方塊。在每個正方塊上任意選擇四面，分別涂上紅、黃、藍、綠四種顏色，其余 兩面隨意各涂這四色之一。請你把四個方塊疊成一根方柱，使方柱每一面都具備四種不同顏色， 并把搜索過程用狀態(tài)空間法描述出來。63.3萬柱問題(5)有2n個硬幣排成一行，n個正向的在左，n個反向的在右，規(guī)定每次移動時必須把緊挨著的兩個一起移，只許旋轉，要求至多用n步把它們變成正反相間的形式，并且中間不許出現(xiàn)空檔。下圖n=3的情形。初始：正正正反反反第1步移動：正反反反正正第2步移動：