人工智能 知識(shí)點(diǎn)歸納

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

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

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

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

5、分解結(jié)果10.把di加入Di中11.end回溯算法BACKTRACK過(guò)程：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=FAIL,go PATH;10.return CONS(R,PA

6、TH).Procedure GRAPHSEARCH1Gs， OPEN （s）2CLOSED NIL 3LOOP：IF OPEN=NIL,THEN FAIL 4 n FIRST(OPEN)，OPEN TAIL(OPEN),CONS(n, CLOSED) 5 IF TERM(n)，THEN 成功結(jié)束 （解路徑可通過(guò)追溯G中從n到s的指針獲得）。 6 擴(kuò)展節(jié)點(diǎn)n， 令M=m m是n的子節(jié)點(diǎn)，且m不是n的祖先 ， G G M 7 （設(shè)置指針，調(diào)整指針）對(duì)于mÎM, (1)若mÏCLOSED, mÏOPEN, 建立m到n的指針，并CONS(m, OPEN). (2)(a)m

7、ÎOPEN, 考慮是否修改m的指針. (b)mÎCLOSED,考慮是否修改m及在G中后裔的指針。 8 重排OPEN表中的節(jié)點(diǎn)（按某一任意確定的方式或者根據(jù)探索信息）。 9 GO LOOP無(wú)信息的圖搜索過(guò)程：深度優(yōu)先搜索：排列OPEN表中的節(jié)點(diǎn)時(shí)按它們?cè)谒阉鳂?shù)中的深度遞減排序 。深度最大的節(jié)點(diǎn)放在表的前面，深度相等的節(jié)點(diǎn)以任意方式排序。寬度優(yōu)先搜索：在排列OPEN表中節(jié)點(diǎn)時(shí)按它們?cè)谒阉鲌D中的深度遞增順序，深度最小的節(jié)點(diǎn)放在表的前面。 A算法: 使用估價(jià)函數(shù)f(n)=g(n)+h(n) 排列OPEN表中節(jié)點(diǎn)順序的 GRAPHSEARCH算法。 其中， g(n)：對(duì)g*(n)的一

8、個(gè)估計(jì) 是當(dāng)前的搜索圖G中s到n的最優(yōu)路徑費(fèi)用 g(n)g*(n) h(n)：對(duì)h*(n)的估計(jì)，稱(chēng)為啟發(fā)函數(shù)。（Note:若h(n)=0，g(n)=d，則 f(n)=d，為寬度優(yōu)先）。A*算法:對(duì)任何節(jié)點(diǎn)n都有h(n)h*(n)的A算法。Ø 定義：如果一個(gè)搜索算法對(duì)于任何具有解路徑的圖都能找到一條最佳路徑，則稱(chēng)此算法為可采納的。 可以證明：A*算法是可采納的（如果解路徑存在，A*一定由于找到最佳解路徑而結(jié)束）A*算法的可采納性：定理1 GRAPHSEARCH對(duì)有限圖必然終止。定理2 若存在s到目標(biāo)的路，則算法A*終止前的任何時(shí)刻，OPEN表中總存在一個(gè)節(jié)點(diǎn)n， n在從s到目標(biāo)的最佳

9、路徑上，且滿(mǎn)足f(n) f*(s) 定理3 若存在從s到目標(biāo)的解路，則算法A*必終止。 定理4 算法A*是可采納的（即如果解路徑存在，A*一定找到最佳解路徑而終止）定理5 算法A*選擇的任意擴(kuò)展點(diǎn)都有f(n)f*(s)可采納的條件：1.與或圖有解圖，2.對(duì)圖中所有節(jié)點(diǎn)n有h(n)h*(n)，3.啟發(fā)函數(shù)滿(mǎn)足單調(diào)性。則AO*必然終止并找出最佳解路徑。影響算法A啟發(fā)能力的三個(gè)重要因素： （1）算法A所找到的解路徑的費(fèi)用。（2）算法A在尋找這條解路徑的過(guò)程中所需要 擴(kuò)展的節(jié)點(diǎn)數(shù)。 （3）計(jì)算啟發(fā)函數(shù)所需要的計(jì)算量。啟發(fā)能力的度量：滲透度P = L / T 其中，L是算法發(fā)現(xiàn)的解路徑的長(zhǎng)度， T是算法

