《吉林大學計算機學院博士入學考試題, 計算智能》由會員分享，可在線閱讀，更多相關《吉林大學計算機學院博士入學考試題, 計算智能（8頁珍藏版）》請在裝配圖網上搜索。

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

2、深度，W(n)是節(jié)點n中“不在位” 數碼的個數；試給出以下面為初始節(jié)點和目標節(jié)點的圖搜索過程，指明各節(jié)點估價函數值和整體解路徑，并計算 該搜索過程的滲透度是多少？有效分枝系數是多少？ 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)證明下面問題： 已知事實A v B ;規(guī)則兩條A T C a D，B T E a 6;目標C v G。畫出演繹過程與/或圖。 三、 證明第一種形式的Herbrand定理：設S是

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

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

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

6、(y)) v R (y)}，求S的H域，S的原子集，子句C = Q (f (y)) v R (y)的基例集合。 2、 使用合一算法判斷表達式集合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))}共同蘊含 3 u (□ P (u))。 四、 設S是命題邏輯子句集，P是S中出現的一個原子符號，于是可將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是不可滿足的當且僅當S1’，S2 ’都是不可滿足的。(8 1 1 n 3 2 1 m 3 分) 五、 請舉出基于規(guī)則的正向演繹系統(tǒng)不完備的例子。(5分) By W01F STUDIO 人工智能原理2002年 一、 簡要回答下列問題(24分) 1、 以八數碼問題為例，說明產生式系統(tǒng)的基本組成。 2、 什么叫A*算法？ A*算法的主要性質是什么？ 3、 在基于規(guī)則的演繹系統(tǒng)中，什么是合一復合替換？為

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

9、限制，則A*算法所擴展的節(jié)點序列的f值是單調遞增的。 3、 設。，入是兩個替換，則。?入小-0。 4、 表達式集合 W={P(f(x), g(y, z), z), P(y, h(k(x)), f(z))}是可合一的。 5、 滲透度和有效分枝系數都是關于圖搜索方法啟發(fā)能力的空間復雜性度量標準。 6、 子句集S恒假，當且僅當對每一個解釋I，使S中的每個子句C的基例很被I弄假。 7、 一階邏輯中任一公式是否是恒假的，可用歸結方法判定。 三、 (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ī)則排序使用對角線函數diag(i, j)，若diag(i, j)Vdiag(m, n)，則在排 序中把規(guī)則％放在規(guī)則Rmn的前面。diag (i, j)定義為用過單元(i, j)的最長對角線的長度。若diag函數值相同則規(guī) 則隨機排序。" 四、 使用歸結方法證明下述子句集是不可滿足的(寫出整個歸結過程和每一步歸結使用的合一替換)。 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 分) 五、設產生式系統(tǒng)PS，其狀態(tài)集合DB={a, b, c, d, e, f, g, h, i, m}，產生式規(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、 設a為初始狀態(tài)，規(guī)則應用費用為1，各狀態(tài)的啟發(fā)函數值為: 用A算法畫出節(jié)點c擴展前與擴展后的搜索圖與搜索樹，要求標出圖中節(jié)點的擴展次序、 點c擴展前CLOSED表與OPEN表中的元素。(15分) 估價函數值，寫出節(jié) 六、已知子句集S={P(g(x), z),?P(f(y), h(a))}，求S的原子集、S的語義樹。若給定S的一個解釋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 請構造S對應與I的H解釋I*。(15分) 人

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

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

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

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

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

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

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

20、n5 n7 bJ 五、試用歸結演繹證明公式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)))} 的邏輯結果。 人工智能原理xxxx年B 一、簡要回答下列問題 1、 無信息的圖搜索方法主要有哪兩種？ 2、 簡述各種搜索策略各自的優(yōu)缺點。 3、 影響A算法啟發(fā)能力的要素有哪些？ 4、 一階邏輯中，公式是怎樣定義的？ 5、 一階邏輯中，公式的解釋是怎樣定義的? 6、 命題邏輯中，常用哪兩種公式范式？ 7、 一階邏輯中，常用哪兩種公式范式？

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