.第二章 知識表示方法2-1 狀態空間法、問題歸約法、謂詞邏輯法和語義網絡法的要點是什么？它們有何本質上的聯系及異同點?答：狀態空間法：基于解答空間的問題表示和求解方法，它是以狀態和算符為基礎來表示和求解問題的。一般用狀態空間法來表示下述方法：從某個初始狀態開始，每次加一個操作符，遞增的建立起操作符的試驗序列，直到達到目標狀態為止。問題規約法：已知問題的描述，通過一系列變換把此問題最終變成一個子問題集合：這些子問題的解可以直接得到，從而解決了初始問題。問題規約的實質：從目標（要解決的問題）出發逆向推理，建立子問題以及子問題的子問題，直至最后把出示問題規約為一個平凡的本原問題集合。謂詞邏輯法：采用謂詞合式公式和一階謂詞算法。要解決的問題變為一個有待證明的問題，然后采用消解定理和消解反演萊證明一個新語句是從已知的正確語句導出的，從而證明這個新語句也是正確的。語義網絡法：是一種結構化表示方法，它由節點和弧線或鏈組成。節點用于表示物體、概念和狀態，弧線用于表示節點間的關系。語義網絡的解答是一個經過推理和匹配而得到的具有明確結果的新的語義網絡。語義網絡可用于表示多元關系，擴展后可以表示更復雜的問題2-2 設有3個傳教士和3個野人來到河邊，打算乘一只船從右岸渡到左岸去。該船的負載能力為兩人。在任何時候，如果野人人數超過傳教士人數，那么野人就會把傳教士吃掉。他們怎樣才能用這條船安全地把所有人都渡過河去?用Si(nC, nY) 表示第i次渡河后，河對岸的狀態，nC表示傳教士的數目，nY表示野人的數目，由于總人數的確定的，河對岸的狀態確定了，河這邊的狀態也即確定了。考慮到題目的限制條件，要同時保證，河兩岸的傳教士數目不少于野人數目，故在整個渡河的過程中，允許出現的狀態為以下3種情況：1. nC=02. nC=33. nC=nY=0 (當nC不等于0或3)用di(dC, dY)表示渡河過程中，對岸狀態的變化，dC表示，第i次渡河后，對岸傳教士數目的變化，dY表示，第i次渡河后，對岸野人數目的變化。當i為偶數時，dC,dY同時為非負數，表示船駛向對岸，i為奇數時，dC, dY同時為非正數，表示船駛回岸邊。初始狀態為S0(0, 0)，目標狀態為S0(3, 3)，用深度優先搜索的方法可尋找渡河方案。在此，用圖求法該問題，令橫坐標為nY, 縱坐標為nC，可行狀態為空心點表示，每次可以在格子上，沿對角線移動一格，也可以沿坐標軸方向移動1格，或沿坐標軸方向移動2格。第奇數次數狀態轉移，沿右方，上方，或右上方移動，第偶數次數狀態轉移，沿左方，下方，或左下方移動。1nCnY231320從(0,0)開始，依次沿箭頭方向改變狀態，經過11步之后，即可以到達目標狀態(3,3)，相應的渡河方案為：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，用狀態空間法規劃一個最短的旅行路程：此旅程從城市A開始，訪問其他城市不多于一次，并返回A。選擇一個狀態表示，表示出所求得的狀態空間的節點及弧線，標出適當的代價，并指明圖中從起始節點到目標節點的最佳路徑。71071013966510BEDAC圖 2.32-4 試說明怎樣把一棵與或解樹用來表達圖2.28所示的電網絡阻抗的計算。單獨的R、L或C可分別用R、jL或1/jC來計算，這個事實用作本原問題。后繼算符應以復合并聯和串聯阻抗的規則為基礎。圖 2.28約定，用原來的與后繼算法用來表達并聯關系，用原來的或后繼算法用來表達串聯關系ZR1Z2Z3Z21Z22Z31Z32R2C1Z211R3C2L2R4L3C4L4C3L12-5 試用四元數列結構表示四圓盤梵塔問題，并畫出求解該問題的與或圖。用四元數列 (nA, nB, nC, nD) 來表示狀態，其中nA表示A盤落在第nA號柱子上，nB表示B盤落在第nB號柱子上，nC表示C盤落在第nC號柱子上，nD表示D盤落在第nD號柱子上。初始狀態為 1111，目標狀態為 333311113333111122212221222322233333111133113311332133212221222311231123113311333333111121112111231123113311332113211321122112212221222332233223312331231123113321332133233323333333如圖所示，按從上往下的順序，依次處理每一個葉結點，搬動圓盤，問題得解。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) (命題聯結詞之優先級如下:否定合取析取蘊涵等價)(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 用謂詞演算公式表示下列英文句子(多用而不是省用不同謂詞和項。例如不要用單一的謂詞字母來表示每個句子。)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上面的句子可以表達為(任意x) (存在t) (存在y) HMN(y) 合取 PERFORM(y,t) 合取 REQUIRE(t) 合取 CMP(x) 合取 PERFORM(x,t) INTLT(x) 2-8 把下列語句表示成語義網絡描述：(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 作為一個電影觀眾，請你編寫一個去電影院看電影的劇本。(1) 開場條件(a) 顧客想看電影(b) 顧客在足夠的錢(2) 角色顧客，售票員，檢票員，放映員 (3) 道具錢，電影票(4) 場景場景 1 購票(a) 顧客來到售票處(b) 售票員把票給顧客(c) 顧客把錢給售票員(d) 顧客走向電影院門場景 2 檢票(a) 顧客把電影票給檢票員(b) 檢票員檢票(c) 檢票員把電影票還給顧客(d) 顧客進入電影院場景 3 等待(a) 顧客找到自己的座位(b) 顧客坐在自己座位一等待電影開始場景 4 觀看電影(a) 放映員播放電影(b) 顧客觀看