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

第二章知識表示方法2-1狀態(tài)空間法、問題歸約法、謂詞邏輯法和語義網(wǎng)絡(luò)法的要點是什么？它們有何本質(zhì)上的聯(lián)系及異同點?答：狀態(tài)空間法：基于解答空間的問題表示和求解方法，它是以狀態(tài)和算符為基礎(chǔ)來表示和求解問題的。一般用狀態(tài)空間法來表示下述方法：從某個初始狀態(tài)開始，每次加一個操作符，遞增的建立起操作符的試驗序列，直到達到目標(biāo)狀態(tài)為止。問題規(guī)約法：已知問題的描述，通過一系列變換把此問題最終變成一個子問題集合：這些子問題的解可以直接得到，從而解決了初始問題。問題規(guī)約的實質(zhì)：從目標(biāo)(要解決的問題)出發(fā)逆向推理，建立子問題以及子問題的子問題，直至最后把出示問題規(guī)約為一個平凡的本原問題集合。謂詞邏輯法：采用謂詞合式公式和一階謂詞算法。要解決的問題變?yōu)橐粋€有待證明的問題，然后采用消解定理和消解反演萊證明一個新語句是從已知的正確語句導(dǎo)出的，從而證明這個新語句也是正確的。語義網(wǎng)絡(luò)法：是一種結(jié)構(gòu)化表示方法，它由節(jié)點和弧線或鏈組成。節(jié)點用于表示物體、概念和狀態(tài)，弧線用于表示節(jié)點間的關(guān)系。語義網(wǎng)絡(luò)的解答是一個經(jīng)過推理和匹配而得到的具有明確結(jié)果的新的語義網(wǎng)絡(luò)。語義網(wǎng)絡(luò)可用于表示多元關(guān)系，擴展后可以表示更復(fù)雜的問題2-2設(shè)有3個傳教士和3個野人來到河邊，打算乘一只船從右岸渡到左岸去。該船的負載能力為兩人。在任何時候，如果野人人數(shù)超過傳教士人數(shù)，那么野人就會把傳教士吃掉。他們怎樣才能用這條船安全地把所有人都渡過河去?用Si(nC,nY)表示第i次渡河后，河對岸的狀態(tài)，nC表示傳教士的數(shù)目，nY表示野人的數(shù)目，由于總?cè)藬?shù)的確定的，河對岸的狀態(tài)確定了，河這邊的狀態(tài)也即確定了?？紤]到題目的限制條件，要同時保證，河兩岸的傳教士數(shù)目不少于野人數(shù)目，故在整個渡河的過程中，允許出現(xiàn)的狀態(tài)為以下3種情況：nC=0nC=3nC=nY>=0(當(dāng)nC不等于0或3)用di(dC,dY)表示渡河過程中，對岸狀態(tài)的變化，dC表示，第i次渡河后，對岸傳教士數(shù)目的變化，dY表示，第i次渡河后，對岸野人數(shù)目的變化。當(dāng)i為偶數(shù)時，dC,dY同時為非負數(shù)，表示船駛向?qū)Π叮琲為奇數(shù)時，dC,dY同時為非正數(shù)，表示船駛回岸邊。初始狀態(tài)為So(O,0),目標(biāo)狀態(tài)為so(3,3),用深度優(yōu)先搜索的方法可尋找渡河方案。在此，用圖求法該問題，令橫坐標(biāo)為nY,縱坐標(biāo)為nC,可行狀態(tài)為空心點表示，每次可以在格子上,沿對角線移動一格,也可以沿坐標(biāo)軸方向移動1格,或沿坐標(biāo)軸方向移動2格。第奇數(shù)次數(shù)狀態(tài)轉(zhuǎn)移，沿右方，上方，或右上方移動，第偶數(shù)次數(shù)狀態(tài)轉(zhuǎn)移，沿左方，下方，或左下方移動。從(0,0)開始，依次沿箭頭方向改變狀態(tài)，經(jīng)過11步之后，即可以到達目標(biāo)狀態(tài)(3,3)，相應(yīng)的渡河方案為：dl(l,l)--^d2(-l,0)--^d3(0,2)--^d4(0,-l)--^d5(2,0)--^d6(-l,-l)--^d7(2,0)--^d8(0,-l)--^d9(0,2)--^dl0(-l,0)--^dll(l,l)2-3利用圖2.3,用狀態(tài)空間法規(guī)劃一個最短的旅行路程：此旅程從城市A開始，訪問其他城市不多于一次，并返回A。選擇一個狀態(tài)表示，表示出所求得的狀態(tài)空間的節(jié)點及弧線，標(biāo)出適當(dāng)?shù)拇鷥r，并指明圖中從起始節(jié)點到目標(biāo)節(jié)點的最佳路徑。

