人工智能(考點(diǎn)復(fù)習(xí)整理)

1、Homework #1(搜索問(wèn)題). 水壺問(wèn)題考慮以下問(wèn)題:“三個(gè)水壺里面裝有水，水壺上沒(méi)有任何的測(cè)量標(biāo)記?？梢园衙總€(gè)水壺都倒空；也可以把水從一個(gè)水壺倒入到另一個(gè)水壺中，當(dāng)一個(gè)倒空或者一個(gè)完全裝滿(mǎn)時(shí)，倒水會(huì)立即停止。此外，不再允許其他的動(dòng)作。三個(gè)水壺的容量分別為15，7和3升。需要量出正好2升水?！? 將以上問(wèn)題表達(dá)為一個(gè)搜索問(wèn)題，即給出（1）狀態(tài)的描述，（2）初始狀態(tài)，（3）目標(biāo)測(cè)試，及（4）后繼函數(shù)。說(shuō)明：不要列出所有的狀態(tài)；對(duì)于后繼函數(shù)，不需要把每個(gè)狀態(tài)的所有后繼都列出來(lái)，但是應(yīng)該描述清楚針對(duì)給定的任意狀態(tài)如何得到其后繼。此處不要求對(duì)問(wèn)題的解進(jìn)行描述。2 畫(huà)出上述搜索問(wèn)題的搜索樹(shù)，畫(huà)到深

2、度為2即可（根節(jié)點(diǎn)深度為0）。在深度為0時(shí)分支因子是多少？深度為1時(shí)分支因子又是多少？參考解答：1. (1) 狀態(tài)描述： x, y, z, 其中 x, y, z 分別為3個(gè)水壺中水的重量（整數(shù)）。(2) 初始狀態(tài)： 15, 7, 3. (3) 目標(biāo)測(cè)試：對(duì)狀態(tài) x, y, z, 有x=2, or y=2, or z=2(4) 后繼函數(shù)：給定 x, y, z, 生成以下：- 0, y, z, x, 0, z, and x, y, 0 (將某一壺里的水倒空)- x-min(x+y,7)+y, min(x+y,7), z (將 x 倒入 y)- x, y-min(y+z,3)+z, min(y+z,

3、3) (將 y倒入z)- min(x+z,15), y, z-min(x+z,15)+x (將 z倒入x)- x-min(x+z,3)+z, y, min(x+z,3) (將 x倒入 z)- min(x+y,15), y-min(x+y,15)+x, z (將 y倒入x)- x, min(y+z,7), z-min(y+z,7)+y (將 z倒入y)2. 搜索樹(shù)根節(jié)點(diǎn)： 15,7,3深度1的節(jié)點(diǎn)： 0,7,3, 15,0,3, 15,7,0 (因?yàn)樗械乃畨卦诔跏紩r(shí)均裝滿(mǎn)了水，所以在唯一可能的動(dòng)作是將壺里的水倒空)深度2的節(jié)點(diǎn)：0,7,3 = 0,0,3, 0,7,0, 7,0,3, 3,7,

4、015,0,3 = 0,0,3, 15,0,0, 8,7,3, 15,3,015,7,0 = 0,7,0, 15,0,0, 12,7,3, 15,4,3深度為0時(shí)分支因子為3，深度為1時(shí)分支因子為4。 雙8數(shù)碼問(wèn)題考慮雙8數(shù)碼問(wèn)題（這是8數(shù)碼問(wèn)題的組合，即要求將兩個(gè)8數(shù)碼牌經(jīng)過(guò)移動(dòng)使其布局到達(dá)各自的目標(biāo)狀態(tài)）。 a. 將雙8數(shù)碼問(wèn)題進(jìn)行問(wèn)題形式化；b. 整個(gè)狀態(tài)空間有多少種狀態(tài)？可到達(dá)的狀態(tài)又有多少？（給出表達(dá)式，不需計(jì)算出具體數(shù)值）參考解答：a. 初始狀態(tài)：兩個(gè)任意的8數(shù)碼布局；后繼函數(shù)：在未解決的8數(shù)碼棋盤(pán)上移動(dòng)一步；目標(biāo)測(cè)試：兩個(gè)8數(shù)碼棋盤(pán)均到達(dá)目標(biāo)狀態(tài)；路徑耗散：每一步為單位耗散。b.

5、 每一個(gè)8數(shù)碼問(wèn)題有9！個(gè)狀態(tài)，其中一半是可達(dá)的；則兩個(gè)8數(shù)碼問(wèn)題聯(lián)合起來(lái)有（9?。?/2個(gè)可達(dá)狀態(tài)。Homework #2(盲目搜索). 考慮這樣一個(gè)狀態(tài)空間，每一個(gè)狀態(tài)是一個(gè)不同的正整數(shù)，即為集合中的一個(gè)元素。后繼函數(shù)為：狀態(tài)返回兩種狀態(tài)：數(shù)字和；初始狀態(tài)為1。 (12分) a. 畫(huà)出包含狀態(tài)1至15狀態(tài)的狀態(tài)圖。 b. 令目標(biāo)狀態(tài)為11。搜索算法在生成了搜索樹(shù)的一個(gè)節(jié)點(diǎn)，該節(jié)點(diǎn)的狀態(tài)為時(shí)，訪問(wèn)狀態(tài)。分別列出以下搜索算法的訪問(wèn)次序。 a) 廣度優(yōu)先搜索 b) 深度限制搜索（限制深度為3）c) 迭代深入搜索參考解答：a. b. a) BFS: 1, 2, 3, 4, 5, 6, 7, 8,

