人工智能原理習題分析2023/8/17人工智能原理習題分析2023/8/52.1謂詞邏輯表示知識用謂詞邏輯表示下列知識：武漢是一個美麗的城市，但她不是一個沿海城市。如果馬亮是男孩，張紅是女孩，則馬亮比張紅長得高。例第一步第二步第三步定義謂詞如下：BCity(x)：x是一個美麗的城市HCity(x)：x是一個沿海城市Boy(x):x是男孩Girl(x):x是女孩High(x,y):x比y長得高根據(jù)語義，用邏輯連接符連接BCity(wuhan)∧~HCity(wuhan)(Boy(mal)∧Girl(zhangh))→High(mal,zhangh)將個體代入謂詞中，得到

BCity(wuhan),HCity(wuhan),Boy(mal),Girl(zhangh),High(mal,zhangh)2023/8/172.1謂詞邏輯表示知識用謂詞邏輯表示下列知識：例第一步第二人人愛勞動。所有整數(shù)不是偶數(shù)就是奇數(shù)。自然數(shù)都是大于零的整數(shù)例第一步第二步第三步MAN(x)：x是人

LOVE(x,y):x愛yN(x)：x是自然數(shù)；I(x)：x是整數(shù)；E(x)：X是偶數(shù)O(x):x是奇數(shù)GZ(x):x大于02.1謂詞邏輯表示知識2023/8/17人人愛勞動。例第一步第二步第三步MAN(x)：x是人L第三步2.1謂詞邏輯表示知識在一個房間里，有一個機器人Robot，一個壁櫥Alcove，一個積木塊Box，兩個桌子A和B。開始時，Bobot在Alcove旁邊且兩手是空的，A上放著Box，B上是空的。Robot將把Box從A移到B上例3第一步第二步TABLE(x)：x是桌子EMPTYHANDED(x)：x雙手是空的AT(x,y):x在y旁邊HOLDS(y,w)：y拿著wON(w,x):w在x上EMPTYTABLE(x)：桌子x上是空的個體詞：ROBOT,BOX,ALCOVE,A,B

2023/8/17第三步2.1謂詞邏輯表示知識在一個房間里，有一個機器人Ro設有如下語句，請用謂詞公式把他們表示出來(1)有的人喜歡梅花，有的人喜歡菊花，有的人既喜歡梅花又喜歡菊花。(2)要想出國留學，必須通過外語考試(2)所有人都有飯吃1.定義謂詞及個體，確定每個謂詞及個體的確切含義。2.根據(jù)所要表達的事物或概念，為每個謂詞中的變元賦以特定的值。3.根據(jù)所要表達的知識的語義，用適當?shù)倪B接符將各個謂詞連接起來,形成謂詞公式。2.1謂詞邏輯表示知識2023/8/17設有如下語句，請用謂詞公式把他們表示出來1.定義謂詞及個體，有的人喜歡梅花，有的人喜歡菊花，有的人既喜歡梅花又喜歡菊花第一步第二步第三步定義謂詞：LIKE(x,y)：x喜歡y定義個體詞：Meihua，JuhuaLIKE(x,Meihua),LIKE(y,Juhua)LIKE(z,Meihua)∧LIKE(z,Juhua)

2023/8/17有的人喜歡梅花，有的人喜歡菊花，有的人既喜歡梅花又喜歡菊花第要想出國留學，必須通過外語考試第一步第二步第三步定義謂詞：Want(x,y)：x想y，Pass(x,y)：x通過y

