人工智能交大題目及答案（精編版）

1、. . 1 / 8 人工智能導論全真試題一、 判斷題（在單項選擇框選擇）1、只有在單位耗散值的情況下，當問題有解時，寬度優(yōu)先算法才能保證找到最優(yōu)解。2、在 a*算法完畢之前， open 表中任何滿足 f(n)f*(s)的節(jié)點 n，一定被擴展。3、設有機器人走迷宮問題，其入口坐標為(x0, y0) ，出口坐標為 (xt, yt)，當前機器人位置為(x, y)，若定義， 當從入口到出口存在通路時，用a算法求解該問題，定能找到從入口到出口的最正確路徑。4、在 a算法中，滿足單調條件的h 必然滿足 a*算法的條件。5、比起極小 - 極大法來，- 剪枝法增大了找不到最正確走步的危險性，但其效率較高。二、

2、 填空題（在橫線上作答）1、基于規(guī)則的正向演繹系統(tǒng)使用的條件是（1）事實表達式是（2）規(guī)則形式為， 其中（3） 目標公式為2、基于規(guī)則的逆向演繹系統(tǒng)使用的條件是（1）事實表達式是（2）規(guī)則形式為， 其中（3）目標公式為3、歸結法中，可以通過的方法得到問題的解答。三、 問答題（在每題下面的空白框上作答）1、某問題狀態(tài)圖如右圖所示。假定k 連接符的耗散值為k。 各節(jié)點的 h 值假定為：h(a)=3, h(b)=2, h(c)=6, h(d)=3, h(e)=4, h(f)=2, h(g)=3, h(h)=h(i)=0 (目標節(jié)點 ) 用 ao* 算法求解該問題，給出每次循環(huán)后的搜索圖，并給出求得的

3、解圖。. . 2 / 8 3、有四人過河，只有一條船，最多可乘坐兩人。若單個過，各需1，1，5，9分鐘，若兩人一起過， 則需要的時間以多的為準 （如需要 5 分和 9 分的兩人同時乘坐，則需要 9 分）。問最少需要多少分鐘。(1) 、用產(chǎn)生式系統(tǒng)描述該問題，要求給出綜合數(shù)據(jù)庫的定義，規(guī)則集，初始狀態(tài)和完畢狀態(tài)。(2) 、定義一個 h 函數(shù)，并說明是否滿足a*條件。(3) 、用 a算法求解該問題，給出狀態(tài)搜索圖，標出擴展次序、各節(jié)點的f值、解路徑與解路徑的耗散值。4、某問題由以下公式描述：(1) 、（ s）p（s）(2) 、（s）（p（g（s）(3) 、（ x）（s）（ y）（ p（s）q （b

4、，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)成立。要求給出一個求得的一致解圖，并說明為什么它是一致的；給出目標的解答。5、簡述為什么修正的a*算法有可能會減少重復節(jié)點的擴展，而又不會比 a*多擴展節(jié)點。6、給 19 九個數(shù)字排一個序列，使得該序列的前n(n=1,.,9) 個數(shù)字組成的整數(shù)能被 n 整除。(1) 、討論哪些知識可以幫助該問題的求解。(2) 、用產(chǎn)生式系統(tǒng)描述該問題。( 給出綜合數(shù)據(jù)庫，規(guī)則集，上述知識要在規(guī)則集中

5、反映出來 ) . . 3 / 8 7、某問題的狀態(tài)空間圖如以下圖所示，其中括號標明的是各節(jié)點的h 值，弧線邊的數(shù)字是該弧線的耗散值， 試用 a算法求解從初始節(jié)點s到目標節(jié)點 t的路徑。要求給出搜索圖， 標明各節(jié)點的 f 值，與各節(jié)點的擴展次序， 并給出求得的解路徑。三、 問答題答案第 1 題答：. . 4 / 8 得解圖：. . 5 / 8 第 3 題答： 綜合數(shù)據(jù)庫：(m1, m5, m9, b) 設從河的左岸到右岸，其中m1, m5,m9分別表示過河時間需要 1 分鐘，5 分鐘和 9 分鐘的人，在河左岸的人數(shù)。 b1 表示船在左岸， b0表示船在右岸。規(guī)則集：初始狀態(tài)：(2, 1, 1,

6、1) 完畢狀態(tài)(0, 0, 0, 0) h 函數(shù)：h(n) = m - b，其中 m為在左岸的人數(shù)， b 為船是否在左岸。對于任意兩個節(jié)點ni 和 nj ，其中 nj 是 ni 的子節(jié)點。當 ni 中 b1 時，則 nj 中 b0，因此： max(h(ni)-h(j)=(m-1)-(m-1)=0, 而c(ni, nj)最小為 1，因此 h(ni)-h(nj)c(ni, nj); 當 ni 中 b0 時，則 nj 中 b1，因此：max(h(ni)-h(j)=m-m=0, 而 c(ni, nj). . 6 / 8 最小為 1，因此 h(ni)-h(nj)c(ni, nj)。而對于目標節(jié)點 t ，

7、h(t)=0 。因此該 h 函數(shù)滿足單調性條件。所以h 滿足 a*條件。第 4 題答： 對事實和規(guī)則進行 skolem 化：（1）( 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(s

8、2)r2: q(b ，x3，s3)q(b，x3，g(s3) r3: p(s4)q(b，x4，h(x4, s4) 用對偶形式對目標skolem 化：( x)h(x) h(x) 演繹圖如以下圖 (這里只給出了一個一致解圖) 。. . 7 / 8 由置換集構造 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(g(h(c, a)/x, g(h(c, a)/s2, c/x3, h(c, a)/s3, c/x4,

9、 h(c, a)/s1, a/s4 將該合一復合帶入目標中，得到解答：x = f(g(h(c, a) 第 5 題答：1、 由于修正的 a*算法對與 open 表中 f 值小于 fm的節(jié)點按照 g 值的大小排序，優(yōu)先擴展 g 值小的節(jié)點。對于這部分節(jié)點來說，相當于h0。而 h0 滿足單調條件，因此至少對于這部分節(jié)點來說，減少了重復擴展節(jié)點的可能性。因此修正的 a*算法有可能減少重復節(jié)點的擴展。. . 8 / 8 2、由于 a*擴展的節(jié)點， 其 f 值總是小于等于 f*(s)，而 fm 是到目標為止擴展過的節(jié)點的最大 f 值， 因此必有 fm小于等于 f*(s)。 又由于 open 表中 f 值小

10、于 f*(s)的節(jié)點，總是被 a*擴展的，因此從open 表中選擇那些 f 值小于 fm 的節(jié)點（這些節(jié)點的 f 值也必然小于 f*(s)），按照 g 值的大小優(yōu)先擴展，只是改變了部分節(jié)點的擴展次序，不會多擴展節(jié)點第 6 題答：如下的知識可以幫助求解該問題：（1）序列中，偶數(shù)在偶數(shù)位置，奇數(shù)在奇數(shù)位置；（2）第五個數(shù)為 5。綜合數(shù)據(jù)庫：用一個 1 到 9 的序列表示： n = x ，其中 x 為 1 到 9 的數(shù)字之一。規(guī)則集：r1: if len(n)=4 then x5 r2: if len(n)為偶數(shù) and n=in(1, 3, 7, 9) then xn r3: if len(n)為奇數(shù) and n=in(2, 4, 6,