2-4試說明怎樣把一棵與或解樹用來表達圖2.28所示的電網(wǎng)絡(luò)阻抗的計算。單獨的R、L或C可分別用R、j3L或1/joC來計算，這個事實用作本原問題。后繼算符應(yīng)以復(fù)合并聯(lián)和串聯(lián)阻抗的規(guī)則為基礎(chǔ)。圖2.28約定，用原來的與后繼算法用來表達并聯(lián)關(guān)系，用原來的或后繼算法用來表達串聯(lián)關(guān)系

2-5試用四元數(shù)列結(jié)構(gòu)表示四圓盤梵塔問題，并畫出求解該問題的與或圖。用四元數(shù)列(nA,nB,nC,nD)來表示狀態(tài)，其中nA表示A盤落在第nA號柱子上，nB表示B盤落在第nB號柱子上，nC表示C盤落在第nC號柱子上，nD表示D盤落在第nD號柱子上。初始狀態(tài)為1111，目標(biāo)狀態(tài)為3333

如圖所示，按從上往下的順序，依次處理每一個葉結(jié)點，搬動圓盤，問題得解。2-6把下列句子變換成子句形式：⑴(Vx){P(x)fP(x)}⑵VxVy(On(x,y)fAbove(x,y))⑶VxVyVz(Above(x,y)AAbove(y,z)fAbove(x,z))(4)?{(Vx){P(x)f{(Vy)[p(y)fp(f(x,y))]A(Vy)[Q(x,y)?P(y)]}}}(ANYx){P(x)TP(x)}(ANYx){~P(x)ORP(x)}~P(x)ORP(x)最后子句為~P(x)ORP(x)(ANYx)(ANYy){On(x,yQAbove(x,y)}(ANYx)(ANYy){~On(x,y)ORAbove(x,y)}~On(x,y)ORAbove(x,y)最后子句為~On(x,y)ORAbove(x,y)(ANYx)(ANYy)(ANYz){Above(x,y)ANDAbove(y,zQAbove(x,z)}(命題聯(lián)結(jié)詞之優(yōu)先級如下:否定f合取f析取f蘊涵f等價)(ANYx)(ANYy)(ANYz){~[Above(x,y)ANDAbove(y,z)]ORAbove(x,z)}~[Above(x,y)ANDAbove(y,z)]ORAbove(x,z)最后子句為~[Above(x,y),Above(y,z)]ORAbove(x,z)~{(ANYx){P(x)T{(ANYy)[p(y)Tp(f(x,y))]AND(ANYy)[Q(x,y)TP(y)]}}}~{(ANYx){~P(x)OR{(ANYy)[~p(y)ORp(f(x,y))]AND(ANYy)[~Q(x,y)ORP(y)]}}}(EXTx){P(x)AND{(EXTx)[p(y)AND~p(f(x,y))]OR(EXTy)[Q(x,y)AND~P(y)]}}(EXTx){P(x)AND{(EXTw)[p(y)AND~p(f(w,y))]OR(EXTv)[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))ORQ(A,C)]AND[p(y)AND~p(f(B,y))OR~P(C)]}P(A)AND{{p(y),~p(f(B,y))}ORQ(A,C)}AND{{p(y),~p(f(B,y))}OR~P(C)}最后子句為P(A){p(x),~p(f(B,x))}ORQ(A,C){p(y),~p(f(B,y))}OR~P(C)2-7用謂詞演算公式表示下列英文句子(多用而不是省用不同謂詞和項。例如不要用單一的謂詞字母來表示每個句子。)Acomputersystemisintelligentifitcanperformataskwhich,ifperformedbyahuman,requiresintelligence.先定義基本的謂詞INTLT(x)meansxisintelligentPERFORM(x,y)meansxcanperformyREQUIRE(x)meansxrequiresintelligenceCMP(x)meansxisacomputersystemHMN(x)meansxisahuman上面的句子可以表達為(任意x){(存在t)(存在y)[HMN(y)合取PERFORM(y,t)合取REQUIRE(t)合取CMP(x)合取PERFORM(x,t)]INTLT(x)}2-8把下列語句表示成語義網(wǎng)絡(luò)描述：Allmanaremortal.Everycloudhasasilverlining.AllbranchmanagersofDECparticipateinaprofit-sharingplan.(1)(3)2-9作為一個電影觀眾，請你編寫一個去電影院看電影的劇本。(1)開場條件(a)顧客想看電影(b)顧客在足夠的錢(2)角色顧客，售票員，檢票員，放映員(3)道具錢，電影票(4)場景場景1購票(a)顧客來到售票處售票員把票給顧客顧客把錢給售票員顧客走向電影院門場景2檢票(a)顧客把電影票給檢票員(