人工智能知识点归纳

《人工智能知识点归纳》由会员分享，可在线阅读，更多相关《人工智能知识点归纳（4页珍藏版）》请在装配图网上搜索。

1、人工智能的不同研究流派：符号主 义/逻辑主义学派-符号智能；连接主 义-计算智能；行为主义-低级智能。人工智能的主要研究领域(一)自动推理(二)专家系统(三)机器 学习(四)自然语言理解(五)机器人学和 智能控制(六)模式识别(七)基于模型的 诊断产生式系统是人工智能系统中常用的一种程序结构，是一种知识表示系统。三部分组成：综合数据库：存放问题的状态描述的数据结构，动态变化的。产生式规 则集、控制系统。/产生式规则集/控制系统产生式规则形式：IF 前提条件THEN操 作 、一八数码难题的产生式系统表示综合数据库：以状态为节点的有向图。状态描述：3X3矩阵产生式规则：? IF空格不在最左边The

2、门左移空格;依次控制系统：选择规则：按左、上、右、下的顺序 移动空格。终止条件：匹配成功。产生式系统的基本过程：Procedure PROCUCTION1. DATK初始状态描述2. until DATA 满足终止条件，do：3. beg in4. 在规则集合中，选出一条可用于 DATA勺规则R (步骤4是不确定的， 只要求选出一条可用的规则 R,至于这 条规则如何选取，却没有具体说明。)5. DATA把R应用于DATA所得的结果6. End产生式系统的特点：1.模块性强，2.产生式 规则相互独立，3.规则的形式与逻辑推理相 近，易懂。产生式系统的控制策略：1.不可撤回的控制 策略：优点是空间

3、复杂度小、速度快；缺点 是多数情况找不到解2.试探性控制策略： 回溯方式：占用空间小，多数情况下能找到 解；缺点是如果深度限制太低就找不到解； 和图搜索方式：优点总能找到解，缺点时间 空间复杂度高。产生式系统工作方式：正向、反向和双向产 生式系统可交换产生式系统：1.可应用性，每一条对 D可应用的规则，对于对 D应用一条可应用 的规则后，所产生的状态描述仍是可应用的。2. 可满足性，如果D满足目标条件，则对D 应用任何一条可应用的规则所产生的状态描 述也满足目标条件。3.无次序性，对D应用 一个由可应用于D的规则所构成的规则序列 所产生的状态描述不因序列的次序不同而改 变。可分解的产生式系统：

4、能够把产生式系统综 合数据库的状态描述分解为若干组成部分， 产生式规则可以分别用在各组成部分上，并 且整个系统的终止条件可以用在各组成部分 的终止条件表示出来的产生式系统，称为可 分解的产生式系统。基本过程：Procedure SPLIT1. DATA J初始状态描述2. Di DATA的分解结果；每个Di看成 是独立的状态描述3. until 对所有的Di Di , Di都满足终 止条件，do:4. beg in5. 在Di中选择一个不满足终止条件的 D6. 从Di中删除D*7. 从规则集合中选出一个可应用于 D*的规则R8. D把R应用于D*的结果9. di J D的分解结果10. 把di

