人工智能及其應(yīng)用(蔡自興)課后答案

.第二章 知識(shí)表示方法2-1 狀態(tài)空間法、問(wèn)題歸約法、謂詞邏輯法和語(yǔ)義網(wǎng)絡(luò)法的要點(diǎn)是什么？它們有何本質(zhì)上的聯(lián)系及異同點(diǎn)?答：狀態(tài)空間法：基于解答空間的問(wèn)題表示和求解方法，它是以狀態(tài)和算符為基礎(chǔ)來(lái)表示和求解問(wèn)題的。一般用狀態(tài)空間法來(lái)表示下述方法：從某個(gè)初始狀態(tài)開(kāi)始，每次加一個(gè)操作符，遞增的建立起操作符的試驗(yàn)序列，直到達(dá)到目標(biāo)狀態(tài)為止。問(wèn)題規(guī)約法：已知問(wèn)題的描述，通過(guò)一系列變換把此問(wèn)題最終變成一個(gè)子問(wèn)題集合：這些子問(wèn)題的解可以直接得到，從而解決了初始問(wèn)題。問(wèn)題規(guī)約的實(shí)質(zhì)：從目標(biāo)（要解決的問(wèn)題）出發(fā)逆向推理，建立子問(wèn)題以及子問(wèn)題的子問(wèn)題，直至最后把出示問(wèn)題規(guī)約為一個(gè)平凡的本原問(wèn)題集合。謂詞邏輯法：采用謂詞合式公式和一階謂詞算法。要解決的問(wèn)題變?yōu)橐粋€(gè)有待證明的問(wèn)題，然后采用消解定理和消解反演萊證明一個(gè)新語(yǔ)句是從已知的正確語(yǔ)句導(dǎo)出的，從而證明這個(gè)新語(yǔ)句也是正確的。語(yǔ)義網(wǎng)絡(luò)法：是一種結(jié)構(gòu)化表示方法，它由節(jié)點(diǎn)和弧線或鏈組成。節(jié)點(diǎn)用于表示物體、概念和狀態(tài)，弧線用于表示節(jié)點(diǎn)間的關(guān)系。語(yǔ)義網(wǎng)絡(luò)的解答是一個(gè)經(jīng)過(guò)推理和匹配而得到的具有明確結(jié)果的新的語(yǔ)義網(wǎng)絡(luò)。語(yǔ)義網(wǎng)絡(luò)可用于表示多元關(guān)系，擴(kuò)展后可以表示更復(fù)雜的問(wèn)題2-2 設(shè)有3個(gè)傳教士和3個(gè)野人來(lái)到河邊，打算乘一只船從右岸渡到左岸去。該船的負(fù)載能力為兩人。在任何時(shí)候，如果野人人數(shù)超過(guò)傳教士人數(shù)，那么野人就會(huì)把傳教士吃掉。他們?cè)鯓硬拍苡眠@條船安全地把所有人都渡過(guò)河去?用Si(nC, nY) 表示第i次渡河后，河對(duì)岸的狀態(tài)，nC表示傳教士的數(shù)目，nY表示野人的數(shù)目，由于總?cè)藬?shù)的確定的，河對(duì)岸的狀態(tài)確定了，河這邊的狀態(tài)也即確定了?？紤]到題目的限制條件，要同時(shí)保證，河兩岸的傳教士數(shù)目不少于野人數(shù)目，故在整個(gè)渡河的過(guò)程中，允許出現(xiàn)的狀態(tài)為以下3種情況：1. nC=02. nC=33. nC=nY=0 (當(dāng)nC不等于0或3)用di(dC, dY)表示渡河過(guò)程中，對(duì)岸狀態(tài)的變化，dC表示，第i次渡河后，對(duì)岸傳教士數(shù)目的變化，dY表示，第i次渡河后，對(duì)岸野人數(shù)目的變化。當(dāng)i為偶數(shù)時(shí)，dC,dY同時(shí)為非負(fù)數(shù)，表示船駛向?qū)Π?，i為奇數(shù)時(shí)，dC, dY同時(shí)為非正數(shù)，表示船駛回岸邊。初始狀態(tài)為S0(0, 0)，目標(biāo)狀態(tài)為S0(3, 3)，用深度優(yōu)先搜索的方法可尋找渡河方案。在此，用圖求法該問(wèn)題，令橫坐標(biāo)為nY, 縱坐標(biāo)為nC，可行狀態(tài)為空心點(diǎn)表示，每次可以在格子上，沿對(duì)角線移動(dòng)一格，也可以沿坐標(biāo)軸方向移動(dòng)1格，或沿坐標(biāo)軸方向移動(dòng)2格。第奇數(shù)次數(shù)狀態(tài)轉(zhuǎn)移，沿右方，上方，或右上方移動(dòng)，第偶數(shù)次數(shù)狀態(tài)轉(zhuǎn)移，沿左方，下方，或左下方移動(dòng)。1nCnY231320從(0,0)開(kāi)始，依次沿箭頭方向改變狀態(tài)，經(jīng)過(guò)11步之后，即可以到達(dá)目標(biāo)狀態(tài)(3,3)，相應(yīng)的渡河方案為：d1(1,1)-d2(-1,0)-d3(0,2)-d4(0,-1)-d5(2,0)-d6(-1,-1)-d7(2,0)-d8(0,-1)-d9(0,2)-d10(-1,0)-d11(1,1)2-3 利用圖2.3，用狀態(tài)空間法規(guī)劃一個(gè)最短的旅行路程：此旅程從城市A開(kāi)始，訪問(wèn)其他城市不多于一次，并返回A。選擇一個(gè)狀態(tài)表示，表示出所求得的狀態(tài)空間的節(jié)點(diǎn)及弧線，標(biāo)出適當(dāng)?shù)拇鷥r(jià)，并指明圖中從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最佳路徑。71071013966510BEDAC圖 2.32-4 試說(shuō)明怎樣把一棵與或解樹(shù)用來(lái)表達(dá)圖2.28所示的電網(wǎng)絡(luò)阻抗的計(jì)算。單獨(dú)的R、L或C可分別用R、jL或1/jC來(lái)計(jì)算，這個(gè)事實(shí)用作本原問(wèn)題。后繼算符應(yīng)以復(fù)合并聯(lián)和串聯(lián)阻抗的規(guī)則為基礎(chǔ)。圖 2.28約定，用原來(lái)的與后繼算法用來(lái)表達(dá)并聯(lián)關(guān)系，用原來(lái)的或后繼算法用來(lái)表達(dá)串聯(lián)關(guān)系ZR1Z2Z3Z21Z22Z31Z32R2C1Z211R3C2L2R4L3C4L4C3L12-5 試用四元數(shù)列結(jié)構(gòu)表示四圓盤(pán)梵塔問(wèn)題，并畫(huà)出求解該問(wèn)題的與或圖。用四元數(shù)列 (nA, nB, nC, nD) 來(lái)表示狀態(tài)，其中nA表示A盤(pán)落在第nA號(hào)柱子上，nB表示B盤(pán)落在第nB號(hào)柱子上，nC表示C盤(pán)落在第nC號(hào)柱子上，nD表示D盤(pán)落在第nD號(hào)柱子上。初始狀態(tài)為 1111，目標(biāo)狀態(tài)為 333311113333111122212221222322233333111133113311332133212221222311231123113311333333111121112111231123113311332113211321122112212221222332233223312331231123113321332133233323333333如圖所示，按從上往下的順序，依次處理每一個(gè)葉結(jié)點(diǎn)，搬動(dòng)圓盤(pán)，問(wèn)題得解。2-6 把下列句子變換成子句形式：(1) (x)P(x)P(x)(2) xy(On(x,y)Above(x,y)(3) xyz(Above(x,y)Above(y,z)Above(x,z)(4) (x)P(x)（y）p(y)p(f(x,y)(y)Q(x,y)P(y)(1) (ANY x) P(x)P(x) (ANY x) P(x) OR P(x)P(x) OR P(x)最后子句為P(x) OR P(x)(2) (ANY x) (ANY y) On(x,y)Above(x,y) (ANY x) (ANY y) On(x,y) OR Above(x,y) On(x,y) OR Above(x,y)最后子句為On(x,y) OR Above(x,y)(3) (ANY x) (ANY y) (ANY z) Above(x,y) AND Above(y,z) Above(x,z) (命題聯(lián)結(jié)詞之優(yōu)先級(jí)如下:否定合取析取蘊(yùn)涵等價(jià))(ANY x) (ANY y) (ANY z) Above(x,y) AND Above(y,z) OR Above (x,z) Above(x,y) AND Above(y,z) OR Above (x,z)最后子句為Above(x,y), Above(y,z) OR Above(x,z)(4) (ANY x) P(x) (ANY y) p(y)p(f(x,y) AND (ANY y) Q(x,y) P(y) (ANY x) P(x) OR (ANY y) p(y) OR p(f(x,y) AND (ANY y) Q(x,y) OR P(y) (EXT x) P(x) AND (EXT x) p(y) AND p(f(x,y) OR (EXT y) Q(x,y) AND P(y) (EXT x) P(x) AND (EXT w) p(y) AND p(f(w,y) OR (EXT v) Q(x,v) AND P(v) P(A) AND p(y) AND p(f(B,y) OR Q(A,C) AND P(C) P(A) AND p(y) AND p(f(B,y) OR Q(A,C) AND p(y) AND p(f(B,y) OR P(C) P(A) AND p(y), p(f(B,y) OR Q(A,C) AND p(y), p(f(B,y) OR P(C) 最后子句為P(A) p(x), p(f(B,x) OR Q(A,C) p(y), p(f(B,y) OR P(C)2-7 用謂詞演算公式表示下列英文句子(多用而不是省用不同謂詞和項(xiàng)。例如不要用單一的謂詞字母來(lái)表示每個(gè)句子。)A computer system is intelligent if it can perform a task which, if performed by a human, requires intelligence.先定義基本的謂詞INTLT(x) means x is intelligentPERFORM(x,y) means x can perform yREQUIRE(x) means x requires intelligenceCMP(x) means x is a computer systemHMN(x) means x is a human上面的句子可以表達(dá)為(任意x) (存在t) (存在y) HMN(y) 合取 PERFORM(y,t) 合取 REQUIRE(t) 合取 CMP(x) 合取 PERFORM(x,t) INTLT(x) 2-8 把下列語(yǔ)句表示成語(yǔ)義網(wǎng)絡(luò)描述：(1) All man are mortal.(2) Every cloud has a silver lining.(3) All branch managers of DEC participate in a profit-sharing plan.(1) ManMortalATTR(2)CloudLiningSilverHASCOLOUR(3) ManagerBranchDECPlanProfit-sharingLEVELCOMPANYATTENDATTR2-9 作為一個(gè)電影觀眾，請(qǐng)你編寫(xiě)一個(gè)去電影院看電影的劇本。(1) 開(kāi)場(chǎng)條件(a) 顧客想看電影(b) 顧客在足夠的錢(qián)(2) 角色顧客，售票員，檢票員，放映員 (3) 道具錢(qián)，電影票(4) 場(chǎng)景場(chǎng)景 1 購(gòu)票(a) 顧客來(lái)到售票處(b) 售票員把票給顧客(c) 顧客把錢(qián)給售票員(d) 顧客走向電影院門(mén)場(chǎng)景 2 檢票(a) 顧客把電影票給檢票員(b) 檢票員檢票(c) 檢票員把電影票還給顧客(d) 顧客進(jìn)入電影院場(chǎng)景 3 等待(a) 顧客找到自己的座位(b) 顧客坐在自己座位一等待電影開(kāi)始場(chǎng)景 4 觀看電影(a) 放映員播放電影(b) 顧客觀看