人工智能知識點歸納

1、人工智能的不同研究流派：符號主義/ 邏輯主義學(xué)派 - 符號智能；連接主義- 計算智能；行為主義 - 低級智能。人工智能的主要 研究領(lǐng)域（一）自動推理（二）專家系統(tǒng)（三）機器學(xué)習(xí)（四）自然語言理解（五）機器人學(xué)和智能控制（六）模式識別（七）基于模型的診斷產(chǎn)生式系統(tǒng) 是人工智能系統(tǒng)中常用的一種程序結(jié)構(gòu)，是一種知識表示系統(tǒng)。三部分組成 ：綜合數(shù)據(jù)庫 : 存放問題的狀態(tài)描述的數(shù)據(jù)結(jié)構(gòu) , 動態(tài)變化的 。產(chǎn)生式規(guī)則集、控制系統(tǒng)。/產(chǎn)生式規(guī)則集 /控制系統(tǒng)產(chǎn)生式規(guī)則形式：IF前提條件THEN 操作八數(shù)碼難題的產(chǎn)生式系統(tǒng)表示綜合數(shù)據(jù)庫：以狀態(tài)為節(jié)點的有向圖。狀態(tài)描述： 3×3矩陣產(chǎn)生式規(guī)則：IF&

2、lt; 空格不在最左邊 >Then<左移空格 >；依次控制系統(tǒng)：選擇規(guī)則 : 按左、上、右、下的順序移動空格。終止條件：匹配成功。產(chǎn)生式系統(tǒng)的基本過程 : Procedure PROCUCTION1. DATA初始狀態(tài)描述2. until DATA 滿足終止條件， do：3. begin4. 在規(guī)則集合中，選出一條可用于DATA的規(guī)則 R（步驟 4 是不確定的，只要求選出一條可用的規(guī)則 R，至于這條規(guī)則如何選取，卻沒有具體說明。）5. DATA把 R應(yīng)用于 DATA所得的結(jié)果6. End產(chǎn)生式系統(tǒng)的特點： 1. 模塊性強， 2. 產(chǎn)生式規(guī)則相互獨立， 3. 規(guī)則的形式與邏輯推

3、理相近，易懂。產(chǎn)生式系統(tǒng)的控制策略 ：1. 不可撤回的控制策略：優(yōu)點是空間復(fù)雜度小、速度快；缺點是多數(shù)情況找不到解 2. 試探性控制策略：回溯方式：占用空間小，多數(shù)情況下能找到解；缺點是如果深度限制太低就找不到解；和圖搜索方式：優(yōu)點總能找到解，缺點時間空間復(fù)雜度高。產(chǎn)生式系統(tǒng)工作方式 ：正向、反向和雙向產(chǎn)生式系統(tǒng)可交換產(chǎn)生式系統(tǒng) ：1. 可應(yīng)用性，每一條對D可應(yīng)用的規(guī)則，對于對D應(yīng)用一條可應(yīng)用的規(guī)則后，所產(chǎn)生的狀態(tài)描述仍是可應(yīng)用的。2. 可滿足性，如果 D滿足目標條件，則對 D 應(yīng)用任何一條可應(yīng)用的規(guī)則所產(chǎn)生的狀態(tài)描述也滿足目標條件。 3. 無次序性，對 D應(yīng)用一個由可應(yīng)用于 D的規(guī)則所構(gòu)成的

4、規(guī)則序列所產(chǎn)生的狀態(tài)描述不因序列的次序不同而改變?？煞纸獾漠a(chǎn)生式系統(tǒng) ：能夠把產(chǎn)生式系統(tǒng)綜合數(shù)據(jù)庫的狀態(tài)描述分解為若干組成部分，產(chǎn)生式規(guī)則可以分別用在各組成部分上，并且整個系統(tǒng)的終止條件可以用在各組成部分的終止條件表示出來的產(chǎn)生式系統(tǒng)，稱為可分解的產(chǎn)生式系統(tǒng)。 基本過程 ：Procedure SPLIT1.DATA 初始狀態(tài)描述2.Di DATA的分解結(jié)果；每個 Di 看成是獨立的狀態(tài)描述3.until 對所有的 Di Di ， Di 都滿足終止條件， do:4.begin5. 在Di 中選擇一個不滿足終止條件的 D*6. 從Di 中刪除 D*7. 從規(guī)則集合中選出一個可應(yīng)用于 D*的規(guī)則R8