10、在尋找這條解路徑期間所產(chǎn)生的節(jié)點(diǎn)數(shù)（不包括初始節(jié)點(diǎn)，包括目標(biāo)節(jié)點(diǎn)） 有效分枝系數(shù)是B，則有 BB2十BL=T或 B（BL-1）/（B-1）=T8數(shù)碼啟發(fā)函數(shù)h(n)=P(n)+3S(n),p(n)是每個(gè)硬紙片離開(kāi)目標(biāo)位置的和，S(n)是如果一個(gè)硬紙片后面的紙片不是它的目標(biāo)后繼則記2，否則記0，如果中心有硬紙片記1，否則記0，然后求和。滲透度，搜索算法的性能的度量：P = L / T，L是算法發(fā)現(xiàn)的解路徑的長(zhǎng)度，T是算法在尋找這條解路徑期間所產(chǎn)生的節(jié)點(diǎn)數(shù)（不包括初始節(jié)點(diǎn)，包括目標(biāo)節(jié)點(diǎn)） 。有效分枝數(shù)B，反映目標(biāo)搜索的集中程度：設(shè)搜索樹(shù)的深度是L，算法所產(chǎn)生的總節(jié)點(diǎn)數(shù)為T(mén)，則BB2十BL=T或B（

11、BL-1）/（B-1）=T與/或圖是一種超圖在超圖中父親節(jié)點(diǎn)和一組后繼節(jié)點(diǎn)用超弧連接 超弧又叫 k-連接符k-連接符: 一個(gè)父節(jié)點(diǎn)指向一組k個(gè)有與關(guān)系的后繼節(jié)點(diǎn)，這樣一組弧線稱(chēng)為一個(gè)k-連接符l 極小極大原則：MAX節(jié)點(diǎn)在其MIN子節(jié)點(diǎn)的倒推值中選max；MIN節(jié)點(diǎn)在其MAX子節(jié)點(diǎn)的倒推值中選minl 剪枝規(guī)則：（1）剪枝：如果一個(gè)MIN節(jié)點(diǎn)的值小于或等于它的某一個(gè)MAX祖先節(jié)點(diǎn)的值，則剪枝發(fā)生在該MIN節(jié)點(diǎn)之下：中止這個(gè)MIN節(jié)點(diǎn)以下的搜索過(guò)程。這個(gè)MIN節(jié)點(diǎn)最終的倒推值就確定為這個(gè)值。（2）剪枝：如果一個(gè)MAX節(jié)點(diǎn)的值大于或者等于它的某一個(gè)MIN祖先節(jié)點(diǎn)的值，則剪枝發(fā)生在該MAX節(jié)點(diǎn)之下中

12、止這個(gè)MAX節(jié)點(diǎn)以下的搜索過(guò)程。該MAX節(jié)點(diǎn)的最終返回值可以置成它的值l ND=2(BD/2)-1（D為偶數(shù)）ND=B(D+1)/2+B(D-1)/2-1（D為奇數(shù)）D為深度，B為平均后繼。l定理1 任意公式G都等價(jià)于一個(gè)前束范式證明 通過(guò)如下四個(gè)步驟即可將公式G化為前束范式 步驟1：使用基本等價(jià)式 FH=(FH) (HF) FH=FH 可將公式G中的和刪去。 步驟2：使用(F)=F和De. Morgan律及引理1， 可將公式中所有否定號(hào)放在原子之前。步驟3：如果必要的話，則將約束變量改名步驟4：使用引理1和引理2又將所有量詞都提到公式的最左邊。G=$x"y"z$u&quo