定義個體詞：goabroad,flanguagePass(x,flanguage),Want(x,goabroad)2023/8/17要想出國留學，必須通過外語考試第一步第二步第三步定義謂詞：W所有人都有飯吃第一步第二步第三步定義謂詞：Havefood(x)：x有飯吃2023/8/17所有人都有飯吃第一步第二步第三步定義謂詞：Havefood(自測題目1.李明每天下午踢足球2.合肥的夏天潮濕炎熱3.喜歡打籃球的人必喜歡踢足球2023/8/17自測題目1.李明每天下午踢足球2023/8/5動物isa生物植物isaisaisa魚鳥飛翅膀水游泳cancaninhave烏鴉isa黑色腐肉eatingcovering吃運動cancan2.2語義網(wǎng)絡知識表示2023/8/17動物isa生物植物isaisaisa魚鳥飛翅膀水游泳canc2.2語義網(wǎng)絡知識表示語義網(wǎng)絡AKOAKOISHAVELocate-at山羊動物羊豬綿羊野豬哺乳動物頭上有角羊毛森林AKOAKOAKOAKO豬和羊的語義網(wǎng)絡2023/8/172.2語義網(wǎng)絡知識表示語義網(wǎng)絡AKOAKOISHAVELo框架名：<計算機主機>

主機品牌：聯(lián)想1+1

生產(chǎn)廠商：北京聯(lián)想集團公司CPU：品牌：Intel型號：奔騰Ⅲ/933主板：品牌：QDI型號：ATXVA5

內存：品牌：現(xiàn)代型號：SDRAM容量：128MB硬盤：品牌：Seagate型號：ST320423A容量：20GB例2.3框架知識表示2023/8/17框架名：<計算機主機>例2.3框架知識表示2023/8/5例：[新華社9月16日電]國家氣象臺命名的“99年2號”臺風于昨日下午4時在浙江舟山地區(qū)登陸，據(jù)專家經(jīng)驗，認為風力大于等于8級，但風力的準確值，有待數(shù)據(jù)處理，目前尚未公布。此次臺風造成的損失，尚未得到報告，若需要詳細的損失數(shù)字，可電詢自然災害統(tǒng)計中心。另據(jù)介紹，事前曾得到國際氣象組織預報：昨日上午于太平洋赤道地區(qū)生成的高壓氣旋，將向北移動，于浙江舟山地區(qū)登陸。依國際慣例，將其命名為Carla颶風。我國也予以承認，至于Carla是否就是“99年2號”尚須另加核實。2.3框架知識表示2023/8/17例：[新華社9月16日電]國家氣象臺命名的“99年2號Frame：臺風slot1：登陸時間

Value：9月15日下午四時

……slot2：登陸地點

Value：浙江舟山地區(qū)……slot3：風力

default：大于等于8級

……slot4：損失

If-needed：電詢自然災害統(tǒng)計中心……slot5：名稱

Value：99年2號Default：Carla颶風If-added：核查Carla與“61年2號的關系并加注釋……2.3框架知識表示2023/8/17Frame：臺風slot1：登陸時間slot2：登陸地點3.1

子句集消去存在量詞1234謂詞公式化為子句集步驟重新命名變元利用等價關系消去謂詞公式中的“”和“”利用等價關系把“”移到緊靠謂詞存在量詞不出現(xiàn)在全稱量詞的轄域內，則用新的個體常量替換存在量詞；存在量詞位于一個或多個全稱量詞的轄域內，則用全稱量詞的函數(shù)取代存在量詞2023/8/173.1子句集消去存在量詞1234謂詞公式化為重新命名變元3.1子句集把全稱量詞移到公式左邊8765謂詞公式化為子句集步驟消去全稱量詞利用等價關系把母式化為合取范式9使不同子句中的變元不同名消去合取詞，生成子句集2023/8/173.1子句集把全稱量詞移到公式左邊8765謂詞公3.1子句集2023/8/173.1子句集2023/8/5例如：E1=P(a,x,f(g(y)))E2=P(z,f(a),f(u))求mgu。解：(1)W={E1,E2}={P(a,x,f(g(y))),P(z,f(a),f(u))}(2)W0=W,g=[](3)W0未合一，從左到右找不一致集，有D0={a,z}(4)取v0=z,t0=a(5)令g1=g0{t0/v0,}={a/z}W1=W0g1={P(a,x,f(g(y))),P(a,f(a),f(u))}3.2最小合一置換2023/8/17例如：E1=P(a,x,f(g(y)))E2=P(z,f((3)’

W1未合一，從左到右找不一致集，有D1={x,f(a)}(4)’

取v1=x,t1=f(a)(5)’

令g2=g1{t1/v1,}={a/z,f(a)/x}W2=W1g2={P(a,f(a),f(g(y))),P(a,f(a),f(u))}(3)’’W2未合一，從左到右找不一致集，有D2={g(y),u)}(4)’’

取v2=u,t2=g(y)(5)’’

令g3=g2{t2/v2,}={a/z,f(a)/x,g(y)/u}W3=W2g3={P(a,f(a),f(g(y))),P(a,f(a),f(g(y)))}(3)’’’W3已合一，這時g3={a/z,f(a)/x,g(y)/u}3.2最小合一置換2023/8/17(3)’W1未合一，從左到右找不一致集，有D1={x,f(已知能閱讀的都是有文化的；海豚是沒有文化的；某些海豚是有智能的；證明：某些有智能的并不能閱讀。證明：符號化R(x):x能閱讀L(x):x有文化D(x)：x是海豚I(x)：x有智能3.3使用歸結原理證明問題2023/8/17已知能閱讀的都是有文化的；海豚是沒有文化的；某些海豚是有智能﹁I(w)∨R(w)I(A)R(A)﹁R(x)∨L(x)﹁D(y)∨﹁L(y)L(A)NIL﹁D(A)D(A)3.3使用歸結原理證明問題2023/8/17﹁I(w)∨R(w)I(A)R(A)﹁R(x)∨L(x)﹁D例4.6已知F1：王(wang)先生是小李(Li)的老師

F2：小李和小張(zhang)是同班同學

F3：如果x和y是同班同學，則x的老師就是y的老師。求：小張的老師是誰？解：1)定義謂詞：T(x,y):x是y的老師；C(x,y):x與y是同班同學3.4使用歸結原理求解2023/8/17例4.6已知F1：王(wang)先生是小李(Li)的老師3﹁C(Li,y)∨T(Wang,y)T(Wang,Li)﹁C(x,y)∨﹁T(z,x)∨T(z,y)﹁T(u,Zhang)∨T(u,Zhang)C(Li,Zhang)﹁C(Li,Zhang)∨T(Wang,Zhang)T(Wang,Zhang){Wang/z,Li/x}{Wang/u,Zhang/y}3.4使用歸結原理求解2023/8/17﹁C(Li,y)∨T(Wang,y)T(Wang,Li)﹁C作業(yè)1某公司招聘工作人員，A、B、C三人應試，經(jīng)面試后公司表示如下想法：

(1)三人中至少錄取一人

(2)如果錄取A而不錄取B，則一定錄取C

(3)如果錄取B，則一定錄取C

求證：公司一定錄取C2023/8/17作業(yè)1某公司招聘工作人員，A、B、C三人應試，經(jīng)作業(yè)2已知以下的事實：①Marcus是人。②Marcus是羅馬人。③Caser是一位統(tǒng)治者。④所有羅馬人或忠于Caser或仇恨他。⑤每個人都忠于某個人。⑥人們只想暗殺他們不忠于的統(tǒng)治者。⑦Marcus試圖暗殺Caser。求證：Marcus仇恨Caser。2023/8/17作業(yè)2已知以下的事實：①Marcus是人。②Marcu作業(yè)3設A、B、C三人中有人從不說真話，也有人從不說假話，某人向這三個人分別提出同一個問題：誰是說謊者？A答：“B和C都是說謊者”；B答“A和C都是說謊者”；C答：“A和B中至少有一個是說謊者。”求誰是老實人，誰是說謊者？2023/8/17作業(yè)3設A、B、C三人中有人從不說真話，也有人從

例2設有如下知識R1：IFATHEN(20，1)B1(0.03)R2：IFB1THEN(300，0.0001)B2(0.01)求：當證據(jù)A必然發(fā)生時,P(B2/A)的值是多少？

解:（1）由于A必發(fā)生，由R1得（2）由于B1不是必發(fā)生的，所以需作插值處理。例14.1主觀bayes方法2023/8/17例2設有如下知識解:（1）由于A必發(fā)生，由R1得

當時，有，所以在此區(qū)間插值。由于4.1主觀bayes方法2023/8/17當時，有，所以在此區(qū)間插值。由于4.1主觀bayes例2：設有如下知識

r1:IFE1THEN(20，1)H

r2:IFE2THEN(300,1)H已知P(H)=0.03，若證據(jù)E1，E2依次出現(xiàn)，求P(H|E1,E2)解法1：合成法O(H)=P(H)/(1-P(H))=0.0309由r1：O(H|E1)=LS1*O(H)=0.618由r2：O(H|E2)=LS2*O(H)=9.274.1主觀bayes方法2023/8/17例2：設有如下知識解法1：合成法O(H)=P(H)/(1-解法2：更新法2023/8/17解法2：更新法2023/8/5例3設有如下規(guī)則：

r1:IFE1THEN(2,0.000001)H1

r2:IFE2THEN(100,0.000001)H1

r3:IFH1THEN(65,0.01)H2

r4:IFE3THEN(300,0.0001)H2

且已知P(H1)=0.1,P(H2)=0.01,P(E1)=0.2,P(E2)=0.4,P(E3)=0.03P(E1|S1)=0.7,P(E2|S2)=0.6,P(E3|S3)=0.02,求P(H2|S1S2S3)4.1主觀bayes方法2023/8/17例3設有如下規(guī)則：

r1:IFE1THENE1H1E2E3H2(2,0.000001)(65,0.01)(300,0.0001)(100,0.000001)0.20.40.030.10.012023/8/17E1H1E2E3H2(2,0.000001)(65,0.01解(1)求P(H1|S1)2023/8/17解(1)求P(H1|S1)2023/8/5(2)求P(H1|S2)2023/8/17(2)求P(H1|S2)2023/8/52023/8/172023/8/52023/8/172023/8/52023/8/172023/8/52023/8/172023/8/54.2C-F方法已知R1：IFA1THENB1CF(B1,A1)=0.8；R2:IFA2THENB1CF(B1,A2)=0.5；R3:IFB1∧A3THENB2CF(B2,B1∧A3)=0.8;初始證據(jù)為A1,A2,A3的可信度CF均設為1，即,CF(A1)=CF(A2)=CF(A3)=1,對B1,B2一無所知,求CF(B1)和CF(B2)。例12023/8/174.2C-F方法已知例12023/8/5解:由于對B1,B2一無所知，所以使用合成算法進行計算。由題意得到推理網(wǎng)絡如下圖所示。B2B1A3A1A24.2C-F方法2023/8/17解:由于對B1,B2一無所知，所以使用合成算法進行計(1)對于知識R1,R2,分別計算CF1(B1),CF2(B1)(2)利用合成算法計算B1的綜合可信度(3)計算B2的可信度，這時，B1作為B2的證據(jù)，CF(B1)=0.9，而A3的可信度為初始制定的1。由規(guī)則R3得到4.2C-F方法2023/8/17(1)對于知識R1,R2,分別計算CF1(B1),CF2(B例2:設有如下規(guī)則：

R1：IFEITHENH(0.8)

R2：IFE2THENH(0.6)

R3:IFE3THENH(-0.5)

R4：IFE4ANDE5ORE6THENE1(0.7)

R5：IFE7ANDE8THENE3(0.9)

在系統(tǒng)運行中已從用戶處得CF(E2)=0.8，CF(E4)=0.5，CF(E5)=0.6，CF(E6)=0.7，CF(E7)=0.6，CF(E8)=0.9，求H的綜合可倍度CF(H)。4.2C-F方法2023/8/17例2:設有如下規(guī)則：

R1：IFEIT(1)求CF(E1),CF(E3)CF(E4AND(E5ORE6))=min{CF(E4),max{CF(E5),CF(E6)}}=0.5CF(E1)=0.7×max{0,CF(E4AND(E5ORE6))}=0.5×0.7=0.35

同理可得：CF(E3)=0.54(2)求CF1(H),CF2(H),CF3(H)CF1(H)=0.8×max{0,CF(E1)}=0.8×0.35=0.28CF2(H)=0.6×max{0,CF(E2)}=0.6×0.8=0.48CF3(H)=-0.5×max{0,CF(E3)}=-0.5×0.54=-0.274.2C-F方法2023/8/17(1)求CF(E1),CF(E3)4.2C-F方法20(3)求CF1,2(H),CF1,2,3(H)CF1,2(H)=CF1(H)＋CF2(H)-CF1(H)×CF2(H)=0.28+0.48-0.28×0.48=0.63CF1,2,3(H)=CF1,2(H)+CF3(H)=0.63-0.27=0.364.2C-F方法2023/8/17(3)求CF1,2(H),CF1,2,3(H)4.2C-ABCDE434523例：五個城市間的交通路線圖，A城是出發(fā)地．E是目的地，兩城市間的交通費用(代價)如圖數(shù)字所示。求從A到E最小費用交通路線。將交通圖轉換為代價樹從起始節(jié)點A開始，把與它直接相鄰的節(jié)點作為它的子節(jié)點。若一個節(jié)點已作為某節(jié)點的先輩節(jié)點時，就不能再作為這個節(jié)點的子節(jié)點。圖中除起始節(jié)點A外，其它節(jié)點都可能要在代價樹中出現(xiàn)多次，為區(qū)分它的多次出現(xiàn)．分別用下標1．2．…標出。5.1代價樹寬度優(yōu)先搜索2023/8/17ABCDE434AB1E19AB1D2E311AC1D1E28AC1D1B2E414245AC1B1D1D2E1E2B2C2E3E434342355.1代價樹寬度優(yōu)先搜索2023/8/17AB1E1f(n):從初始結點經(jīng)過n結點到達目的結點的最優(yōu)路徑的代價估計值。作用是評價open表中各節(jié)點的重要性，決定open表的次序h(n):從n到目標結點的最佳路徑的估計代價，稱為啟發(fā)函數(shù)。g(n):從初始結點到n已經(jīng)付出的實際代價

g(n)和h(n)各占適當?shù)谋戎匾话愕兀琯(n)的比重越大，越傾向于廣度優(yōu)先搜索，h(n)的比重越大，越傾向于深度優(yōu)先搜索。2.估價函數(shù)一般形式：f(n)=g(n)+h(n)5.2啟發(fā)信息和估價函數(shù)2023/8/17f(n):從初始結點經(jīng)過n結點到達目的結點的最優(yōu)路徑的代價估f(n)=d(n)+W(n)其中：d(n)表示節(jié)點n在搜索樹中的深度

W(n)表示節(jié)點n中“不在位”的數(shù)碼個數(shù)。計算初始狀態(tài)S0的估價函數(shù)值f(S0)【例】八數(shù)碼難題。設問題的初始狀態(tài)S0和目標狀態(tài)Sg如下圖所示，且估價函數(shù)為2

831476512384765S0Sg5.2啟發(fā)信息和估價函數(shù)2023/8/17f(n)=d(n)+W(n)【例】八數(shù)碼難題。設問題的初始狀2

831476512384765S0Sg解：取g(n)=d(n)，h(n)=W(n)。它說明是用從S0到n的路徑上的單位代價表示實際代價，用結點n中“不在位”的數(shù)碼個數(shù)作為啟發(fā)信息。一般來說，某節(jié)點中的“不在位”的數(shù)碼個數(shù)越多，說明它離目標節(jié)點越遠對初始節(jié)點S0，由于d(S0)=0，W(S0)=3，因此有f(S0)=0+3=35.2啟發(fā)信息和估價函數(shù)2023/8/1728312例：有如下結構的移動將牌游戲B:代表黑色將牌W：代表白色將牌E：代表該位置為空BEBWWBW規(guī)則：要求：把所有B移至所有W的右邊，計算h(x)5.2啟發(fā)信息和估價函數(shù)當一個將牌移入相鄰的空位置時，費用為1個單位。一個將牌至多可跳過兩個將牌進入空位置，其費用等于跳過的將牌數(shù)加1因為W左邊的B越少越接近目標．因此可用W左邊B的個數(shù)作為h(x);h(x)=3*(每個W左邊B的個數(shù)的總和）

2023/8/17例：有如下結構的移動將牌游戲BEBWWBW規(guī)則：要求：把所有廣度優(yōu)先、代價樹廣度優(yōu)先是全局擇優(yōu)搜索的特例2831476512384765估計函數(shù)：f(x)=d(x)+h(x)d(x)表示節(jié)點x的深度

h(x)表示節(jié)點的格局與目標格局不相同的牌數(shù)例：用全局擇優(yōu)搜索求解重排九宮問題初始狀態(tài)S0目標狀態(tài)Sg5.2全局擇優(yōu)搜索2023/8/17廣度優(yōu)先、代價樹廣度優(yōu)先是全局擇優(yōu)搜索的特例283147652831476528314765231847652831476528316475

8321476528371465

23184765231847651238476512378465123

847654455564644SgS1S2S36該問題的解為：

S0→S1→S2→S3→Sg5.2全局擇優(yōu)搜索2023/8八數(shù)碼難題。

S0Sgf(n)=d(n)+P(n)d(n)深度P(n)與目標距離f*=g*+h*2831476528314765231847652831476528316475

2318476523184765123847651237846512384765f=6g*=1h*=3f=6f=6

g*=2h*=2f=6f=4g*=3h*=1f=4g*=4h*=0f=4f=6f=45.3A*算法應用舉例h*=4f=42023/8/17例八數(shù)碼難題。S0Sgf(n)=d(n)+P(n)2例

修道士和野人問題。解：用m表示左岸的修道士人數(shù)，c表示左岸的野人數(shù)，b表示左岸的船數(shù)，用三元組(m,c,b)表示問題的狀態(tài)。對A*算法，首先需要確定估價函數(shù)。設g(n)=d(n)，h(n)=m+c-2b，則有f(n)=g(n)+h(n)=d(n)+m+c-2b其中，d(n)為節(jié)點的深度。通過分析可知h(n)≤h*(n)，滿足A*算法的限制條件。

M-C問題的搜索過程如下圖所示。5.3A*算法應用舉例2023/8/17例修道士和野人問題。解：用m表示左岸的修道士人數(shù)，c表示左(3,2,0)(3,1,0)(2,2,0)h(n)=m+c-2b(3,3,1)h=4f=4(3,2,1)(2,1,0)(3,0,0)(2,2,1)(3,1,1)(0,2,0)(1,1,0)(0,3,1)(0,1,0)(0,2,1)(0,0,0)h=5f=6h=3f=5h=3f=6h=3f=6h=2f=6h=2f=7h=1f=7h=1f=8h=0f=8h=4f=5h=4f=5h=2f=6h=2f=7傳教士和野人問題的搜索圖5.3A*算法應用舉例2023/8/17(3,2,0)(3,1,0)6.1基于決策樹的歸納學習方法1.決策樹決策樹由一個根結點，若干葉結點和若干非葉結點構成。根結點對應于學習任務。每個葉結點都包含一個分類名，即包含一個概念。每個非葉結點都包含一個屬性測試，對該屬性可能取的每一個值