5、.D 把 R 應(yīng)用于 D*的結(jié)果9.di D 的分解結(jié)果10. 把di 加入 Di 中11.end回溯算法 BACKTRACK過程：Recursive Procedure BACKTRACK(DATA)1.if TERM(DATA),return NIL;2.if DEADEND(DATA),return FAIL;3.RULESAPPRULES(DATA);4.LOOP:if NULL(RULES),return FAIL;5.RFIRST(RULES);6.RULESTAIL(RULES);7.RDATAR（DATA）;8.PATHBACKTRACK(RDATA);9if PATH=FAI

6、L,go PATH;10.return CONS(R,PATH).Procedure GRAPHSEARCH1Gs ， OPEN （ s）2CLOSEDNIL 3 LOOP：IF OPEN=NIL,THEN FAIL4 n FIRST(OPEN)，OPEN TAIL(OPEN),CONS(n, CLOSED)5 IF TERM(n) ，THEN成功結(jié)束（解路徑可通過追溯 G中從 n 到s 的指針獲得）。6 擴展節(jié)點 n，令 M=m m 是 n 的子節(jié)點，且 m不是 n 的祖先 ， G G M 7 （設(shè)置指針，調(diào)整指針）對于 m M,(1) 若 m CLOSED, m OPEN, 建立 m 到

7、n 的指針，并 CONS(m, OPEN).(2)(a)mOPEN, 考慮是否修改 m的指針 .CLOSED,考慮是否修改 m(b)m及在 G中后裔的指針。8 重排 OPEN表中的節(jié)點（按某一任意確定的方式或者根據(jù)探索信息）。9 GO LOOP無信息的圖搜索過程：深度優(yōu)先搜索 ：排列OPEN表中的節(jié)點時按它們在搜索樹中的深度遞減排序 。深度最大的節(jié)點放在表的前面，F(xiàn)H=FH深度相等的節(jié)點以任意方式排序。 寬度優(yōu)先搜索：在排列 OPEN表中節(jié)點時按它們在搜索圖中的深度遞增順序，深度最小的節(jié)點放在表的前面。A算法 :使用估價函數(shù) f(n)=g(n)+h(n)排列 OPEN表中節(jié)點順序的 GRAPH

8、SEARCH算法。其中， g(n) ：對 g*(n) 的一個估計 是當前的搜索圖 G中 s 到 n 的最優(yōu)路徑費用 g(n) g*(n)h(n)：對h*(n) 的估計，稱為啟發(fā)函數(shù)。（ Note: 若 h(n)=0 ，g(n)=d ，則 f(n)=d ，為寬度優(yōu)先）。A*算法 : 對任何節(jié)點 n 都有 h(n) h*(n) 的 A算法。定義：如果一個搜索算法對于任何具有解路徑的圖都能找到一條最佳路徑，則稱此算法為可采納的?？梢宰C明： A*算法是可采納的（如果解路徑存在， A*一定由于找到最佳解路徑而結(jié)束）A*算法的可采納性 ：定理 1 GRAPHSEARCH 對有限圖必然終止。定理 2 若存在

9、 s 到目標的路，則算法 A*終止前的任何時刻， OPEN 表中總存在一個節(jié)點 n， n 在從 s 到目標的最佳路徑上，且滿足 f(n ) f*(s)定理 3 若存在從 s 到目標的解路，則算法A*必終止。定理 4 算法 A*是可采納的（即如果解路徑存在， A*一定找到最佳解路徑而終止）定理 5算法 A*選擇的任意擴展點都有f(n) f*(s)數(shù)為 T，則 BB2 十 BL=T或 B（BL-1）/（ B-1）=T與/ 或圖是一種超圖在超圖中父親節(jié)點和一組后繼節(jié)點用超弧連接 超弧又叫 k-連接符k- 連接符 : 一個父節(jié)點指向一組 k 個有與關(guān)系的后繼節(jié)點，這樣一組弧線稱為一個 k- 連接符極小