13、t;v$wP(x,y,z,u,v,w) 則用a代替x，用f(y，z)代替u，用g(y，z，v)代替w，得公式G的Skolem范式："y"z"vP(a,y,z,f(y,z),v,g(y,z,v) 定理2 設(shè)S是公式G的子句集于是，G是不可滿(mǎn)足的，當(dāng)且僅當(dāng)S是不可滿(mǎn)足的醫(yī)生騙子問(wèn)題：SP(a),D(y)ÚL(a,y),P(x)ÚQ(y)ÚL(x, y),D(b),Q(b)引理1 設(shè)G是僅含有自由變量x的公式，記以G（x），H是不含變量x的公式，于是有 (1) "x(G(x)H)= "xG(x )H(1)$x(G(x)H

14、)= $xG(x )H(2) "x(G(x)H)= "xG(x ) H(2)$x(G(x) H)= $xG(x ) H(3) ("xG(x)= $x (G(x )(4) ($xG(x)= "x (G(x )引理2 設(shè)H，G是兩個(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) (3) "xG(x)"x H(x)= "x"y (G(x )H(y)(4)

15、$xG(x)$x H(x)= $x$y (G(x )H(y)l 基本等價(jià)式1) (G«H)=(G®H)Ù(H®G)； 2) (G®H)=(GÚH)； 3) GÚG=G，GÙG=G； (等冪律)4) GÚH=HÚG，GÙH=HÙG； (交換律) 5) GÚ(HÚS)=(GÚH)ÚS， GÙ(HÙS)=(GÙH)ÙS； (結(jié)合律) 6) GÚ(GÙH)=G，GÙ(G

16、18;H)=G； (吸收律)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ÚH)= GÙH， (GÙH)= GÚH。 (De Morgan律)11) GÚG=T；GÙG=F （互補(bǔ)律）12) G=G （雙重否定律） 將公式"x"y