6、9, 10, 11 b) DFS: 1, 2, 3, 4, 5, 8, 9, 10, 11 c) IDS: 1; 1, 2, 3; 1, 2, 3, 4, 5, 6, 7; 1, 2, 3, 4, 5, 8, 9, 10, 11 . 簡(jiǎn)述廣度優(yōu)先搜索、深度優(yōu)先搜索、迭代深入搜索的基本原理，及其算法性能分析。參考解答：自己對(duì)照課本及課件理解自行總結(jié)。Homework #3(啟發(fā)搜索). 用A*算法解決下圖所示八數(shù)碼問(wèn)題。 參考解答：. 某問(wèn)題的狀態(tài)空間圖如下圖所示，其中括號(hào)內(nèi)標(biāo)明的是各節(jié)點(diǎn)的h值，弧線(xiàn)邊的數(shù)字是該弧線(xiàn)的耗散值，試用A算法求解從初始節(jié)點(diǎn)S到目標(biāo)節(jié)點(diǎn)T的路徑。要求給出搜索圖，標(biāo)明各節(jié)

7、點(diǎn)的f值，及各節(jié)點(diǎn)的擴(kuò)展次序，并給出求得的解路徑。 參考解答：搜索圖如下頁(yè)圖所示，其中括號(hào)內(nèi)標(biāo)出的是節(jié)點(diǎn)的f值，圓圈內(nèi)的數(shù)字是擴(kuò)展的次序。得到的解路徑為：S-B-F-J-T。附加題：考慮下圖所示搜索問(wèn)題a. 對(duì)于表中所列出的3個(gè)啟發(fā)函數(shù)，哪（幾）個(gè)是可納的？請(qǐng)做簡(jiǎn)要分析。b. 分別使用上述三個(gè)啟發(fā)函數(shù)，進(jìn)行A*搜索，請(qǐng)分別給出它們返回的解路徑。 h0:h1:h2:參考解答：a. h0和h1是可納的，因?yàn)閔2(C)h*(C),所以h2不是可納的。b. Homework #4(約束滿(mǎn)足問(wèn)題). 你負(fù)責(zé)安排計(jì)科專(zhuān)業(yè)的課程的授課教師，課程安排在星期一、星期三和星期五。計(jì)科專(zhuān)業(yè)共有5個(gè)班，邀請(qǐng)校外3位資

8、深教授來(lái)講授課程。你需要確定哪個(gè)班級(jí)由哪位教授上課，你的安排計(jì)劃要滿(mǎn)足以下約束：同一時(shí)刻每個(gè)教授只能上1個(gè)班的課。 （12分）具體的班級(jí)課程對(duì)應(yīng)關(guān)系如下：1班：程序設(shè)計(jì)（上午8:00-9:00）2班：人工智能（上午8:30-9:30）3班：自然語(yǔ)言處理（上午9:00-10:00）4班：計(jì)算機(jī)視覺(jué)（上午9:00-10:00）5班：機(jī)器學(xué)習(xí)（上午9：30-10：30）資深教授具體講授課程如下：A教授可以上3和4班的課B教授可以上2、3、4和5班的課C教授可以上1、2、3、4和5班的課a. 將上述問(wèn)題形式化為CSP問(wèn)題，每個(gè)班作為一個(gè)變量，進(jìn)行滿(mǎn)足約束關(guān)系的賦值（注：形式化不需要給出具體的賦值）。變

9、量及其值域：C1 CC2 B,CC3 A,B,CC4 A,B,CC5 B,C 約束關(guān)系：C1C2, C2C3, C3C4, C4C5, C2C4, C3C5.b. 根據(jù)你形式化的CSP問(wèn)題，畫(huà)出相應(yīng)的約束圖。c. 根據(jù)約束圖應(yīng)用弧約束關(guān)系后，各變量的值域?qū)l(fā)生變化，請(qǐng)寫(xiě)出應(yīng)用約束關(guān)系后的值域。值域變化如下：C1 CC2 BC3 A,CC4 A,CC5 B,Cd. 給出該CSP問(wèn)題的一個(gè)解。C1 = C, C2 = B, C3 = C, C4 = A, C5 = B 是問(wèn)題的一個(gè)解。e 簡(jiǎn)述約束滿(mǎn)足問(wèn)題形式化的過(guò)程步驟？Homework #5(對(duì)抗搜索和博弈). 下圖所示博弈樹(shù)，按從左到右的順序進(jìn)行-剪枝搜索，試標(biāo)明各生成節(jié)點(diǎn)