10、極大原則： MAX節(jié)點在其 MIN子節(jié)點的倒推值中選 max；MIN節(jié)點在其MAX子節(jié)點的倒推值中選 min剪枝規(guī)則：（ 1）剪枝：如果一個MIN節(jié)點的 值小于或等于它的某一個MAX祖先節(jié)點的 值，則剪枝發(fā)生在該MIN節(jié)點之下：中止這個 MIN節(jié)點以下的搜索過程。這個 MIN節(jié)點最終的倒推值就確定為這個 值。（ 2）剪枝：如果一個 MAX節(jié)點的 值大于或者等于它的某一個 MIN祖先節(jié)點的 值，則剪枝發(fā)生在該 MAX節(jié)點之下中止這個 MAX節(jié)點以下的搜索過程。該 MAX節(jié)點的最終返回值可以置成它的 值ND=2(BD/2)-1 （D為偶數(shù)）ND=B(D+1)/2+B(D-1)/2-1 （D 為奇數(shù)

11、）D為深度， B 為平均后繼。定理 1 任意公式 G都等價于一個前束范式證明 通過如下四個步驟即可將公式 G化為前束范式步驟 1：使用基本等價式? H=(FH) (HF)F可采納的條件： 1. 與或圖有解圖， 2. 對圖中可將公式 G中的 ? 和刪去。所有節(jié)點 n 有 h(n) h*(n) ，3. 啟發(fā)函數(shù)滿足單調(diào)性。則 AO*必然終止并找出最佳解路步驟 2：使用 ( F)=F 和 De. Morgan 律徑。及引理 1，影響算法 A 啟發(fā)能力的三個重要因素：可將公式中所有否定號放（1）算法 A所找到的解路徑的費用。在原子之前。（2）算法 A在尋找這條解路徑的過程中所步驟 3：如果必要的話，則

