人工智能重點復(fù)習(xí)題

1、1、盲目搜索（寬度、深度）圖搜索a abdg abdcegkl abdcefeigkoldh ,open集就是當(dāng)前的葉子結(jié)點尚待進(jìn)一步分解的節(jié)點廣度優(yōu)先的open集合 : a, bdg, cekl, fioh, jm,n 深度優(yōu)先的open集合 : a, bdg, dg, ceg, feg, jieg, ig, mg, ng,2、a*算法某問題的狀態(tài)空間圖如下圖所示，其中括號內(nèi)標(biāo)明的是各節(jié)點的h 值，弧線邊的數(shù)字是該弧線的耗散值， 試用 a算法求解從初始節(jié)點s到目標(biāo)節(jié)點t的路徑。 要求給出搜索圖，標(biāo)明各節(jié)點的 f 值，及各節(jié)點的擴(kuò)展次序，并給出求得的解路徑。a b g d l h e c k

2、o m i f n j 3、- 剪枝下圖所示博弈樹，按從左到右的順序進(jìn)行- 剪枝搜索， 試標(biāo)明各生成節(jié)點的到推值，何處發(fā)生剪枝，及應(yīng)選擇的走步。4、猴子香蕉問題狀態(tài)空間圖猴子香蕉問題狀態(tài)空間圖5、問題歸約機(jī)理設(shè)想把三元狀態(tài)組(s,f,g) 規(guī)定的狀態(tài)空間搜索問題歸結(jié)為比較簡單的一些狀態(tài)空間搜索問題。如果能夠識別某個適當(dāng)?shù)摹奥窐?biāo)”狀態(tài)序列g(shù)1,g2,.,gn,那么就能夠把初始問題歸約為由三元狀態(tài)(s,f,g1),( g1,f,g2),.,(gn,f,g)規(guī)定的問題集合。解答所有這些問題就等價于解答該初始問題。6、用語義網(wǎng)絡(luò)表示下列命題(1) 樹和草都足植物。(2) 樹和草是有根、有葉的。(3)

