人工智能期末復(fù)習(xí)題解讀

人工智能期末復(fù)習(xí)題解讀人工智能期末復(fù)習(xí)題解讀人工智能期末復(fù)習(xí)題解讀xxx公司人工智能期末復(fù)習(xí)題解讀文件編號(hào)：文件日期：修訂次數(shù)：第1.0次更改批準(zhǔn)審核制定方案設(shè)計(jì)，管理制度簡(jiǎn)述產(chǎn)生式系統(tǒng)分為幾個(gè)部分及其主要功能(10)答案：產(chǎn)生式系統(tǒng)分為三部分，分別為綜合數(shù)據(jù)庫(kù)、規(guī)則集和控制策略。綜合數(shù)據(jù)庫(kù)中保存了推理的初始狀態(tài)、中間結(jié)果和目標(biāo)狀態(tài)。規(guī)則集中的規(guī)則是描述能夠使?fàn)顟B(tài)發(fā)生改變的操作或者方法，它的形式是IF<前件>THEN<后件>?？刂撇呗悦枋隽水?dāng)對(duì)某一狀態(tài)而言有很多規(guī)則可用時(shí)，系統(tǒng)應(yīng)該先采用哪一條規(guī)則。簡(jiǎn)述回溯策略與深度優(yōu)先策略的不同點(diǎn)。(10) 答案： 回溯搜索策略與深度有限搜索策略最大的不同是深度有限搜索策略屬于圖搜索，而回溯搜索則不是圖搜索。在回溯搜索中，只保留了從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的搜索路徑。而深度優(yōu)先搜索，則保留了所有的已經(jīng)搜索過的路徑。(10)(10)(20)對(duì)N＝5、k≤3時(shí)，求解傳教士和野人問題的產(chǎn)生式系統(tǒng)各組成部分進(jìn)行描述（給出綜合數(shù)據(jù)庫(kù)、規(guī)則集合的形式化描述，給出初始狀態(tài)和目標(biāo)條件的描述）(20)答案：1，綜合數(shù)據(jù)庫(kù)

定義三元組：（m,c,b）

其中：，表示傳教士在河左岸的人數(shù)。

，表示野人在河左岸的人數(shù)。

，b=1，表示船在左岸，b=0，表示船在右岸。

2，規(guī)則集

按每次渡河的人數(shù)分別寫出每一個(gè)規(guī)則，共(30)、(03)、(21)、(11)、(10)、(01)、(20)、(02)八種渡河的可能（其中(xy)表示x個(gè)傳教士和y個(gè)野人上船渡河），因此共有16個(gè)規(guī)則（從左岸到右岸、右岸到左岸各八個(gè)）。注意：這里沒有(12)，因?yàn)樵摻M合在船上的傳教士人數(shù)少于野人人數(shù)。

規(guī)則集如下：r1：IF(m,c,1)THEN(m-3,c,0)

r2：IF(m,c,1)THEN(m,c-3,0)

r3：IF(m,c,1)THEN(m-2,c-1,0)

r4：IF(m,c,1)THEN(m-1,c-1,0)

r5：IF(m,c,1)THEN(m-1,c,0)

r6：IF(m,c,1)THEN(m,c-1,0)

r7：IF(m,c,1)THEN(m-2,c,0)

r8：IF(m,c,1)THEN(m,c-2,0)r9：IF(m,c,0)THEN(m+3,c,1)

r10：IF(m,c,0)THEN(m,c+3,1)

r11：IF(m,c,0)THEN(m+2,c+1,1)

r12：IF(m,c,0)THEN(m+1,c+1,1)

r13：IF(m,c,0)THEN(m+1,c,1)

r14：IF(m,c,0)THEN(m,c+1,1)

r15：IF(m,c,0)THEN(m+2,c,1)

r16：IF(m,c,0)THEN(m,c+2,1)3，初始狀態(tài)：(5,5,1)

4，結(jié)束狀態(tài)：(0,0,0)對(duì)三枚錢幣問題給出產(chǎn)生式系統(tǒng)描述。（20）

設(shè)有三枚錢幣，其排列處在"正、正、反"狀態(tài)，現(xiàn)允許每次可翻動(dòng)其中任意一個(gè)錢幣，問只許操作三次的情況下，如何翻動(dòng)錢幣使其變成"正、正、正"或"反、反、反"狀態(tài)。答：1）綜合數(shù)據(jù)庫(kù)

