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

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

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

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

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

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

6、; 1, 2, 3; 1, 2, 3, 4, 5, 6, 7; 1, 2, 3, 4, 5, 8, 9, 10, 11II簡(jiǎn)述廣度優(yōu)先搜索、深度優(yōu)先搜索、迭代深入搜索的基本原理，及其算法性能分析。參考解答：自己對(duì)照課本及課件理解自行總結(jié)。Homework #3（啟發(fā)搜索）I用A*算法解決下圖所示八數(shù)碼問題。s*參考解答:CgUlP=5 f=516 475A2 8 316 47 5P=6f=7-2 8 3147 6 5E irD2 8 3P=4f=52 8 316 47 5F147 0 5P=5f=7P=Sf=7條 318 47 6 5P=3f=5G2 318 47 6 5P=2f=5H 丁廠

7、18 4 7 6 5P=5f=7P=4f=712 3.8 47 6 5h：+=L 的4P=1f=51 ；2 3, v 3= -12 3.8.4P=07 8 47 6 5f=56 5P=2f=7II.某問題的狀態(tài)空間圖如下圖所示，其中括號(hào)內(nèi)標(biāo)明的是各節(jié)點(diǎn)的h值，弧線邊的數(shù)字是該弧線的 耗散值，試用A算法求解從初始節(jié)點(diǎn)S到目標(biāo)節(jié)點(diǎn)T的路徑。要求給出搜索圖，標(biāo)明各節(jié)點(diǎn)的f值， 及各節(jié)點(diǎn)的擴(kuò)展次序，并給出求得的解路徑。參考解答：搜索圖如下頁圖所示，其中括號(hào)內(nèi)標(biāo)出的是節(jié)點(diǎn)的f值，圓圈內(nèi)的數(shù)字是擴(kuò)展的次序。 得到的解路徑為：S-B-F-J-T。附加題：考慮下圖所示搜索問題5Node/圮hiS0.56A03

8、.5B042C09 m3.5D0.53G000a.對(duì)于表中所列出的3個(gè)啟發(fā)函數(shù)，哪（幾）個(gè)是可納的？請(qǐng)做簡(jiǎn)要分析。b.分別使用上述三個(gè)啟發(fā)函數(shù)，進(jìn)行A*搜索，請(qǐng)分別給出它們返回的解路徑。h0：hi:h2：參考解答：h。和是可納的，因?yàn)閔2（C）h*（C）,所以h2不是可納的。h: S B C Gh1: S B C Gh2: S T B T D T GHomework #4（約束滿足問題）I你負(fù)責(zé)安排計(jì)科專業(yè)的課程的授課教師，課程安排在星期一、星期三和星期五。計(jì)科專業(yè)共有5個(gè)班，邀請(qǐng)校外3位資深教授來講授課程。你需要確定哪個(gè)班級(jí)由哪位教授上課，你的安排計(jì)劃要滿足 以下約束：同一時(shí)刻每個(gè)教授只能上

9、 1 個(gè)班的課。（12 分）具體的班級(jí)課程對(duì)應(yīng)關(guān)系如下：1班：程序設(shè)計(jì)（上午8:00-9:00）2班：人工智能（上午8:30-9:30）3班：自然語言處理（上午9:00-10:00）4班：計(jì)算機(jī)視覺（上午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.將上述問題形式化為CSP問題，每個(gè)班作為一個(gè)變量，進(jìn)行滿足約束關(guān)系的賦值（注：形式化不需 要給出具體的賦值）。變量及其值域：C1C2C3C4C5約束關(guān)系：CB,CA,B,CA,B,CB,CC1 豐 C2,

10、C2 豐 C3, C3 豐 C4, C4 豐 C5, C2 豐 C4, C3 豐 C5.b.根據(jù)你形式化的CSP問題，畫出相應(yīng)的約束圖。根據(jù)約束圖應(yīng)用弧約束關(guān)系后，各變量的值域?qū)l(fā)生變化，請(qǐng)寫出應(yīng)用約束關(guān)系后的值域。值域變化如下：C1 CC2 BC3 A,CC4 A,CC5 B,C給出該CSP問題的一個(gè)解。C1 = C, C2 = B, C3 = C, C4 = A, C5 = B 是問題的一個(gè)解。e簡(jiǎn)述約束滿足問題形式化的過程步驟?Homework #5（對(duì)抗搜索和博弈）1下圖所示博弈樹，按從左到右的順序進(jìn)行a-p剪枝搜索，試標(biāo)明各生成節(jié)點(diǎn)的回推值，何處發(fā)生 剪枝，及應(yīng)選擇的走步。參考解答:

11、II.下圖所示博弈樹，按從左到右的順序進(jìn)行a-p剪枝搜索，試標(biāo)明各生成節(jié)點(diǎn)的回推值，何處發(fā)生 剪枝，及應(yīng)選擇的走步。5 -5 U 1 5 10 -1 -2 0 14 5-1oI5 -3 3 3 -3 0 -2 3 5 2 5 -5 0 1 5 1 -3 0 -5 5 -3 3 2 3 -3 0 l-2 0 1 4 5 1-1-1 3 -3 20 QtJ口口口 附加題：考慮下圖所示的極大極小樹:請(qǐng)用X在圖上標(biāo)出應(yīng)用a - p剪枝算法不會(huì)訪問到的結(jié)點(diǎn)（假設(shè)子結(jié)點(diǎn)的訪問順序?yàn)閺淖笾劣遥?。參考解?S. (15 pdints.) Game Trees: The BalancerConsider ihp

12、 following zero-sum game, in which Lhe utilities L偵(s arc shown for the first payer (A). Assume the second player (R) is a mmirniaer: E hoDdi the opposite utiUitis to A? = -L偵(幻一 In this rase一 l!s mALniizaLion of Ue 也(xjuivalenL to miniiniatLon of Ua : Le. the compuLation in Btndard minima.(a) (2 po

13、ints) In each node, write【偵時(shí).lh (minimax) utility of that stAtc for player A,畋umifig that H is a minimizer.Ansviier: Displayed Abdve,(b) (3 points) Crass off any nodes which will be skipped bypruning.心unilng left-to-right ardrine.Aitsvrer: Displayed Abdve,Assume now thL R in not & inininiLzer. bul 角 baianccr. A balancer does not iry to HiLnimiz A 近 scor bui