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

人工智能原理2004年一、回答下列問題(30分)1、什么叫寬度優(yōu)先搜索？寬度優(yōu)先搜索的優(yōu)點(diǎn)在何處？缺點(diǎn)在何處？2、試說明邏輯符號(hào)“ n ”、"”的含義和差別。3、請(qǐng)舉出輸入歸結(jié)演繹不完備的例子。4、設(shè)S=P(x),Q(f(a)是子句集，請(qǐng)舉出I是S的普通解釋，而不是其Herbrand解釋的例子。5、請(qǐng)舉出公式與其Skolem范式不等價(jià)的例子。6、什么叫A算法？什么叫A*算法？什么叫A*算法是可采納的？?jī)蓚€(gè)A*算法如何比較好壞？ 二、求解下列問題(30分)1、設(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ù)；試給出以下面為初始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的圖搜索過程，指明各節(jié)點(diǎn)估價(jià)函數(shù)值和整體解路徑，并計(jì)算 該搜索過程的滲透度是多少？有效分枝系數(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)證明下面問題：已知事實(shí)A v B ;規(guī)則兩條A T C a D，B T E a 6;目標(biāo)C v G。畫出演繹過程與/或圖。三、證明第一種形式的Herbrand定理：設(shè)S是子句集，則S是不可滿足的，當(dāng)且僅當(dāng)對(duì)應(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分)30 -3-1-2014125-11-1-13-3236-2五、什么叫支架集歸結(jié)演繹，試證明基子句集支架集歸結(jié)演繹的完備性。(10分)人工智能原理2003年一、敘述圖搜索算法GRAPHSEARCH過程；設(shè)八數(shù)碼問題有兩個(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)是由如下方式得到的序列分：對(duì)于非中心的外圈上的數(shù)碼沿順時(shí)針方向走 一圈，如果一個(gè)數(shù)碼后面的數(shù)碼不是它在目標(biāo)狀態(tài)下的后繼者，則給這個(gè)數(shù)碼記2分，否則記0分；對(duì)于中心位 置，有數(shù)碼的記1分，沒有的話記0分。然后把所有上述得分加起來，就得到序列分S(n)?，F(xiàn)有初始狀態(tài)和目標(biāo) 狀態(tài)描述如下：請(qǐng)畫出各自的啟發(fā)式搜索過程圖，在圖中標(biāo)明各節(jié)點(diǎn)的估價(jià)函數(shù)值，并標(biāo)明節(jié)點(diǎn)擴(kuò)展的次序。計(jì) 算出各自的滲透度和有效分枝系數(shù)。(40分)3452 I 1 I 7初始狀態(tài)1 I 8 | 7目標(biāo)狀態(tài)二、總結(jié)博弈搜索的極小極大過程和a -p過程，并以下述博弈樹為例，給出兩個(gè)過程的各節(jié)點(diǎn)返回值和搜索到 的路徑(請(qǐng)畫出兩個(gè)過程圖)。對(duì)于其中的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-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、使用合一算法判斷表達(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è)原子符號(hào)，于是可將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，請(qǐng)證明S是不可滿足的當(dāng)且僅當(dāng)S1，S2 都是不可滿足的。(8 11n 321m3分)五、請(qǐng)舉出基于規(guī)則的正向演繹系統(tǒng)不完備的例子。(5分)By W01F STUDIO 人工智能原理2002年一、簡(jiǎn)要回答下列問題(24分)1、以八數(shù)碼問題為例，說明產(chǎn)生式系統(tǒng)的基本組成。2、什么叫A*算法？ A*算法的主要性質(zhì)是什么？3、在基于規(guī)則的演繹系統(tǒng)中，什么是合一復(fù)合替換？為什么要考慮替換的相容性？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、常用的知識(shí)表示方法有哪幾種，簡(jiǎn)要回答各自的特點(diǎn)。二、判斷對(duì)錯(cuò)(14分)1、OPEN表上任一具有f(n) Wf*(s)的點(diǎn)，最終都將被A*算法選作擴(kuò)展的節(jié)點(diǎn)。2、若滿足單調(diào)限制，則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)對(duì)每一個(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,求 Ee, Ex, Ee .入2、使用回溯搜索策略求解四皇后問題。其中規(guī)則排序使用對(duì)角線函數(shù)diag(i, j)，若diag(i, j)Vdiag(m, n)，則在排 序中把規(guī)則放在規(guī)則Rmn的前面。diag (i, j)定義為用過單元(i, j)的最長(zhǎng)對(duì)角線的長(zhǎng)度。若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) 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)用費(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)2211221 F F請(qǐng)構(gòu)造S對(duì)應(yīng)與I的H解釋I*。(15分)人工智能原理2002年七、對(duì)下面的博弈樹以優(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分）-1332-23-30-1-201451-1人工智能原理2000年一、簡(jiǎn)要回答下列問題(24分)1、請(qǐng)敘述產(chǎn)生式系統(tǒng)的過程。2、回答產(chǎn)生式系統(tǒng)的分類，并說明各自的優(yōu)缺點(diǎn)。3、敘述什么樣的產(chǎn)生式系統(tǒng)是可交換的產(chǎn)生式系統(tǒng)。4、說明無信息的圖搜索過程與啟發(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)請(qǐng)畫出啟發(fā)式搜索過程圖，在圖中標(biāo)明各節(jié)點(diǎn)的估價(jià)函數(shù)值，并標(biāo)明節(jié)點(diǎn)擴(kuò)展的次序。(20分)、試用表推演方法證明(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分)五、欲對(duì)某一有解的圖搜索問題試用A*算法，試證明A*算法終止前的任何時(shí)刻OPEN表中總存在節(jié)點(diǎn)n，n在 最佳解路徑上，滿足f(n)Wf*(s)，其中s為初始節(jié)點(diǎn)。(15分)六、在歸結(jié)推理方法中，若不取因子而僅使用二元?dú)w結(jié)式是不完備的，請(qǐng)舉出一個(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)的一般形式。二、請(qǐng)用估價(jià)函數(shù)：f(n)=d(n)+W(n)求解八數(shù)碼問題，其中d(n)是節(jié)點(diǎn)n在搜索樹中的深度，W(n)是節(jié)點(diǎn)n中“不 在位”數(shù)碼的個(gè)數(shù)。n1nn°%n6七n§h(n)024411200n4初始狀態(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。請(qǐng)用Ab算法求解其最優(yōu)解圖。(20分) n0n8n3n5n7 *五、證明下述歸結(jié)方法的完備性定理：如果基子句集S是不可滿足的，則存在從S推出空子句的歸結(jié)演繹。(20 分)人工智能原理xxxx年A一、簡(jiǎn)要回答下列問題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)和目標(biāo)狀態(tài)為:n1nn°%n6七%h(n)024411200n4初始狀態(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。請(qǐng) 用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一、簡(jiǎn)要回答下列問題1、無信息的圖搜索方法主要有哪兩種？2、簡(jiǎn)述各種搜索策略各自的優(yōu)缺點(diǎn)。3、影響A算法啟發(fā)能力的要素有哪些？4、一階邏輯中，公式是怎樣定義的？5、一階邏輯中，公式的解釋是怎樣定義的?6、命題邏輯中，常用哪兩種公式范式？7、一階邏輯中，常用哪兩種公式范式？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)五、請(qǐng)用歸結(jié)方法證明子句集S = P v Q, P v Q, Pv Q, Pv Q是不可滿足的。六、請(qǐng)使用回溯搜索策略求解四皇后問題。其中規(guī)則排序使用對(duì)角線函數(shù)diag(i, j)，若diag(i, j)Vdiag(m, n)，則 在排序中把規(guī)則放在規(guī)則Rmn的前面。diag (i, j)定義為用過單元(i, j)的最長(zhǎng)對(duì)角線的長(zhǎng)度。