定義四元組：（x,y,z,n）

其中x,y,x∈[0,1]，1表示錢幣為正面，0表示錢幣為反面。n=0,1,2,3，表示當(dāng)前狀態(tài)是經(jīng)過n次翻錢幣得到的。

2）規(guī)則庫(kù)

r1:IF(x,y,z,n)THEN(~x,y,z,n+1)

r2:IF(x,y,z,n)THEN(x,~y,z,n+1)

r3:IF(x,y,z,n)THEN(x,y,~z,n+1)

其中~x表示對(duì)x取反。

3）初始狀態(tài)(1,1,0,0)

4）結(jié)束狀態(tài)(1,1,1,3)或者(0,0,0,3)有四人過河，只有一條船，最多可乘坐兩人。若單個(gè)過，各需1，1，5，9分鐘，若兩人一起過，則需要的時(shí)間以多的為準(zhǔn)（如需要5分和9分的兩人同時(shí)乘坐，則需要9分）。問最少需要多少分鐘。要求用產(chǎn)生式系統(tǒng)描述該問題，要求給出綜合數(shù)據(jù)庫(kù)的定義，規(guī)則集，初始狀態(tài)和結(jié)束狀態(tài)。(20)1）綜合數(shù)據(jù)庫(kù)：(m1,m5,m9,b)設(shè)從河的左岸到右岸，其中m1,m5,m9分別表示過河時(shí)間需要1分鐘，5分鐘和9分鐘的人，在河左岸的人數(shù)。b＝1表示船在左岸，b＝0表示船在右岸。2）規(guī)則集：初始狀態(tài)：(2,1,1,1)

結(jié)束狀態(tài)(0,0,0,0)寬度優(yōu)先搜索(10)詳見課件相關(guān)內(nèi)容限深度為5寫出下面的八數(shù)碼游戲用A算法進(jìn)行搜索的示意圖(20)初始狀態(tài)目標(biāo)狀態(tài)142083765123804765注：（1）首先需要簡(jiǎn)要的描述八數(shù)碼游戲的產(chǎn)生式系統(tǒng)三要素（2）最終要寫出所采用的規(guī)則序列答案： 首先描述產(chǎn)生式系統(tǒng)三要素。綜合數(shù)據(jù)庫(kù)用二維數(shù)組表示，規(guī)則集為上下左右4條規(guī)則?？刂撇呗裕篺(n)=g(n)+h(n)。選取f（n）最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展，擴(kuò)展時(shí)采用左上右下順序。搜索路徑如下：