3、水草是草，且長在水中。(4) 果樹是樹，且會結(jié)果。(5) 蘋果樹是果樹中的一種，它結(jié)蘋果。問題涉及的對象有植物、樹、草、水草、果樹、蘋果樹共6 個對象。各對象的屬性如下：樹和草的屬性：有根、有葉；水草的屬性：長在水中；果樹的屬性：會結(jié)果；蘋果樹的屬性：結(jié)蘋果。關(guān)系：樹和草與植物問的關(guān)系是ako 水草和草之間的關(guān)系是ako 果樹和樹之間的關(guān)系是ako蘋果樹和果樹間的關(guān)系是ako 7、語義網(wǎng)絡(luò)圖中的全稱量詞表示每個學(xué)生都學(xué)習(xí)了所有的程序設(shè)計課程8、化下列公式成子句形式：(1) (x) p(x)p(x)(2) xy(on(x,y) above(x,y) (3) xyz(above(x,y) abov

4、e(y,z) above(x,z) (4) (x)p(x) （y） p(y)p(f(x,y) (y)q(x,y) p(y) 9、反演歸結(jié)(1) 、試用歸結(jié)法證明( x)r(x) ；(2) 、做出修改證明樹，提取問題的回答。s i p g 程序語言學(xué)習(xí)學(xué)生gs f是一是一是一是一主體客體具有兩個全稱量詞的語義（2）給定下述語句：john likes all kinds of food. apples are food. anything anyone eats and isnt killed by is food. bill eats peanuts and is still alive. su

5、e eats everything bill eats. （1）用歸結(jié)法證明john likes peanuts。 （2）用歸結(jié)法提取回答what food does sue eat? 該問題用謂詞公式描述如下：已知：（1）(x)food(x) like(john, x)（2）food(apple) （3）(x)(y)eat(y, x) kill(x, y)food(x) （4）eat(bill, peanut) kill(penut, bill) （5）(x)eat(bill, x)eat(sue, x)目標(biāo) 1：like(john, peanut) 目標(biāo) 2：(x)food(x) eat(

6、sue, x) 已知條件化子句集：（1）(x)food(x) like(john, x)= (x)food(x) like(john, x) = food(x) like(john, x) （2）food(apple) （3）(x)(y)eat(y, x) kill(x, y)food(x)= (x)(y)eat(y, x) kill(x, y) food(x) = (x)(y)eat(y, x) kill(x, y) food(x) = eat(y, x) kill(x, y) food(x) （4）eat(bill, peanut) kill(penut, bill) = eat(bill

7、, peanut), kill(penut, bill) （5）(x)eat(bill, x)eat(sue, x)= (x)eat(bill, x) eat(sue, x) = eat(bill, x) eat(sue, x) 目標(biāo) 1 取反化子句集：like(john, peanut) 目標(biāo) 2 取反化子句集：(x)food(x) eat(sue, x) = (x)food(x) eat(sue, x) = food(x) eat(sue, x) 對于目標(biāo) 1，經(jīng)變量換名后，得子句集：food(x1) like(john, x1)，food(apple) ，eat(y2, x2)kill(

8、x2, y2)food(x2) ，eat(bill, peanut), kill(penut, bill), eat(bill, x3)eat(sue, x3), like(john, peanut) 歸結(jié)樹如下：對于目標(biāo) 2，經(jīng)變量換名后，得子句集：food(x1) like(john, x1) ，food(apple) ，eat(y2, x2) kill(x2, y2) food(x2) ，eat(bill, peanut), kill(penut, bill), eat(bill, x3)eat(sue, x3), food(x) eat(sue, x) 歸結(jié)樹如下：修改證明樹如下：得到

9、解答為：food(peanut)eat(sue, peanut) （3） “快樂學(xué)生”問題。假設(shè)：任何通過計算機(jī)考試并獲獎的人都是快樂的，任何肯學(xué)習(xí)或幸運(yùn)的人都可以通過所有考試，張不肯學(xué)習(xí)但他是幸運(yùn)的，任何幸運(yùn)的人都能獲獎。求證：張是快樂的將上述謂詞公式轉(zhuǎn)化為子句集如下：（1） pass（x， computer ） win（x， prize ） happy（x）（2） study （y） pass （y，z）（3） lucky（u） pass （u，v）（4） study （zhang）（5）lucky（zhang）（6） lucky（w） win （w， prize）（7） happy（zh

10、ang） （本子句為結(jié)論的否定）按謂詞邏輯的歸結(jié)原理對此子句集進(jìn)行歸結(jié)，其歸結(jié)反演過程如圖所示。由于歸結(jié)出了空子句，這就證明了張是快樂的。（4） “激動人心的生活”問題。假設(shè)：所有不貧窮并且聰明的人都是快樂的。那些看書的人是聰明的。李明能看書且不貧窮?？鞓返娜诉^著激動人心的生活。求證：李明過著激動人心的生活。將上述謂詞公式轉(zhuǎn)化為子句集如下：（1）poor（ x） smart（x） happy（x）（2） read（y） smart （y）（3） read（ liming ）（4） poor（ liming ）（5） happy（z） exciting（ z）（6） exciting（limin

11、g ）按謂詞邏輯的歸結(jié)原理對此子句集進(jìn)行歸結(jié)，其歸結(jié)反演過程如圖所示。由于歸結(jié)出了空子句，這就證明了李明過著激動人心的生活pass(x,computer) win(x,prize) lucky(w)win(w,prize) happy(zhang) pass(w,computer) happy(w) lucky(w) pass(zhang,computer) lucky(zhang) lucky(zhang) lucky(u)pass(u,v) pass(zhang,computer) lucky(zhang) lucky(zhang) w/x zhang/w zhang/u,computer

12、/v “ 快樂學(xué)生 ” 問題的歸結(jié)反演樹nil （5）“ 激動人心的生活” 問題的歸結(jié)反演樹exciting(liming) happy(z) exciting(z) poor(x) smart(x) happy(x) happy(liming) read(y) smart(y) poor(liming)smart(liming) poor(liming) nil liming/z liming/x liming/y poor(liming)read(liming) read(liming) read(liming ) （6）猴子香蕉問題（7）例 已知：張和李是同班同學(xué)，如果x 和 y 是同班

13、同學(xué)，則x 的教室也是y 的教室，現(xiàn)在張在 302 教室上課。問：現(xiàn)在李在哪里上課？解：首先定義謂詞： c(x,y) x和 y 是同班同學(xué)； at(x,u) x在 u 教室上課。把已知前提用謂詞公式表示如下： c(zhang,li); at(zhang,302) (x)(y)(u)(c(x,y) at(x,u) at(y,u) 把目標(biāo)的否定用謂詞公式表示如下： (v)at(li,v) 把上述公式化為子句集： c(zhang,li), at(zhang,302), c(x,y) at(x,u) at(y,u) 把目標(biāo)的否定化成子句式，并用重言式at(li，v) at(li，v) 代替之。并利用

14、skolem 函數(shù)消去存在量詞。10、正向規(guī)則演繹（1）（2）（3）11、逆向規(guī)則演繹(1）某問題由下列公式描述：(1) 、 （ s）p（s）(2) 、 （s） （p（g（s） ） ）(3) 、 （ x） （s） （ y） （ （ p（s） q（b，x，s） ）h（ y）(4) 、 （x） （s） （q （b，x，s）q （ b，x，g（s） ） ）(5) 、 （x） （s） （ y） （p（s）q （ b，x，y） ）求證： (x)h(x) 請用基于規(guī)則的逆向演繹系統(tǒng)求解( x)h(x) 成立。要求給出一個求得的一致解圖，并說明為什么它是一致的；給出目標(biāo)的解答。證明 : 對事實和規(guī)則進(jìn)行sk

15、olem 化：（1）(s) p （s）p(a) （2）(s)(p(g(s) p(g(s) （3）(x)(s)(y)(p(s)q(b，x，s) h(y)(p(s) q(b，c，s) h(f(s) （4）(x)(s)(q(b ，x，s) q(b， x， g(s) q(b， x，s) q(b， x，g(s) （5）(x)(s)(y)(p(s) q(b， x，y) p(s) q(b， x，h(x, s) 經(jīng)變量換名后，有事實和規(guī)則如下：p(a) p(g(s1) r1: (p(s2)q(b，c，s2) h(f(s2) r2: q(b，x3，s3) q(b， x3，g(s3) r3: p(s4)q(b，

16、x4，h(x4, s4) 用對偶形式對目標(biāo)skolem 化：( x)h(x) h(x) 演繹圖如下圖(這里只給出了一個一致解圖)。由置換集構(gòu)造u1和 u2：u1 = (x, s2, x3, s2, x4, s3, s4) u2 = (f(s2), g(s1), c, g(s3), c, h(x4, s4), a) 由于 u1和 u2是可合一的，因此該解圖是一致解圖。合一復(fù)合為：f(g(h(c, a)/x, g(h(c, a)/s2, c/x3, h(c, a)/s3, c/x4, h(c, a)/s1, a/s4 將該合一復(fù)合帶入目標(biāo)中，得到解答：x = f(g(h(c, a) （2） 設(shè)有如

17、下事實和規(guī)則:事實：f1: dog(fido) ；狗的名字叫fido f2: barks(fido) ；fido 是不叫的f3: wags-tail(fido) ；fido 搖尾巴f4: meows(myrtle) ；貓咪的名字叫myrtle 規(guī)則：r1: (wags-tail(x1) dog(x1) friendly(x1); 搖尾巴的狗是溫順的狗r2: (friendly(x2) barks(x2) afraid(y2,x2) ；溫順而又不叫的東西是不值得害怕的r3: dog(x3) animal(x3) ；狗為動物r4: cat(x4) animal(x4) ；貓為動物r5: meows

18、(x5) cat(x5) ；貓咪是貓問題：是否存在這樣的一只貓和一條狗，使得這只貓不怕這條狗?12、產(chǎn)生式系統(tǒng)對 n5、k3 時，求解傳教士和野人問題的產(chǎn)生式系統(tǒng)各組成部分進(jìn)行描述（給出綜合數(shù)據(jù)庫、規(guī)則集合的形式化描述，給出初始狀態(tài)和目標(biāo)條件的描述）。答： 1 ，綜合數(shù)據(jù)庫定義三元組： （m, c, b）其中：，表示傳教士在河左岸的人數(shù)。，表示野人在河左岸的認(rèn)輸。， b=1，表示船在左岸，b=0，表示船在右岸。2，規(guī)則集規(guī)則集可以用兩種方式表示，兩種方法均可。第一種方法：按每次渡河的人數(shù)分別寫出每一個規(guī)則，共(3 0)、(0 3)、(2 1)、(1 1) 、(1 0) 、(0 1) 、(2 0) 、(0 2) 八種渡河的可能（其中(x y)表示 x 個傳教士和y 個野人上船渡河） ，因此共有16 個規(guī)則（從左岸到右岸、右岸到左岸各八個）。注意：這里沒有(1 2) ，因為該組合在船上的傳教士人數(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