《吉林大學(xué)計(jì)算機(jī)學(xué)院博士入學(xué)考試題, 計(jì)算智能》由會(huì)員分享，可在線閱讀，更多相關(guān)《吉林大學(xué)計(jì)算機(jī)學(xué)院博士入學(xué)考試題, 計(jì)算智能（8頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、人工智能原理2004年 一、回答下列問題(30分) 1、 什么叫寬度優(yōu)先搜索？寬度優(yōu)先搜索的優(yōu)點(diǎn)在何處？缺點(diǎn)在何處？ 2、 試說明邏輯符號“ n ”、"…”的含義和差別。 3、 請舉出輸入歸結(jié)演繹不完備的例子。 4、 設(shè)S={P(x),Q(f(a))}是子句集，請舉出I是S的普通解釋，而不是其Herbrand解釋的例子。 5、 請舉出公式與其Skolem范式不等價(jià)的例子。 6、 什么叫A算法？什么叫A*算法？什么叫A*算法是可采納的？兩個(gè)A*算法如何比較好壞？ 二、求解下列問題(30分) 1、設(shè)八數(shù)碼問題有估價(jià)函數(shù)：f(n)=d(n)+W(n)；其中d(n)是節(jié)點(diǎn)n在搜索樹中的

2、深度，W(n)是節(jié)點(diǎn)n中“不在位” 數(shù)碼的個(gè)數(shù)；試給出以下面為初始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的圖搜索過程，指明各節(jié)點(diǎn)估價(jià)函數(shù)值和整體解路徑，并計(jì)算 該搜索過程的滲透度是多少？有效分枝系數(shù)是多少？ 2、 將公式G化為Skolem范式，并給出G的子句集S。 G = V 乂 E( x a) T (3 y ( E ( y, g ( x) )V z (E (z , g Gx ) ) E (y z 3、 使用基于規(guī)則的正向演繹系統(tǒng)證明下面問題： 已知事實(shí)A v B ;規(guī)則兩條A T C a D，B T E a 6;目標(biāo)C v G。畫出演繹過程與/或圖。 三、 證明第一種形式的Herbrand定理：設(shè)S是

3、子句集，則S是不可滿足的，當(dāng)且僅當(dāng)對應(yīng)于S的每一個(gè)完全語 義樹都存在一個(gè)有限的封閉語義樹。(15分) 四、 總結(jié)a -8過程，并以下述博弈樹為例，以優(yōu)先產(chǎn)生左邊子節(jié)點(diǎn)的次序進(jìn)行a -8剪枝，指出在何處發(fā)生剪枝、 何處為a修剪、何處為8修剪？標(biāo)明發(fā)生剪枝的節(jié)點(diǎn)和初始節(jié)點(diǎn)返回值的變化。圖中□表示極大點(diǎn)，。表示極小 點(diǎn)。(15分) 3 0 -3 -1 -2 0 1 4 1 2 5 -1 1 -1 -1 3 -3 2 3 6 -2 五、什么叫支架集歸結(jié)演繹，試證明基子句集支架集歸結(jié)演繹的完備性。(10分) 人工智能原理2003年 一、敘述圖搜索算法GRAPHSEARCH過程；設(shè)八數(shù)碼問題有兩

4、個(gè)估價(jià)函數(shù)：fi(n)=d(n)+W(n)； f2(n)=d(n)+P(n)+3S(n)。其中d(n)是節(jié)點(diǎn)n在搜索樹中的深度，W(n)是節(jié)點(diǎn)n中“不在位”數(shù)碼的個(gè)數(shù)，P(n)是每 個(gè)數(shù)碼離開目標(biāo)位置的距離的和。S(n)是由如下方式得到的序列分：對于非中心的外圈上的數(shù)碼沿順時(shí)針方向走 一圈，如果一個(gè)數(shù)碼后面的數(shù)碼不是它在目標(biāo)狀態(tài)下的后繼者，則給這個(gè)數(shù)碼記2分，否則記0分；對于中心位 置，有數(shù)碼的記1分，沒有的話記0分。然后把所有上述得分加起來，就得到序列分S(n)?，F(xiàn)有初始狀態(tài)和目標(biāo) 狀態(tài)描述如下：請畫出各自的啟發(fā)式搜索過程圖，在圖中標(biāo)明各節(jié)點(diǎn)的估價(jià)函數(shù)值，并標(biāo)明節(jié)點(diǎn)擴(kuò)展的次序。計(jì) 算出各自的

5、滲透度和有效分枝系數(shù)。(40分) 345 2 I 1 I 7 初始狀態(tài) 1 I 8 | 7 目標(biāo)狀態(tài) 二、總結(jié)博弈搜索的極小極大過程和a -p過程，并以下述博弈樹為例，給出兩個(gè)過程的各節(jié)點(diǎn)返回值和搜索到 的路徑(請畫出兩個(gè)過程圖)。對于其中的a -p過程以優(yōu)先產(chǎn)生左邊子節(jié)點(diǎn)的次序進(jìn)行a -p剪枝，指出在何處 發(fā)生剪枝、何處為a修剪、何處為p修剪？標(biāo)明發(fā)生剪枝的節(jié)點(diǎn)和初始節(jié)點(diǎn)返回值的變化。圖中□表示極大點(diǎn)， 。表示極小點(diǎn)。(20分) 3 -3 0 -1 -2 0 1 4 5 1 -1 -1 3 3 2 -2 三、 (27分) 1、 設(shè)子句集S = {P (x), Q (f

6、(y)) v R (y)}，求S的H域，S的原子集，子句C = Q (f (y)) v R (y)的基例集合。 2、 使用合一算法判斷表達(dá)式集合W={Q(f(a), g(x)), Q(y, y)}是否可合一，若可合一，則求出最一般合一。 3、 試用表推演方法證明{Vx(P (x) T Q (x)), Vy (Q (y) T R (y)), 3z(□ R (z))}共同蘊(yùn)含 3 u (□ P (u))。 四、 設(shè)S是命題邏輯子句集，P是S中出現(xiàn)的一個(gè)原子符號，于是可將S中子句分為三部分：含有文字P的部分 S = {C v P,..., C v P}，含有文字?P的部分S = {B v □

7、 P,..., B v □ P}，和不含文字P 或~P的部分S。令 1 1 n 2 1 m 3 S ' = {C，…，C} uS，S ' = {B ,..., B } u S，請證明S是不可滿足的當(dāng)且僅當(dāng)S1’，S2 ’都是不可滿足的。(8 1 1 n 3 2 1 m 3 分) 五、 請舉出基于規(guī)則的正向演繹系統(tǒng)不完備的例子。(5分) By W01F STUDIO 人工智能原理2002年 一、 簡要回答下列問題(24分) 1、 以八數(shù)碼問題為例，說明產(chǎn)生式系統(tǒng)的基本組成。 2、 什么叫A*算法？ A*算法的主要性質(zhì)是什么？ 3、 在基于規(guī)則的演繹系統(tǒng)中，什么是合一復(fù)合替換？為

8、什么要考慮替換的相容性？ 4、 在基于規(guī)則的正向演繹系統(tǒng)中，規(guī)則和目標(biāo)各要求怎樣的形式？ 5、 基于規(guī)則的正向演繹系統(tǒng)是否完備？反向演繹是否完備？雙向演繹是否完備？ 6、 在啟發(fā)式搜索中，估價(jià)函數(shù)一般定義為f(n)=g(n)+h(n)，指明定義中各部分的含義，并說明為什么使用這種 定義方式。 7、 在合一算法中，設(shè)W是非空表達(dá)式集合，D是W的差異集合，則當(dāng)D具有怎樣的形式時(shí)，W是不可合一的？ 8、 常用的知識表示方法有哪幾種，簡要回答各自的特點(diǎn)。 二、 判斷對錯(cuò)(14分) 1、 OPEN表上任一具有f(n) Wf*(s)的點(diǎn)，最終都將被A*算法選作擴(kuò)展的節(jié)點(diǎn)。 2、 若滿足單調(diào)

9、限制，則A*算法所擴(kuò)展的節(jié)點(diǎn)序列的f值是單調(diào)遞增的。 3、 設(shè)。，入是兩個(gè)替換，則。?入小-0。 4、 表達(dá)式集合 W={P(f(x), g(y, z), z), P(y, h(k(x)), f(z))}是可合一的。 5、 滲透度和有效分枝系數(shù)都是關(guān)于圖搜索方法啟發(fā)能力的空間復(fù)雜性度量標(biāo)準(zhǔn)。 6、 子句集S恒假，當(dāng)且僅當(dāng)對每一個(gè)解釋I，使S中的每個(gè)子句C的基例很被I弄假。 7、 一階邏輯中任一公式是否是恒假的，可用歸結(jié)方法判定。 三、 (12分) 1、 若 E=Q(y, f(y, g(x))), 0 ={a/x, b/y, y/z},入={a/x, z/y, f(x)/z},求

10、Ee, Ex, Ee .入 2、 使用回溯搜索策略求解四皇后問題。其中規(guī)則排序使用對角線函數(shù)diag(i, j)，若diag(i, j)Vdiag(m, n)，則在排 序中把規(guī)則％放在規(guī)則Rmn的前面。diag (i, j)定義為用過單元(i, j)的最長對角線的長度。若diag函數(shù)值相同則規(guī) 則隨機(jī)排序。" 四、 使用歸結(jié)方法證明下述子句集是不可滿足的(寫出整個(gè)歸結(jié)過程和每一步歸結(jié)使用的合一替換)。 S = {A(a, f (c), f (b)), B (a), A(x, x, f (x)), 口 A(x, y, z) v C (x, z), 口 B (x) v 口 A(y, z, u

11、) v 口 C (x, u) v C (x, y) v C (x, z), 口 C (a,b)} (10 分) 五、設(shè)產(chǎn)生式系統(tǒng)PS，其狀態(tài)集合DB={a, b, c, d, e, f, g, h, i, m}，產(chǎn)生式規(guī)則為: a—b，c —m，g—h，a—c，d—e，h—i，a—d，e—f，m—i，b—g，f—m 狀態(tài) a b c d e f g h i m h值 1 1 8 2 2 2 4 4 10 4 狀態(tài) a b c d e f g h i m h值 1 1 8 2 2 2 4 4 10 4

12、 設(shè)a為初始狀態(tài)，規(guī)則應(yīng)用費(fèi)用為1，各狀態(tài)的啟發(fā)函數(shù)值為: 用A算法畫出節(jié)點(diǎn)c擴(kuò)展前與擴(kuò)展后的搜索圖與搜索樹，要求標(biāo)出圖中節(jié)點(diǎn)的擴(kuò)展次序、 點(diǎn)c擴(kuò)展前CLOSED表與OPEN表中的元素。(15分) 估價(jià)函數(shù)值，寫出節(jié) 六、已知子句集S={P(g(x), z),?P(f(y), h(a))}，求S的原子集、S的語義樹。若給定S的一個(gè)解釋I如下: D={1, 2} a g(1) g(2) f(1) f(2) h(1) h(2) P(1, 1) P(2, 2) P(2, 1) P(1, 2) 2 2 1 1 2 2 1 F F 請構(gòu)造S對應(yīng)與I的H解釋I*。(15分) 人

13、工智能原理2002年 七、對下面的博弈樹以優(yōu)先產(chǎn)生左邊子節(jié)點(diǎn)的次序進(jìn)行a -8剪枝，指出在何處發(fā)生剪枝、何處為a修剪、何處 為8修剪？標(biāo)明發(fā)生剪枝的節(jié)點(diǎn)和初始節(jié)點(diǎn)返回值的變化，以及搜索到的路徑。圖中□表示極大點(diǎn)，。表示極小 點(diǎn)。說明一般的a -8剪枝過程中，什么情況下效率最高。（10分） -1 3 3 2 -2 3 -3 0 -1 -2 0 1 4 5 1 -1 人工智能原理2000年 一、 簡要回答下列問題(24分) 1、 請敘述產(chǎn)生式系統(tǒng)的過程。 2、 回答產(chǎn)生式系統(tǒng)的分類，并說明各自的優(yōu)缺點(diǎn)。 3、 敘述什么樣的產(chǎn)生式系統(tǒng)是可交換的產(chǎn)生式系統(tǒng)。 4、 說明無信息的圖搜索

14、過程與啟發(fā)式圖搜索過程的差異，并舉出兩種典型的無信息圖搜索方法。 5、 敘述一階邏輯解釋的定義。 6、 在語義上證明子句集恒假時(shí)，僅考慮該子句集的Herbrand解釋是否夠用？為什么？ 7、 在基于規(guī)則的演繹系統(tǒng)中，什么是合一復(fù)合替換？為什么要考慮替換的相容性？ 8、 機(jī)器學(xué)習(xí)一般分為哪幾種類型？ 二、 設(shè)八數(shù)碼問題有估價(jià)函數(shù)：f(n)=d(n)+W(n)；其中d(n)是節(jié)點(diǎn)n在搜索樹中的深度，W(n)是節(jié)點(diǎn)n中“不在 位”數(shù)碼的個(gè)數(shù)?，F(xiàn)有初始狀態(tài)描述和目標(biāo)狀態(tài)描述如下： 初始狀態(tài) 目標(biāo)狀態(tài) 請畫出啟發(fā)式搜索過程圖，在圖中標(biāo)明各節(jié)點(diǎn)的估價(jià)函數(shù)值，并標(biāo)明節(jié)點(diǎn)擴(kuò)展的次序。(20

15、分) 、試用表推演方法證明(V X (P (x) T Q (x)), V y (Q (y) T R (y)), 3 z (□ R (z))｝共同蘊(yùn)含 3 u (□ P (u))。(16 分) 四、 敘述合一算法，并用合一算法求出W=(P(a, x, f(g(y))), P(z, f(z), f(u))｝的最一般合一。(寫出算法的執(zhí)行步驟， 20分) 五、 欲對某一有解的圖搜索問題試用A*算法，試證明A*算法終止前的任何時(shí)刻OPEN表中總存在節(jié)點(diǎn)n’，n’在 最佳解路徑上，滿足f(n’)Wf*(s)，其中s為初始節(jié)點(diǎn)。(15分) 六、 在歸結(jié)推理方法中，若不取因子而僅使用二元?dú)w結(jié)式是不完

16、備的，請舉出一個(gè)反例。(5分) 人工智能原理xxxx年 一、回答下列問題(20分) 1、 什么是可交換產(chǎn)生式系統(tǒng)？ 2、 影響A算法啟發(fā)能力的因素有哪些？ 3、 敘述a -8過程的剪枝規(guī)則。 4、 歸結(jié)原理有哪幾種重要的改進(jìn)？ 5、 描述基于規(guī)則的正向演繹系統(tǒng)的初始狀態(tài)、規(guī)則和目標(biāo)的一般形式。 二、請用估價(jià)函數(shù)：f(n)=d(n)+W(n)求解八數(shù)碼問題，其中d(n)是節(jié)點(diǎn)n在搜索樹中的深度，W(n)是節(jié)點(diǎn)n中“不 在位”數(shù)碼的個(gè)數(shù)。 n1 n n° % % % n6 七 n§ h(n) 0 2 4 4 1 1 2 0 0

17、 n4 初始狀態(tài) 目標(biāo)狀態(tài) 畫出啟發(fā)式搜索過程圖，在圖中標(biāo)明各節(jié)點(diǎn)的估價(jià)函數(shù)值，并標(biāo)明節(jié)點(diǎn)擴(kuò)展的次序。(20分) 三、 敘述合一算法，并用該算法尋找表達(dá)式集W=｛R(x, x), R(f(a), g(y))｝的最一般合一。(20分) 四、 使用AOT算法，啟發(fā)函數(shù)應(yīng)滿足什么條件？下圖是已給出的與/或圖，其中n0是初始節(jié)點(diǎn)，｛n7 n8｝是目標(biāo)節(jié) 點(diǎn)集，h是啟發(fā)函數(shù)，并假定k-連接符的費(fèi)用是k。請用Ab算法求解其最優(yōu)解圖。(20分) ^ n0 n8 n3 n5 n7 * 五、證明下述歸結(jié)方法的完備性定理：如果基子句集S是不可滿足的，則存在從S推出空子句的歸

18、結(jié)演繹。(20 分) 人工智能原理xxxx年A 一、 簡要回答下列問題 1、 人工智能的主要研究領(lǐng)域有哪些？ 2、 產(chǎn)生式系統(tǒng)由哪幾部分組成？各部分的作用是什么？ 3、 產(chǎn)生式系統(tǒng)的控制策略有哪幾種方式？ 4、 什么是深度優(yōu)先搜索？什么是寬度優(yōu)先搜索？ 5、 什么叫啟發(fā)信息？它是如何使用的？ 6、 影響A算法啟發(fā)能力的要素有哪些？ 7、 搜索方法的啟發(fā)能力有哪幾種基本的度量方法？ 8、 什么是從子句集S推出子句C的歸結(jié)演繹？ 9、 什么是可交換產(chǎn)生式系統(tǒng)？ 10、 在歸結(jié)演繹中，什么叫最一般的合一替換？ 二、 試述可分解產(chǎn)生式系統(tǒng)的基本過程。 三、已知八數(shù)碼難題的初

19、始狀態(tài)和目標(biāo)狀態(tài)為: n1 n n° % % % % % n6 七 % h(n) 0 2 4 4 1 1 2 0 0 n4 初始狀態(tài) 目標(biāo)狀態(tài) 設(shè)估價(jià)函數(shù)：f(n)=d(n)+W(n)，其中d(n)是節(jié)點(diǎn)n在搜索樹中的深度，W(n)是節(jié)點(diǎn)n中“不在位”數(shù)碼的個(gè)數(shù)。 畫出使用此函數(shù)A算法解題的搜索樹，在樹上標(biāo)明各節(jié)點(diǎn)的估價(jià)函數(shù)值及選擇擴(kuò)展節(jié)點(diǎn)的次序。 四、已知與/或圖，其中n0是初始節(jié)點(diǎn)，｛n7 %｝是目標(biāo)節(jié)點(diǎn)集，h是啟發(fā)函數(shù)，并假定k-連接符的費(fèi)用是k。請 用A。算法求解其最優(yōu)解圖。 ^ n0 n8 n3

20、n5 n7 bJ 五、試用歸結(jié)演繹證明公式Vx(R (x) — 口 Q(x))是公式集 {□ (3x3 j(P(x) a Q (y) a S (x, j))), 3x(P(x) a V j(R (j) - S (x, j)))} 的邏輯結(jié)果。 人工智能原理xxxx年B 一、簡要回答下列問題 1、 無信息的圖搜索方法主要有哪兩種？ 2、 簡述各種搜索策略各自的優(yōu)缺點(diǎn)。 3、 影響A算法啟發(fā)能力的要素有哪些？ 4、 一階邏輯中，公式是怎樣定義的？ 5、 一階邏輯中，公式的解釋是怎樣定義的? 6、 命題邏輯中，常用哪兩種公式范式？ 7、 一階邏輯中，常用哪兩種公式范式？

21、8、 什么叫子句集的Herbrand域？ 、試述圖搜索算法GRAPHSEARCH。 三、已知八數(shù)碼難題的初始狀態(tài)和目標(biāo)狀態(tài)為: 初始狀態(tài) 目標(biāo)狀態(tài) 設(shè)估價(jià)函數(shù)：f(n)=d(n)+W(n)，其中d(n)是節(jié)點(diǎn)n在搜索樹中的深度，W(n)是節(jié)點(diǎn)n中“不在位”數(shù)碼的個(gè)數(shù)。 畫出使用此函數(shù)A算法解題的搜索樹，在樹上標(biāo)明各節(jié)點(diǎn)的估價(jià)函數(shù)值及選擇擴(kuò)展節(jié)點(diǎn)的次序。 四、寫出下述公式的Skolem范式： G = □ (3 缶 y (P (x) a Q (y) a S (x, y))) a3 x (P (x) a V y (R (y) r S (x, y))) 五、 請用歸結(jié)方法證明子句集S = {P v Q, □ P v Q, Pv □ Q, □ Pv □ Q}是不可滿足的。 六、 請使用回溯搜索策略求解四皇后問題。其中規(guī)則排序使用對角線函數(shù)diag(i, j)，若diag(i, j)Vdiag(m, n)，則 在排序中把規(guī)則％放在規(guī)則Rmn的前面。diag (i, j)定義為用過單元(i, j)的最長對角線的長度。