采用的規(guī)則序列為右上右下左寫出下面的八數(shù)碼游戲用A算法進(jìn)行搜索的示意圖(20)初始狀態(tài)目標(biāo)狀態(tài)142083765142730685注：（1）首先需要簡(jiǎn)要的描述八數(shù)碼游戲的產(chǎn)生式系統(tǒng)三要素（2）最終要寫出所采用的規(guī)則序列首先描述產(chǎn)生式系統(tǒng)三要素。綜合數(shù)據(jù)庫(kù)用二維數(shù)組表示，規(guī)則集為上下左右4條規(guī)則?？刂撇呗裕篺(n)=g(n)+h(n)。選取f（n）最小得節(jié)點(diǎn)進(jìn)行擴(kuò)展，擴(kuò)展時(shí)采用左上右下順序。g（n）為不在位的將牌數(shù)搜索路徑如下：規(guī)則序列如下：（4分）下右上右把下面的謂詞公式化成子句集：(10)(x)((y)P(x,y)~(y)(Q(x,y)R(x,y)))(x)((y)P(x,y)~(y)(Q(x,y)R(x,y)))=>(x)((y)P(x,y)~(y)(~Q(x,y)∨R(x,y)))(a)=>(x)((y)P(x,y)(y)(Q(x,y)∧~R(x,y)))(b)=>(x)((y)~P(x,y)∨((y)(Q(x,y)∧~R(x,y)))(c)=>(x)(y)(~P(x,y)∨(Q(x,y)∧~R(x,y)))(d)=>(x)(y)((~P(x,y)∨Q(x,y))∧(~P(x,y)∨~R(x,y)))(e)=>(x)((~P(x,f(x))∨Q(x,f(x)))∧(~P(x,f(x))∨~R(x,f(x))))(f)故子句集為{~P(x,f(x))∨Q(x,f(x)),~P(x,f(x))∨~R(x,f(x))}(g) 換名后的字句集：{~P(x1,f(x1))∨Q(x1,f(x1)),~P(x2,f(x2))∨~R(x2,f(x2))}化子句集的方法(10)例：(z)(x)(y){[(P(x)Q(x))R(y)]U(z)} =>(z)(x)(y){[~(P(x)Q(x))R(y)]U(z)} =>(z)(x)(y){[(~P(x)~Q(x))R(y)]U(z)} =>(x){[(~P(x)~Q(x))R(f(x))]U(a)}=>(x){(~P(x)~Q(x))R(f(x))U(a)}=>(x){[~P(x)R(f(x))U(a)][~Q(x))R(f(x))U(a)]}{[~P(x)R(f(x))U(a)][~Q(x))R(f(x))U(a)]}{~P(x)R(f(x))U(a),~Q(x))R(f(x))U(a)}{~P(x1)R(f(x1))U(a),~Q(x2))R(f(x2))U(a)}(10)命題邏輯歸結(jié)詳見課件（10）證明公式：(P→Q)→(～Q→～P)(10)證明：（1）根據(jù)歸結(jié)原理，將待證明公式轉(zhuǎn)化成待歸結(jié)命題公式： (P→Q)∧～(～Q→～P)（2）分別將公式前項(xiàng)化為合取范式： P→Q＝～P∨Q 結(jié)論求～后的后項(xiàng)化為合取范式： ～(～Q→～P)＝～(Q∨～P)＝～Q∧P 兩項(xiàng)合并后化為合取范式： （～P∨Q）∧～Q∧P（3）則子句集為： {～P∨Q，～Q，P}子句集為： {～P∨Q，～Q，P}（4）對(duì)子句集中的子句進(jìn)行歸結(jié)可得：1.

～P∨Q2.

～Q3.

P4.

Q， （1，3歸結(jié)）5.

， （2，4歸結(jié)） 由上可得原公式成立。{P(x,x,z),P(f(y),f(B),y)}求mgu(10)前綴表示： (Pxxz) (P(fy)(fB)y) 置換：{(fy)/x} (P(fy)(fy)z) (P(fy)(fB)y) 置換：{B/y},并使得{(fB)/x} (P(fB)(fB)z) (P(fB)(fB)B) 置換：{B/z} 得到置換：{(fB)/x，B/y，B/z} 置換后的結(jié)果：(P(fB)(fB)B)求W={P(a,x,f(g(y))),P(z,f(z),f(u))}的mgu(10)找出集{P（x，z，y），P（w，u，w），P（A，u，u）}的mgu。（10）思路：先求P（x，z，y）與P（w，u，w）的mgu，然后再求中間結(jié)果和P（A，u，u）的mgu，此即所求先將3個(gè)謂詞表示為如下形式：（Pxzy）(1)（Pwuw）(2)（PAuu）(3)S1={w/x,u/z,w/y}。用S1將（1）（2）變換為P（w，u，w）。下面求（2）（3）的mgu。令S2＝{A/w,A/u}則三者的mgu為S1﹒S2={A/x,A/y,A/z,A/w,A/u}設(shè)公理集： P, (PQ)R, (ST)Q, T求證：R要求畫出歸結(jié)樹(20)化子句集： (PQ)R=>~(PQ)R=>~P~QR (ST)Q=>~(ST)Q=>(~S~T)Q=>(~SQ)(~TQ){~SQ,~TQ}子句集： (1)P (2)~P~QR (3)~SQ (4)~TQ (5)T (6)~R（目標(biāo)求反）子句集： (1)P (2)~P~QR (3)~SQ (4)~TQ (5)T (6)~R（目標(biāo)求反）歸結(jié)：此處直接繪制歸結(jié)樹即可設(shè)公理集： (x)(R(x)L(x)) (x)(D(x)~L(x)) (x)(D(x)I(x))求證：(x)(I(x)~R(x))(20)化子句集： (x)(R(x)L(x))=>(x)(~R(x)L(x))=>~R(x)L(x)(1)(x)(D(x)~L(x))=>(x)(~D(x)~L(x))=>~D(x)~L(x)(2) (x)(D(x)I(x))=>D(A)I(A)=>D(A)(3) I(A)(4