人工智能 模擬試卷.doc

人工智能導(dǎo)論試卷 一、 選擇1、比起極小 - 極大法來，-剪枝法增大了找不到最佳走步的危險(xiǎn)性，但其效率較高。 A 對 B 錯(cuò)2、在A算法中，滿足單調(diào)條件的h必然滿足A*算法的條件。 A 對 B 錯(cuò)3、設(shè)有機(jī)器人走迷宮問題，其入口坐標(biāo)為(x0, y0)，出口坐標(biāo)為(xt, yt)，當(dāng)前機(jī)器人位置為(x, y)，若定義， 當(dāng)從入口到出口存在通路時(shí)，用A算法求解該問題，定能找到從入口到出口的最佳路徑。 A 對 B 錯(cuò) 答案：B A A二、 填空題1、在修正的A算法中，fm的含義是2、對任意節(jié)點(diǎn)n，設(shè)m是n的子節(jié)點(diǎn)，當(dāng)h滿足條件時(shí)，稱h是單調(diào)的。 答案1、在修正的A算法中，fm的含義是 到當(dāng)前為止，擴(kuò)展的節(jié)點(diǎn)中，f的最大值2、對任意節(jié)點(diǎn)n，設(shè)m是n的子節(jié)點(diǎn)，當(dāng)h滿足條件 h(n)-h(m) C(n, m), h(t) = 0 時(shí)，稱h是單調(diào)的。三、 問答題1、簡述用A*算法求解問題時(shí)為什么會(huì)出現(xiàn)重復(fù)擴(kuò)展節(jié)點(diǎn)問題，解決的方法有哪些？2、簡述回溯策略與深度優(yōu)先策略的不同點(diǎn)。3、某問題由下列公式描述：(1)、試用歸結(jié)法證明(x)R(x)；(2)、做出修改證明樹，提取問題的回答。 4、下圖所示博弈樹，按從左到右的順序進(jìn)行-剪枝搜索，試標(biāo)明各生成節(jié)點(diǎn)的到推值，何處發(fā)生剪枝，及應(yīng)選擇的走步。5、某問題的狀態(tài)空間圖如下圖所示，其中括號(hào)內(nèi)標(biāo)明的是各節(jié)點(diǎn)的h值，弧線邊的數(shù)字是該弧線的耗散值，試用A算法求解從初始節(jié)點(diǎn)S到目標(biāo)節(jié)點(diǎn)T的路徑。要求給出搜索圖，標(biāo)明各節(jié)點(diǎn)的f值，及各節(jié)點(diǎn)的擴(kuò)展次序，并給出求得的解路徑。 6、給19九個(gè)數(shù)字排一個(gè)序列，使得該序列的前n(n=1,.,9) 個(gè)數(shù)字組成的整數(shù)能被n整除。(1)、討論哪些知識(shí)可以幫助該問題的求解。(2)、用產(chǎn)生式系統(tǒng)描述該問題。(給出綜合數(shù)據(jù)庫，規(guī)則集，上述 知識(shí)要在規(guī)則集中反映出來) 問答題答案第1題答：當(dāng)問題有解時(shí)，A*算法總是找到問題的最優(yōu)解結(jié)束。如果h函數(shù)定義的不合理，則當(dāng)擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)，不一定就找到了從初始節(jié)點(diǎn)到該節(jié)點(diǎn)的最優(yōu)路徑，對于這樣的節(jié)點(diǎn)，就有可能被多次擴(kuò)展。特別是如果這樣的節(jié)點(diǎn)處于問題的最優(yōu)解路徑上時(shí)，則一定會(huì)被多次擴(kuò)展。解決的方法一是對h函數(shù)的定義給出限制，使得h滿足單調(diào)性。對于滿足單調(diào)性條件的h，則一定不會(huì)出現(xiàn)重復(fù)擴(kuò)展節(jié)點(diǎn)問題。二是對A*算法加以改進(jìn)，使用修正的A*算法進(jìn)行搜索，則可以減少重復(fù)擴(kuò)展節(jié)點(diǎn)問題。第2題答：回溯搜索策略與深度有限搜索策略最大的不同是深度有限搜索策略屬于圖搜索，而回溯搜索則不是圖搜索。在回溯搜索中，只保留了從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的搜索路徑。而深度優(yōu)先搜索，則保留了所有的已經(jīng)搜索過的路徑。第3題答： 化子句集如下：歸結(jié)樹如下： 修改證明樹：得到問題的解答：R(h(f(g(c, a)第4題第5題答：搜索圖如圖所示，其中括號(hào)內(nèi)標(biāo)出的是節(jié)點(diǎn)的f值，圓圈內(nèi)的數(shù)字是擴(kuò)展的次序。F(16)得到的解路徑為：S-B-F-J-T第6題答：如下的知識(shí)可以幫助求解該問題：（1）序列中，偶數(shù)在偶數(shù)位置，奇數(shù)在奇數(shù)位置；（2）第五個(gè)數(shù)為5。綜合數(shù)據(jù)庫：用一個(gè)1到9的序列表示：N = x，其中x為1到9的數(shù)字之一。規(guī)則集：r1: IF len(N)=4 THEN x5r2: IF len(N)為偶數(shù)and n=In(1, 3, 7, 9) THEN xnr3: IF len(N)為奇數(shù)and n=In(2, 4, 6, 8) THEN x