17、（A(x) ®B(x,y)）®($yC(y) ®$zD(z)化為前束范式解：（1）消去®聯(lián)結(jié)詞。 "x"y（A(x) ®B(x,y)）®($yC(y) ®$zD(z)= "x"y（A(x) Ú B(x,y)）Ú（$yC(y) Ú$zD(z)（2）將公式中所有否定號(hào)放在原子之前。 "x"y（A(x) Ú B(x,y)）Ú（$yC(y) Ú$zD(z)= $x$y(A(x) ÙB(x,y) Ú

18、;("yC(y) Ú$zD(z)（3）將約束變量改名. $x$y(A(x) ÙB(x,y) Ú ("yC(y) Ú$zD(z)= $x$y(A(x) ÙB(x,y) Ú ("tC(t) Ú$zD(z)（4）將量詞提到整個(gè)公式前。 $x$y(A(x) ÙB(x,y) Ú ("tC(t) Ú$zD(z)= $x$y"t$z （(A(x) ÙB(x,y) Ú C(t) ÚD(z)）= $x$y"t$z(A(x)&

19、#218;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， a 2 f(2) f(3) 3 2 P(2) P(3) Q(2, 2) Q(2, 3) Q(3, 2) Q(3, 3) F T

20、 T T F TTI(G)= TI(P(f(2)ÙQ(2，f(2)Ú P(f(3)ÙQ(3，f(2)= TI(P(3)ÙQ(2，3)Ú(P(2)ÙQ(3，3)=(TÙT)Ú(FÙT)=Tl TI(H)= TI(P(2)ÙQ(2，2)ÙP(3)ÙQ(3，2)=FÙTÙTÙF=F（Herbrand域）設(shè)S為子句集，令H0是出現(xiàn)于子句集S的常量符號(hào)集。如果S中無(wú)常量符號(hào)出現(xiàn)，則H0由一個(gè)常量符號(hào)a組成。 對(duì)于i1，2，令Hi = Hi-1È所

21、有形如f(t1，tn)的項(xiàng)其中f(t1，tn)是出現(xiàn)在S中的所有n元函數(shù)符號(hào)，tjÎ Hi-1，j1，nHi為S的i級(jí)常量集，H¥ 稱(chēng)為S的Herbrand域，簡(jiǎn)稱(chēng)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). 子句的一個(gè)基例=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解釋?zhuān)浩胀ń忉尣皇潜仨毝x在H域上，即使定義在H域上，也不一定是一個(gè)H解釋。3、任取普通解

22、釋I，依照I，可以按如下方法構(gòu)造S的一個(gè)H解釋I*，使得若 S在 I下為真則 S在I*下也為真。定理：如果某區(qū)域D上的解釋I滿(mǎn)足子句集S，則對(duì)應(yīng)于I的任意一個(gè)H解釋I*也滿(mǎn)足S。 語(yǔ)義樹(shù)：S=P(x)Q(x),P(f(x), Q(f(x)分別畫(huà)出S的完全語(yǔ)義樹(shù)與 封閉語(yǔ)義樹(shù)。D-P過(guò)程：?jiǎn)挝淖忠?guī)則：若S中有一個(gè)單元基子句L，令S為刪除S中包含L的所有基子句所剩子句集，則：1) 若S為空集，則S可滿(mǎn)足。(2) 否則，令S為刪除S中所有文字L所得子句集（若S 中有單元基子句L，則刪文字L 得空子句），于是， S恒假 iff S恒假。定義（純文字）：稱(chēng)S的基子句中文字L是純的，如果L不出現(xiàn)在S中。純

23、文字規(guī)則設(shè)L是S中純文字，且S為刪除S中所有包含L的基子句所剩子句集，則(1)若S為空集，則S可滿(mǎn)足。(2) 否則，S恒假 iff S恒假。分裂規(guī)則若S=(A1 ÚL) Ù Ù (Am ÚL) Ù(B1 Ú L) Ù Ù (Bn Ú L) ÙR其中A i , Bi ,R都不含L或L，令 S1 =A1 Ù Ù Am ÙR，S2= B1 Ù Ù Bn ÙR 則S恒假 iff S1 ， S2同時(shí)恒假。 歸結(jié)式 對(duì)任意兩個(gè)基子句C1和C2。如果

24、C1中存在文字L1，C2中存在文字L2，且L1L2，則從C1和C2中分別刪除L1和L2，將C1和C2的剩余部分析取起來(lái)構(gòu)成的子句，稱(chēng)為C1和C2的歸結(jié)式，記為R(C1, C2)。 （歸結(jié)演繹） 設(shè)S是子句集。從S推出子句C的一個(gè)歸結(jié)演繹是如下一個(gè)有限子句序列： C1，C2，Ck其中Ci或者是S中子句，或者是Cj和Cr的歸結(jié)式 (j<i, r< i)；并且CkC。定理：如果基子句集S是不可滿(mǎn)足的，則存在從S推出空子句的歸結(jié)演繹。歸結(jié)式簡(jiǎn)化:若S=PC1, ,PCi , PCi+1, ,PCj,Cj+1 , , Cn則S=Ci+1, ,Cj,Cj+1 , , Cn S=C1, ,Ci , Cj+1 , , Cn合一算法：定義(替換)一個(gè)替換是形如t1/v1, , tn/vn 的一個(gè)有限集合，其中vi是變量符號(hào)，ti是不同于vi的項(xiàng)。合一算法步驟：W=Q(f(a), g(x), Q(y, y), 求W的mgu。l 步驟1： k=0, W0=W, s0=e。l 步驟2： D0 =f(a), y。l 步驟3：有v0= y ÎD0，v0不出現(xiàn)在t0f(a)中。l 步驟4：令 s1=s0×t0/v0=f(a)/y, W1=Q(f(a), g(x), Q(