5、加入Di中11. e nd回溯算法 BACKTRACK程 : RecursiveProcedure BACKTRACK(DATA)1.if TERM(DATA),retur n NIL;2.if DEADEND(DATA),retur n FAIL;3. RULES- APPRULES(DATA);4. LOOP:if NULL(RULES),retur n FAIL;5. R FIRST(RULES);6. RULES- TAIL(RULES);7. RDATA-R (DATA ;8. PATF BACKTRACK(RDATA);9. if PATH=FAIL,go PATH;10. ret

6、ur n CONS(R,PATH).Procedure GRAPHSEARCH1. As , OPEN (s).2. CLOSEDNIL.3 . LOOP IF OPEN=NIL,THEN FAIL4 . n FIRST(OPEN) OPEN TAIL(OPEN),CONS( n, CLOSED).5 . IF TERM(n) , THEN成功结束(解路径可通过追溯G中从n到 s的指针获得)。6.扩展节点n,令M=m| m是n的子节 点，且m不是n的祖先 , G G U M 7 .(设置指针，调整指针)对于 m M,(1) 若 m CLOSED, m OPEN,建立 m 至U n 的指针，并

7、CONS(m, OPEN).(a)mOPEN,考虑是否修改m的指针.(b)mCLOSED考虑是否修改m及在G中后裔的指针。8 .重排OPEN表中的节点(按某一 任意确定的方式或者根据探索信息)。9 . GO LOOP无信息的图搜索过程：深度优先搜索：排列 OPEN表中的节点时按它们在搜索树中的深度 递减排序。深度最大的节点放在表的前面， 深度相等的节点以任意方式排序。 宽度优先 搜索：在排列OPENg中节点时按它们在搜 索图中的深度递增顺序，深度最小的节点放 在表的前面。A 算法 : 使用估价函数 f(n)=g(n)+h(n) 排列OPEN表中节点顺序的GRAPHSEARCH 法。其中， g(

8、n) ：对 g*(n) 的一个估计 是 当前的搜索图G中s到n的最优路径费用 g(n) g*(n)h(n) ：对 h*(n) 的估计，称为启发函数。(Note:若 h(n)=0 , g(n)=d，贝S f(n)=d ，为 宽度优先)。A*算法：对任何节点n都有h(n) h*(n)的A 算法。? 定义： 如果一个搜索算法对于任何具 有解路径的图都能找到一条最佳路径， 贝称此算法为可采纳的。可以证明：A*算法是可采纳的(如果解 路径存在，A*定由于找到最佳解路径而结 束)A*算法的可采纳性：定理1 GRAPHSEARCH 对有限图必然终止。定理2 若存在s到目 标的路，则算法A*终止前的任何时刻，

9、OPEN 表中总存在一个节点 n， n 在从 s 到目 标的最佳路径上，且满足f(n ) f*(s) 定理 3 若存在从 s 到目标的解路，贝算法 A*必终止。定理4算法A*是可采纳的(即如果解路径 存在，A*定找到最佳解路径而终止). 定理5算法A*选择的任意扩展点都有f(n) f*(s)可采纳的条件： 1.与或图有解图， 2.对图中 所有节点n有h(n) h*(n) , 3.启发函数满 足单调性。则AO必、然终止并找出最佳解路 径。影响算法A启发能力的三个重要因素：(1) 算法A所找到的解路径的费用。(2) 算法A在寻找这条解路径的过程中所 需要 扩展的节点数。( 3)计算启发函数所需要的

10、计算量。 启发能力的度量：渗透度 P = L / T 其中， L 是算法发现的解路径的长度，T 是算法在寻找这条解路径期间所产生 的节点数(不包括初始节点，包括目标节点) 有效分枝系数是B,则有B + B2十+ Bl=T 或 B( BL-1 ) / ( B-1 ) =T8 数码启发函数 h(n)=P(n)+3S(n),p(n) 是每 个硬纸片离开目标位置的和，S(n)是如果一 个硬纸片后面的纸片不是它的目标后继则记 2，否则记 0，如果中心有硬纸片记 1，否则 记 0，然后求和。 渗透度，搜索算法的性能的度量： P = L / T, L是算法发现的解路径的长度，T是算法 在寻找这条解路径期间所

11、产生的节点数(不 包括初始节点，包括目标节点) 。 有效分枝数B,反映目标搜索的集中程度： 设搜索树的深度是L,算法所产生的总节点数为T,贝卩B+ B2十+ BL=T或B (BL-1) / ( B-1 )=T与/或图是一种超图在超图中父亲节点和 一组后继节点用超弧连接 超弧又叫 k- 连接符k-连接符：一个父节点指向一组k个有与关 系的后继节点，这样一组弧线称为一个 k-连 接符极小极大原则：MAX节点在其MIN子节 点的倒推值中选 max； M I N 节点在其 MAX子节点的倒推值中选min 剪枝规则：(1)a剪枝：如果一个 MIN节点的B值小于或等于它的某一个 MAX祖先节点的a值，贝卩

12、剪枝发生在该 MIN节点之卞：中止这个MIN节点以下 的搜索过程。这个MIN节点最终的倒 推值就确定为这个B值。(2) B剪枝：如果一个MAX节点的a 值大于或者等于它的某一个 MIN祖先 节点的B值，则剪枝发生在该MAX节 点之下.中止这个MAX节点以下的搜 索过程。该MAX节点的最终返回值可 以置成它的a值.ND=2(BAD/2)-1 (D 为偶数) ND=BA(D+1)/2+BA(D-1)/2-1( D 为奇数)D为深度，B为平均后继。定理1任意公式G都等价于一个前束范式. 证明 通过如下四个步骤即可将公式 G化为 前束范式.步骤 1：使用基本等价式F ? H=(F H) A (H F)

13、 F H二FV H可将公式G中的？和删去。 步骤2:使用(F)=F和De. Morgan律 及引理 1 ，可将公式中所有否定号放 在原子之前。步骤 3：如果必要的话，则将约束变量改名. 步骤 4：使用引理 1 和引理 2 又将所有量词 都提到公式的最左边。G= x y z u 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设S是公式G的子句集.于是，G 是不可满足的,当且仅当 S 是不可满足的. 医生骗子问题：S= P(a),D(y

14、) L(a,y), P(x) Q(y) L(x, y),D(b),Q(b) 弓|理1设G是仅含有自由 变量 x 的公式,记以 G( x), H 是不含变量 x 的公式,于是有(1) x(G(x) VH)= xG(x ) VH(1) x(G(x) VH)= xG(x ) VH(2) x(G(x) AH)= xG(x ) AH(2) x(G(x) AH)= xG(x ) AH(3) ( xG(x)=x ( G(x )(4) ( xG(x)=x ( G(x )引理2设H, G是两个仅含有自由变量x的 公式，分别记以H(x) , G(x)，于是有：(1)xG(x) A x H(x)：=x(G(x )A

15、 H(x)xG(x) V x H(x)=x(G(x )V H(x)xG(x) V x H(x)：=x y (G(x ) VH(y)xG(x) A x H(x)=x y (G(x ) A H(y)基本等价式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;(结合律)6)G (G H)=G, G (G H)=G;(吸收律)7)G (H S)=(G H)(G S),G(H S)=(G H)(G S);( 分配律)8)G F=G G T=G(

16、 同一律)9)G F 二 F, G T=T;( 零一律)10)(G H)=G H, (G H)=GH。(DeMorga n 律)11) G G=T G G=F(互补律)12) G=G(双重否定律)将公式 x y (A(x)B(x,y)(yC(y)zD(z)化为前束范式解：(1)消去联结词。x y (A(x)B(x,y)(yC(y)zD(z) x y ( A(x)B(x,y)( yC(y)(2)将公式中所有否定号，放在原子之前。 x y ( A(x)B(x,y)(yC(y)zD( z)=x y(A(x) B(x,y)( y C(y)zD( z)(3) 将约束变量改名.x y(A(x) B(x,y

17、)( yC(y)zD( z)=x y(A(x) B(x,y)( t C(t)zD(z)(4) 将量词提到整个公式前。x y(A(x) B(x,y)( t C(t)zD( z)=x y t z (A(x) B(x,y) C(t)D(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) 设解释 I :D=2, 3,_a_2f(2)

18、 f(3)32P(2) P(3) Q(2, 2) Q(2, 3) Q(3,2) Q(3, 3)F T T TF 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)=TTi(H) = Ti(P(2)Q(2, 2) P(3) Q(3,2)=F T T F=F(Herbrand域)设S为子句集，令HO 是出现于子句集S的常量符号集。如果S中 无常量符号出现，则H0由一个常量符号a 组成。对于i = 1, 2,，令Hi = Hi-1 所有形如f(t1 ，tn)的项其中 f(t1，tn)是

19、出现在S中的所有n元函 数符号，tj Hi-1 , j = 1,，n. 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解释与普通解释的关系：1、子句集S的H 解释是S的普通解释。2、S的普通解释不一 定是S的H解释：普通解释不是必须定义在 H域上，即使定义在H域上，也不一定是一 个H解释。3、任取普通解释I，依照

20、I，可 以按如下方法构造S的一个H解释I*，使得 若S在I下为真则S在I*下也为真。 定理：如果某区域D上的解释I满足子句集 S,则对应于I的任意一个H解释I*也满足 S。语义树：S=P(x) V 一 Q(x),P(f(x),Q(f(x)分别画出 S 的完全语义树与封闭语义树。S基子句L,令S为删除S中包含L的所有 基子句所剩子句集，贝Z 1)若S为空集, 则S可满足。(2)否则，令S为删除S 中所有文字 L所得子句集(若S中有单 元基子句L,则删文字L得空子句)， 于是，S恒假肝S 恒假。定义(纯 文字)：称S的基子句中文字L是纯的，如 果L不出现在S中。纯文字规则设L是S 中纯文字，且S为

21、删除S中所有包含L的 基子句所剩子句集，则(1)若S为空集，则 S可满足。(2)否则，S恒假 肝S 恒 假。分裂规则若S=(A1 L) (Am L)(B1L) (BnL) R其中A i , Bi ,R 都不含L或L,令S1 =A1 Am R, S2= B1 Bn R 贝SS恒假肝S1 , S2同时恒假。归结式对任意两个基子句C1和C2如果 C1中存在文字L1, C2中存在文字L2,且L1 =L2,则从C1和C2中分别删除L1和L2, 将C1和C2的剩余部分析取起来构成的子句， 称为C1和C2的归结式，记为R(C1, C2)。(归结演绎)设S是子句集。从S推出子句C的一个归结演绎是如下一个有限子

22、句序 列：C1, C2,，Ck其中Ci或者是S中子句， 或者是Cj和Cr的归结式(j i, r i)；并 且Ck= C。定理：如果基子句集S是不可满足的，则存在从S推出空子句的归结演绎。 归结式简化：若S=PV C1，,P VCi,PV Ci+1,PVCj ,Cj+1，,Cn则S二Ci+1 ,Cj ,Cj+1，,Cn S =C1,C i , Cj+1，,Cn 合一算法：定义(替换)一个替换是形如 t1/v1,tn/vn 的一个有限集合，其中vi是变量符号，ti是不同于vi的项。 合一算法步骤：W=Q(f(a), g(x), Q(y, y),求 W勺 mgu步骤 1: k=0, W0=W,0=。

23、步骤 2： DO =f(a), y 。步骤3:有v0= yD0, v0不出现在t0 = f(a)中。步骤 4:令 1= 0 t0/v0=f(a)/y, W1=Q(f(a), g(x),Q(f(a), f(a)步骤 2： D1 =g(x), f(a) 步骤3： D1中无变量符号，算法停止， W不可合一。归结定理的几种改进：支架集归结：子句集 S的子集T称为S的支架集，如果(S-T)是 可满足的。一个支架集归结是一个不同时属 于(S-T)的两个子句的归结。语义归结：(1)PV QV R(2)P V R(3)Q V R(4)R 令 1=P,Q,R, PQR。 于是在I下为假的子句只有两个：Si =P

24、 V R, Q V R我们可得如下PI-演绎：(5)R 由(2)、(3) 、(1)(6) 由(5)、(4)(线性归结)设S是一个子句集，C0是S中 的一个子句。以C0为顶子句，从S到Cn的 线性归结演绎是如下一个演绎：对于i=0, 1,n -1 , Ci+1是Ci和Bi的归结式。每 个Bi或者属于S,或者是一个Cj,其中j i。输入归结：边子句都属于S的线性归结演绎 称为输入归结演绎.(锁归结式)将子句中的每个文字配上一个整数。最小锁原则(归结最小锁的子句)， 合并规则(保留最小锁原则) 基于规则的产生式系统：1、如果子表达式 E1,Ek的父亲节点是(E1VV Ek),贝S 用k-连接符(带弧

25、)把这些子节点与父节点 连接起来，否则用1-连接符(不带弧)。(替换的相容性集合、合一复合替换)设有 替换集合(T1 ,。2 ,，。n，每一 (T i具有如下形式：c i =ti1/vi1 , ,tim(i)/vim(i) 其中ti1 , , tim(i) 是项，vi1 ,vim(i)是变量；我们用这些替换构造两个表 达式U1和U2如下：U1 =v11 ,v1m(1), vn1 , , vnm(n) U2 =t11 ,t1m(1), tn1 , , tnm(n) ) 如果U1和U2是可合一的，则替换集合 c 1 , c 2 ,c n称作是相容的，否则 称作是不相容的，U1和U2的最一般合一替 换也叫做 c 1 , c 2 , ,c n的合一复合替换。事实:P(x) V Q(x)规则:P(A) - R(A) Q(B) - R(B)7 - + a r (R(A) V R(B)不是该AND/OF图的一个子句 表示。