1樓：匿名使用者
人工智慧原理 2023年
一、回答下列問題（30分）
1、什麼叫寬度優先搜尋？寬度優先搜尋的優點在何處？缺點在何處？
2、試說明邏輯符號「 」、「→」的含義和差別。
3、請舉出輸入歸結演繹不完備的例子。
4、設s=是子句集，請舉出i是s的普通解釋，而不是其herbrand解釋的例子。
5、請舉出公式與其skolem正規化不等價的例子。
6、什麼叫a演算法？什麼叫a*演算法？什麼叫a*演算法是可採納的？兩個a*演算法如何比較好壞？
二、求解下列問題（30分）
1、設八數碼問題有估價函式：f(n)=d(n)+w(n)；其中d(n)是節點n在搜尋樹中的深度，w(n)是節點n中「不在位」數碼的個數；試給出以下面為初始節點和目標節點的圖搜尋過程，指明各節點估價函式值和整體解路徑，並計算該搜尋過程的滲透度是多少？有效分枝係數是多少？
3 4 5
2 6
1 8 7
3 4 5
8 62 1 7
2、將公式g化為skolem正規化，並給出g的子句集s。
3、使用基於規則的正向演繹系統證明下面問題：
已知事實 ；規則兩條 ， ；目標 。畫出演繹過程與/或圖。
三、證明第一種形式的herbrand定理：設s是子句集，則s是不可滿足的，當且僅當對應於s的每乙個完全語義樹都存在乙個有限的封閉語義樹。（15分）
四、總結α-β過程，並以下述博弈樹為例，以優先產生左邊子節點的次序進行α-β剪枝，指出在何處發生剪枝、何處為α修剪、何處為β修剪？標明發生剪枝的節點和初始節點返回值的變化。圖中□表示極大點，○表示極小點。
（15分）
五、什麼叫支架集歸結演繹，試證明基子句集支架集歸結演繹的完備性。（10分）
人工智慧原理 2023年
一、敘述圖搜尋演算法graphsearch過程；設八數碼問題有兩個估價函式：f1(n)=d(n)+w(n)；f2(n)=d(n)+p(n)+3s(n)。其中d(n)是節點n在搜尋樹中的深度，w(n)是節點n中「不在位」數碼的個數，p(n)是每個數碼離開目標位置的距離的和。
s(n)是由如下方式得到的序列分：對於非中心的外圈上的數碼沿順時針方向走一圈，如果乙個數碼後面的數碼不是它在目標狀態下的後繼者，則給這個數碼記2分，否則記0分；對於中心位置，有數碼的記1分，沒有的話記0分。然後把所有上述得分加起來，就得到序列分s(n)。
現有初始狀態和目標狀態描述如下：請畫出各自的啟發式搜尋過程圖，在圖中標明各節點的估價函式值，並標明節點擴充套件的次序。計算出各自的滲透度和有效分枝係數。
（40分）
3 4 5
2 6
1 8 7
3 4 5
8 62 1 7
二、總結博弈搜尋的極小極大過程和α-β過程，並以下述博弈樹為例，給出兩個過程的各節點返回值和搜尋到的路徑（請畫出兩個過程圖）。對於其中的α-β過程以優先產生左邊子節點的次序進行α-β剪枝，指出在何處發生剪枝、何處為α修剪、何處為β修剪？標明發生剪枝的節點和初始節點返回值的變化。
圖中□表示極大點，○表示極小點。（20分）
三、（27分）
1、設子句集 ，求s的h域，s的原子集，子句 的基例集合。
2、使用合一演算法判斷表示式集合w=是否可合一，若可合一，則求出最一般合一。
3、試用表推演方法證明 共同蘊含 。
四、設s是命題邏輯子句集，p是s中出現的乙個原子符號，於是可將s中子句分為三部分：含有文字p的部分 ，含有文字～p的部分 ，和不含文字p或~p的部分s3。令 ， ，請證明s是不可滿足的當且僅當s1』 , s2』 都是不可滿足的。
（8分）
五、請舉出基於規則的正向演繹系統不完備的例子。（5分）
人工智慧原理 2023年
一、簡要回答下列問題（24分）
1、以八數碼問題為例，說明產生式系統的基本組成。
2、什麼叫a*演算法？a*演算法的主要性質是什麼？
3、在基於規則的演繹系統中，什麼是合一復合替換？為什麼要考慮替換的相容性？
4、在基於規則的正向演繹系統中，規則和目標各要求怎樣的形式？
5、基於規則的正向演繹系統是否完備？反向演繹是否完備？雙向演繹是否完備？
6、在啟發式搜尋中，估價函式一般定義為f(n)＝g(n)＋h(n)，指明定義中各部分的含義，並說明為什麼使用這種定義方式。
7、在合一演算法中，設w是非空表示式集合，d是w的差異集合，則當d具有怎樣的形式時，w是不可合一的？
8、常用的知識表示方法有哪幾種，簡要回答各自的特點。
二、判斷對錯（14分）
1、open表上任一具有f(n)≤f*(s)的點，最終都將被a*演算法選作擴充套件的節點。
2、若滿足單調限制，則a*演算法所擴充套件的節點序列的f值是單調遞增的。
3、設θ，λ是兩個替換，則θ•λ=λ•θ。
4、表示式集合w=是可合一的。
5、滲透度和有效分枝係數都是關於圖搜尋方法啟發能力的空間複雜性度量標準。
6、子句集s恆假，當且僅當對每乙個解釋i，使s中的每個子句c的基例c』被i弄假。
7、一階邏輯中任一公式是否是恆假的，可用歸結方法判定。
三、（12分）
1、若e=q(y, f(y, g(x))), θ=,λ=, 求eθ, eλ, eθ•λ
2、使用回溯搜尋策略求解四皇后問題。其中規則排序使用對角線函式diag(i, j)，若diag(i, j)＜diag(m, n)，則在排序中把規則rij放在規則rmn的前面。diag (i, j)定義為用過單元(i, j)的最長對角線的長度。
若diag函式值相同則規則隨機排序。
四、使用歸結方法證明下述子句集是不可滿足的（寫出整個歸結過程和每一步歸結使用的合一替換）。
（10分）
五、設產生式系統ps，其狀態集合db=，產生式規則為：
a→b，c→m，g→h，a→c，d→e，h→i，a→d，e→f，m→i，b→g，f→m
設a為初始狀態，規則應用費用為1，各狀態的啟發函式值為：
狀態 a b c d e f g h i m
h值 1 1 8 2 2 2 4 4 10 4
用a演算法畫出節點c擴充套件前與擴充套件後的搜尋圖與搜尋樹，要求標出圖中節點的擴充套件次序、估價函式值，寫出節點c擴充套件前closed表與open表中的元素。（15分）
六、已知子句集s=，求s的原子集、s的語義樹。若給定s的乙個解釋i如下：
d= 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 t t
請構造s對應與i的h解釋i*。（15分）
人工智慧原理 2023年
七、對下面的博弈樹以優先產生左邊子節點的次序進行α-β剪枝，指出在何處發生剪枝、何處為α修剪、何處為β修剪？標明發生剪枝的節點和初始節點返回值的變化，以及搜尋到的路徑。圖中□表示極大點，○表示極小點。
說明一般的α-β剪枝過程中，什麼情況下效率最高。（10分）
人工智慧原理 2023年
一、簡要回答下列問題（24分）
1、請敘述產生式系統的過程。
2、回答產生式系統的分類，並說明各自的優缺點。
3、敘述什麼樣的產生式系統是可交換的產生式系統。
4、說明無資訊的圖搜尋過程與啟發式圖搜尋過程的差異，並舉出兩種典型的無資訊圖搜尋方法。
5、敘述一階邏輯解釋的定義。
6、在語義上證明子句集恆假時，僅考慮該子句集的herbrand解釋是否夠用？為什麼？
7、在基於規則的演繹系統中，什麼是合一復合替換？為什麼要考慮替換的相容性？
8、機器學習一般分為哪幾種型別？
二、設八數碼問題有估價函式：f(n)=d(n)+w(n)；其中d(n)是節點n在搜尋樹中的深度，w(n)是節點n中「不在位」數碼的個數。現有初始狀態描述和目標狀態描述如下：
3 4 5
2 6
1 8 7
3 4 5
8 6 7
2 1請畫出啟發式搜尋過程圖，在圖中標明各節點的估價函式值，並標明節點擴充套件的次序。（20分）
三、試用表推演方法證明 共同蘊含 。（16分）
四、敘述合一演算法，並用合一演算法求出w=的最一般合一。（寫出演算法的執行步驟，20分）
五、欲對某一有解的圖搜尋問題試用a*演算法，試證明a*演算法終止前的任何時刻open表中總存在節點n』，n』在最佳解路徑上，滿足f(n』)≤f*(s)，其中s為初始節點。（15分）
六、在歸結推理方法中，若不取因子而僅使用二元歸結式是不完備的，請舉出乙個反例。（5分）
人工智慧原理 ***x年
一、回答下列問題（20分）
1、什麼是可交換產生式系統？
2、影響a演算法啟發能力的因素有哪些？
3、敘述α-β過程的剪枝規則。
4、歸結原理有哪幾種重要的改進？
5、描述基於規則的正向演繹系統的初始狀態、規則和目標的一般形式。
二、請用估價函式：f(n)=d(n)+w(n) 求解八數碼問題，其中d(n)是節點n在搜尋樹中的深度，w(n)是節點n中「不在位」數碼的個數。
3 2 1
4 8
5 6 7
3 8 2
4 6 1
5 7
畫出啟發式搜尋過程圖，在圖中標明各節點的估價函式值，並標明節點擴充套件的次序。（20分）
三、敘述合一演算法，並用該演算法尋找表示式集w=的最一般合一。（20分）
四、使用ao*演算法，啟發函式應滿足什麼條件？下圖是已給出的與/或圖，其中n0是初始節點，是目標節點集，h是啟發函式，並假定k-連線符的費用是k。請用ao*演算法求解其最優解圖。
（20分）
n n0 n1 n2 n3 n4 n5 n6 n7 n8
h(n) 0 2 4 4 1 1 2 0 0
五、證明下述歸結方法的完備性定理：如果基子句集s是不可滿足的，則存在從s推出空子句的歸結演繹。（20分）
人工智慧原理 ***x年a
一、簡要回答下列問題
1、人工智慧的主要研究領域有哪些？
2、產生式系統由哪幾部分組成？各部分的作用是什麼？
3、產生式系統的控制策略有哪幾種方式？
4、什麼是深度優先搜尋？什麼是寬度優先搜尋？
5、什麼叫啟發資訊？它是如何使用的？
6、影響a演算法啟發能力的要素有哪些？
7、搜尋方法的啟發能力有哪幾種基本的度量方法？
8、什麼是從子句集s推出子句c的歸結演繹？
9、什麼是可交換產生式系統？
10、在歸結演繹中，什麼叫最一般的合一替換？
二、試述可分解產生式系統的基本過程。
三、已知八數碼難題的初始狀態和目標狀態為：
1 2 3
8 4
7 6 5
2 8 3
1 6 4
7 5設估價函式：f(n)=d(n)+w(n) ，其中d(n)是節點n在搜尋樹中的深度，w(n)是節點n中「不在位」數碼的個數。畫出使用此函式a演算法解題的搜尋樹，在樹上標明各節點的估價函式值及選擇擴充套件節點的次序。
四、已知與/或圖，其中n0是初始節點，是目標節點集，h是啟發函式，並假定k-連線符的費用是k。請用ao*演算法求解其最優解圖。
n n0 n1 n2 n3 n4 n5 n6 n7 n8
h(n) 0 2 4 4 1 1 2 0 0
五、試用歸結演繹證明公式 是公式集
的邏輯結果。
人工智慧原理 ***x年b
一、簡要回答下列問題
1、無資訊的圖搜尋方法主要有哪兩種？
2、簡述各種搜尋策略各自的優缺點。
3、影響a演算法啟發能力的要素有哪些？
4、一階邏輯中，公式是怎樣定義的？
5、一階邏輯中，公式的解釋是怎樣定義的？
6、命題邏輯中，常用哪兩種公式正規化？
7、一階邏輯中，常用哪兩種公式正規化？
8、什麼叫子句集的herbrand域？
二、試述圖搜尋演算法graphsearch。
三、已知八數碼難題的初始狀態和目標狀態為：
1 2 3
8 4
7 6 5
2 8 3
1 6 4
7 5設估價函式：f(n)=d(n)+w(n) ，其中d(n)是節點n在搜尋樹中的深度，w(n)是節點n中「不在位」數碼的個數。畫出使用此函式a演算法解題的搜尋樹，在樹上標明各節點的估價函式值及選擇擴充套件節點的次序。
四、寫出下述公式的skolem正規化：
五、請用歸結方法證明子句集 是不可滿足的。
六、請使用回溯搜尋策略求解四皇后問題。其中規則排序使用對角線函式diag(i, j)，若diag(i, j)＜diag(m, n)，則在排序中把規則rij放在規則rmn的前面。diag (i, j)定義為用過單元(i, j)的最長對角線的長度。