12、將約束變量改名需要 擴展的節(jié)點數(shù)。步驟 4：使用引理 1 和引理 2 又將所有量詞（3）計算啟發(fā)函數(shù)所需要的計算量。都提到公式的最左邊。啟發(fā)能力的度量：滲透度 P = L / T其中，G= x y z u v wP(x,y,z,u,v,w)則用 a 代L 是算法發(fā)現(xiàn)的解路徑的長度，替 x，用 f(y ，z) 代替 u，用 g(y ，z，v) 代T 是算法在尋找這條解路徑期間所產(chǎn)生替 w，得公式 G的 Skolem 范式：的節(jié)點數(shù)（不包括初始節(jié)點，包括目標節(jié)點）yz vP(a,y,z,f(y,z),v,g(y,z,v)有效分枝系數(shù)是 B，則有 B B2 十 BL=T定理 2設(shè) S 是公式 G的子

13、句集于是， G或 B （BL-1 ）/ （B-1）=T是不可滿足的，當且僅當 S 是不可滿足的8 數(shù)碼啟發(fā)函數(shù) h(n)=P(n)+3S(n),p(n) 是每醫(yī)生騙子問題： S P(a), L(x,個硬紙片離開目標位置的和， S(n) 是如果一D(y) L(a,y), P(x) Q(y)個硬紙片后面的紙片不是它的目標后繼則記y),D(b),Q(b) 引理 1 設(shè) G是僅含有自由2，否則記 0，如果中心有硬紙片記 1，否則變量 x 的公式，記以 G（x）， H 是不含變量記 0，然后求和。x 的公式，于是有xG(x ) H滲透度，搜索算法的性能的度量： P = L /(1)x(G(x) H)=T

14、，L 是算法發(fā)現(xiàn)的解路徑的長度， T 是算法(1) x(G(x) H)=xG(x ) H在尋找這條解路徑期間所產(chǎn)生的節(jié)點數(shù)（不(2)x(G(x) H)=xG(x )H包括初始節(jié)點，包括目標節(jié)點） 。(2) x(G(x) H)= xG(x )H有效分枝數(shù) B，反映目標搜索的集中程度：(3)(xG(x)=x ( G(x )設(shè)搜索樹的深度是 L，算法所產(chǎn)生的總節(jié)點(4)(xG(x)=x ( G(x )引理 2 設(shè) H，G是兩個僅含有自由變量x 的公式，分別記以 H(x) ，G(x) ，于是有：(1)xG(x) x H(x)=x(G(x )H(x)(2)xG(x) x H(x)=x(G(x ) H(x

15、)(3)xG(x) x H(x)=xy (G(x )H(y)xG(x) x H(x)=xy (G(x ) H(y)(4)1)基本等價式G)；(GH)=(G H) (H2)(GH)=( G H)；(3)G G=G，G G=G；等冪律)G H=H G，G H=H G；(交換律 )4)5)G (H S)=(G H) S，G(H S)=(G H) S；(結(jié)合律 )G (G H)=G，G (GH)=G； (吸收律 )6)7)G (H S)=(G H) (G S)，(G(H S)=(G H) (G S)；分配律)8)G F=G，G T=G；(同一律 )9)G F=F，G T=T；(零一律 )10) (G

16、H)= G H，(De(G H)= G H。Morgan律)11) G G=T；G G=F（互補律）12) G=G（雙重否定律）將公式 xy（A(x)B(x,y)）( yC(y)zD(z)化為前束范式解：（ 1）消去 聯(lián)結(jié)詞。x y（A(x)B(x,y) ）(yC(y)zD(z)B(x,y)） （ yC(y)= x y（A(x)zD(z)（ 2）將公式中所有否定號 放在原子之前。 x y（A(x) B(x,y) ） （yC(y)zD(z)(yC(y)=x y(A(x)B(x,y)zD(z)（3）將約束變量改名 .xy(A(x)B(x,y)(yC(y)zD(z)=x y(A(x)B(x,y)(t

17、 C(t)zD(z)（4）將量詞提到整個公式前。x y(A(x)B(x,y)(t C(t)=zD(z)（ (A(x)B(x,y)C(t)x yt zD(z) ）= x y t z(A(x) C(t) D(z) ( B(x,y)C(t)D(z)用 a 代替 x，用 b 代替 y，用 f(t) 代替 z，得公式的 Skolem 范式：t(A(a) C(t)D(f(t)( B(a,b)C(t)D(f(t)例： 1) G=x(P(f(x)Q(x， f(a)2) H=x(P(x)Q(x，a)設(shè)解釋 I：D=2，3 ，a2f(2)f(3)32P(2)P(3)Q(2, 2)Q(2, 3)Q(3,2)Q(3,

18、 3)TTFTFT(P(f(2)Q(2，f(2)T (G)= TIIP(f(3) Q(3，f(2)3)= T I (P(3)Q(2，3)(P(2) Q(3，=(TT)(FT)=TTI (H)= T I (P(2)Q(2，2) P(3)Q(3，2)=FTTF=F（ Herbrand 域）設(shè) S 為子句集，令 H0是出現(xiàn)于子句集 S 的常量符號集。如果 S 中無常量符號出現(xiàn)，則 H0 由一個常量符號 a 組成。 對于 i 1，2， ，令 Hi = Hi-1所有形如 f(t1 ， ， tn) 的項其中f(t1 ， ， tn) 是出現(xiàn)在 S 中的所有 n 元函數(shù)符號， tjHi-1 ，j 1， ， n

19、Hi 為 S的 i 級常量集， H 稱為 S 的 Herbrand 域，簡稱 S的 H域。P(x) ，Q（f(y)VR(y) ） ，于是 S 的 H域a,f(a),f(f(a) 原子集P(a),Q(a),R(a),P(f(a).子句的一個基例=Q(f(a)VR(a),Q(f(f(a)VR(F(a).; 該 S 的 H解釋與原子集相同。H解釋與普通解釋的關(guān)系 ：1、子句集 S 的 H 解釋是 S 的普通解釋。 2、S的普通解釋不一定是 S 的 H解釋：普通解釋不是必須定義在H域上，即使定義在 H域上，也不一定是一個 H解釋。 3、任取普通解釋 I ，依照 I ，可以按如下方法構(gòu)造 S 的一個 H

20、解釋 I* ，使得若S在I 下為真則 S在I*下也為真。定理：如果某區(qū)域 D上的解釋 I 滿足子句集S，則對應(yīng)于 I 的任意一個 H解釋 I* 也滿足S。語義樹： S=P(x) Q(x),P(f(x), Q(f(x) 分別畫出 S的完全語義樹與 封閉語義樹。步驟 3：D1 中無變量符號，算法停止，W不可合一。歸結(jié)定理的幾種改進：支架集歸結(jié)：子句集S 的子集 T 稱為 S 的支架集，如果（ S-T）是可滿足的。一個支架集歸結(jié)是一個不同時屬于（ S-T）的兩個子句的歸結(jié)。語義歸結(jié)： (1) P QR(2)PR(3)QR(4) R令 I= P, Q,R，P Q R。于是在 I下為假的子句只有兩個：

21、Si =P D-P 過程：單文字規(guī)則：若 S 中有一個單元R, QR我們可得如下PI-演繹： (5)R由(2) 、(3)、(1)基子句 L，令 S為刪除 S 中包含 L 的所有(6)由(5)、(4)基子句所剩子句集，則： 1)若 S為空集，（線性歸結(jié)）設(shè) S 是一個子句集， C0是 S中則 S 可滿足。 (2) 否則，令S為刪除 S的一個子句。以C0 為頂子句，從 S 到 Cn的中所有文字 L 所得子句集（若 S 中有單線性歸結(jié)演繹是如下一個演繹：對于 i=0,元基子句 L，則刪文字 L 得空子句），1,n-1 ，Ci+1 是 Ci 和 Bi 的歸結(jié)式。每于是， S 恒假 iff S恒假。定義

22、（純個 Bi 或者屬于 S，或者是一個 Cj ，其中 j文字）：稱 S 的基子句中文字L 是純的，如i 。果 L 不出現(xiàn)在 S 中。純文字規(guī)則設(shè)L 是 S輸入歸結(jié)：邊子句都屬于 S 的線性歸結(jié)演繹中純文字，且 S為刪除 S 中所有包含L 的稱為輸入歸結(jié)演繹 .基子句所剩子句集，則(1) 若 S為空集，則（鎖歸結(jié)式）將子句中的每個文字配上一S 可滿足。 (2) 否則， S恒假 iff S恒個整數(shù)。最小鎖原則（歸結(jié)最小鎖的子句），假。合并規(guī)則（保留最小鎖原則）分裂規(guī)則若 S=(A1 L)(AmL)基于規(guī)則的產(chǎn)生式系統(tǒng)： 1、如果子表達式(B1L)(BnL)R其中E1,Ek 的父親節(jié)點是（ E1 E

23、k）, 則A i , Bi ,R都不含 L 或 L，令 S1 =A1用 k- 連接符（帶弧）把這些子節(jié)點與父節(jié)點AmR，S2= B1BnR 則連接起來，否則用 1- 連接符（不帶?。?。S 恒假 iff S1， S2 同時恒假。（替換的相容性集合、合一復(fù)合替換）設(shè)有歸結(jié)式對任意兩個基子句C1 和 C2。如果替換集合 1，2 ， ， n ，每一C1中存在文字 L1，C2 中存在文字 L2，且 L1i具有如下形式： i = L2，則從 C1 和 C2 中分別刪除L1 和 L2，其中將 C1 和 C2 的剩余部分析取起來構(gòu)成的子句，ti1/vi1， ， tim(i)/vim(i)ti1， ， tim(i) 是項， vi1， ，稱為 C