吉林大學(xué)計算機學(xué)院博士入學(xué)考試題, 計算智能

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

2、以下面為初始節(jié)點和目標節(jié)點的圖搜索過程，指明各節(jié)點估價函數(shù)值和整體解路徑，并計算 該搜索過程的滲透度是多少？有效分枝系數(shù)是多少？2、將公式G化為Skolem范式，并給出G的子句集S。G = V 乂E(xa) T(3y ( E (y,g ( x)Vz (E (z , gGx ) )E(yz3、使用基于規(guī)則的正向演繹系統(tǒng)證明下面問題：已知事實A v B ;規(guī)則兩條A T C a D，B T E a 6;目標C v G。畫出演繹過程與/或圖。三、證明第一種形式的Herbrand定理：設(shè)S是子句集，則S是不可滿足的，當且僅當對應(yīng)于S的每一個完全語 義樹都存在一個有限的封閉語義樹。(15分)四、總結(jié)a

3、-8過程，并以下述博弈樹為例，以優(yōu)先產(chǎn)生左邊子節(jié)點的次序進行a -8剪枝，指出在何處發(fā)生剪枝、 何處為a修剪、何處為8修剪？標明發(fā)生剪枝的節(jié)點和初始節(jié)點返回值的變化。圖中表示極大點，。表示極小 點。(15分)30 -3-1-2014125-11-1-13-3236-2五、什么叫支架集歸結(jié)演繹，試證明基子句集支架集歸結(jié)演繹的完備性。(10分)人工智能原理2003年一、敘述圖搜索算法GRAPHSEARCH過程；設(shè)八數(shù)碼問題有兩個估價函數(shù)：fi(n)=d(n)+W(n)； f2(n)=d(n)+P(n)+3S(n)。其中d(n)是節(jié)點n在搜索樹中的深度，W(n)是節(jié)點n中“不在位”數(shù)碼的個數(shù)，P(n

4、)是每 個數(shù)碼離開目標位置的距離的和。S(n)是由如下方式得到的序列分：對于非中心的外圈上的數(shù)碼沿順時針方向走 一圈，如果一個數(shù)碼后面的數(shù)碼不是它在目標狀態(tài)下的后繼者，則給這個數(shù)碼記2分，否則記0分；對于中心位 置，有數(shù)碼的記1分，沒有的話記0分。然后把所有上述得分加起來，就得到序列分S(n)?，F(xiàn)有初始狀態(tài)和目標 狀態(tài)描述如下：請畫出各自的啟發(fā)式搜索過程圖，在圖中標明各節(jié)點的估價函數(shù)值，并標明節(jié)點擴展的次序。計 算出各自的滲透度和有效分枝系數(shù)。(40分)3452 I 1 I 7初始狀態(tài)1 I 8 | 7目標狀態(tài)二、總結(jié)博弈搜索的極小極大過程和a -p過程，并以下述博弈樹為例，給出兩個過程的各節(jié)

5、點返回值和搜索到 的路徑(請畫出兩個過程圖)。對于其中的a -p過程以優(yōu)先產(chǎn)生左邊子節(jié)點的次序進行a -p剪枝，指出在何處 發(fā)生剪枝、何處為a修剪、何處為p修剪？標明發(fā)生剪枝的節(jié)點和初始節(jié)點返回值的變化。圖中表示極大點， 。表示極小點。(20分)3-30-1-201451-1-1332-2三、(27分)1、設(shè)子句集S = P (x), Q (f (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

6、(x) T Q (x), Vy (Q (y) T R (y), 3z( R (z)共同蘊含 3 u ( P (u)。四、設(shè)S是命題邏輯子句集，P是S中出現(xiàn)的一個原子符號，于是可將S中子句分為三部分：含有文字P的部分S = C v P,., C v P，含有文字P的部分S = B v P,., B v P，和不含文字P 或P的部分S。令 11n21m3S = C，C uS，S = B ,., B u S，請證明S是不可滿足的當且僅當S1，S2 都是不可滿足的。(8 11n 321m3分)五、請舉出基于規(guī)則的正向演繹系統(tǒng)不完備的例子。(5分)By W01F STUDIO 人工智能原理2002年一、

7、簡要回答下列問題(24分)1、以八數(shù)碼問題為例，說明產(chǎn)生式系統(tǒng)的基本組成。2、什么叫A*算法？ A*算法的主要性質(zhì)是什么？3、在基于規(guī)則的演繹系統(tǒng)中，什么是合一復(fù)合替換？為什么要考慮替換的相容性？4、在基于規(guī)則的正向演繹系統(tǒng)中，規(guī)則和目標各要求怎樣的形式？5、基于規(guī)則的正向演繹系統(tǒng)是否完備？反向演繹是否完備？雙向演繹是否完備？6、在啟發(fā)式搜索中，估價函數(shù)一般定義為f(n)=g(n)+h(n)，指明定義中各部分的含義，并說明為什么使用這種 定義方式。7、在合一算法中，設(shè)W是非空表達式集合，D是W的差異集合，則當D具有怎樣的形式時，W是不可合一的？8、常用的知識表示方法有哪幾種，簡要回答各自的特點

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

9、, b/y, y/z,入=a/x, z/y, f(x)/z,求 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ī) 則隨機排序。四、使用歸結(jié)方法證明下述子句集是不可滿足的(寫出整個歸結(jié)過程和每一步歸結(jié)使用的合一替換)。S = A(a, f (c), f (b), B (a), A(x, x, f (x), 口 A(x, y, z) v C (x, z), 口

10、B (x) v 口 A(y, z, u) 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ī)則為:ab，c m，gh，ac，de，hi，ad，ef，mi，bg，fm狀態(tài)abcdefghimh值11822244104狀態(tài)abcdefghimh值11822244104設(shè)a為初始狀態(tài)，規(guī)則應(yīng)用費用為1，各狀態(tài)的啟發(fā)函數(shù)值為:用A算法畫出節(jié)點c擴展前與擴展后的搜索圖與搜索樹，要求標出圖中節(jié)點的擴展次序、 點c擴展前CLOSED表與OPEN表中的元

11、素。(15分)估價函數(shù)值，寫出節(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)2211221 F F請構(gòu)造S對應(yīng)與I的H解釋I*。(15分)人工智能原理2002年七、對下面的博弈樹以優(yōu)先產(chǎn)生左邊子節(jié)點的次序進行a -8剪枝，指出在何處發(fā)生剪枝、何處為a修剪、何處 為8修剪？標明發(fā)生剪枝的節(jié)點和初始節(jié)點返回值的變化，以及搜索到的路徑。圖中表示極大點，。表示極小 點。說明一般的a -8剪枝過程中，什么情況下

12、效率最高。（10分）-1332-23-30-1-201451-1人工智能原理2000年一、簡要回答下列問題(24分)1、請敘述產(chǎn)生式系統(tǒng)的過程。2、回答產(chǎn)生式系統(tǒng)的分類，并說明各自的優(yōu)缺點。3、敘述什么樣的產(chǎn)生式系統(tǒng)是可交換的產(chǎn)生式系統(tǒng)。4、說明無信息的圖搜索過程與啟發(fā)式圖搜索過程的差異，并舉出兩種典型的無信息圖搜索方法。5、敘述一階邏輯解釋的定義。6、在語義上證明子句集恒假時，僅考慮該子句集的Herbrand解釋是否夠用？為什么？7、在基于規(guī)則的演繹系統(tǒng)中，什么是合一復(fù)合替換？為什么要考慮替換的相容性？8、機器學(xué)習(xí)一般分為哪幾種類型？二、設(shè)八數(shù)碼問題有估價函數(shù)：f(n)=d(n)+W(n)；

13、其中d(n)是節(jié)點n在搜索樹中的深度，W(n)是節(jié)點n中“不在 位”數(shù)碼的個數(shù)?，F(xiàn)有初始狀態(tài)描述和目標狀態(tài)描述如下：初始狀態(tài)目標狀態(tài)請畫出啟發(fā)式搜索過程圖，在圖中標明各節(jié)點的估價函數(shù)值，并標明節(jié)點擴展的次序。(20分)、試用表推演方法證明(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*算法終止前的

14、任何時刻OPEN表中總存在節(jié)點n，n在 最佳解路徑上，滿足f(n)Wf*(s)，其中s為初始節(jié)點。(15分)六、在歸結(jié)推理方法中，若不取因子而僅使用二元歸結(jié)式是不完備的，請舉出一個反例。(5分)人工智能原理xxxx年一、回答下列問題(20分)1、什么是可交換產(chǎn)生式系統(tǒng)？2、影響A算法啟發(fā)能力的因素有哪些？3、敘述a -8過程的剪枝規(guī)則。4、歸結(jié)原理有哪幾種重要的改進？5、描述基于規(guī)則的正向演繹系統(tǒng)的初始狀態(tài)、規(guī)則和目標的一般形式。二、請用估價函數(shù)：f(n)=d(n)+W(n)求解八數(shù)碼問題，其中d(n)是節(jié)點n在搜索樹中的深度，W(n)是節(jié)點n中“不 在位”數(shù)碼的個數(shù)。n1nn%n6七nh(n

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

16、問題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ù)碼難題的初始狀態(tài)和目標狀態(tài)為:n1nn%n6七%h(n)024411200n4初始狀態(tài)目標狀態(tài)設(shè)估價函數(shù)：f(n)=d(n)+W(n)，其中d(n)是

17、節(jié)點n在搜索樹中的深度，W(n)是節(jié)點n中“不在位”數(shù)碼的個數(shù)。畫出使用此函數(shù)A算法解題的搜索樹，在樹上標明各節(jié)點的估價函數(shù)值及選擇擴展節(jié)點的次序。四、已知與/或圖，其中n0是初始節(jié)點，n7 %是目標節(jié)點集，h是啟發(fā)函數(shù)，并假定k-連接符的費用是k。請 用A。算法求解其最優(yōu)解圖。n0n8n3n5n7 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)缺點。3、影響A算法啟發(fā)能力的要素有哪些？4、一階邏輯中，公式是怎樣定義的？5、一階邏輯中，公式的解釋是怎樣定義的?6、命題邏輯中，常用哪兩種公式范式？7、一階邏輯中，常用哪兩種公式范式？8、什么叫子句集的Herbrand域？、試述圖搜索算法GRAPHSEARCH。三、已知八數(shù)碼難題的初始狀態(tài)和目標狀態(tài)為:初始狀態(tài)目標狀態(tài)設(shè)估價函數(shù)：f(n)=d(n)+W(n)，其中d(n)是節(jié)點n在搜索樹中的深度，W(n)是節(jié)點n中“不在位”數(shù)碼的個數(shù)。畫出使用此函數(shù)A算法解題的搜索樹，在樹