人工智能知识点归纳

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

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

2、n左移空格; 依次控制系统：选择规则:按左、上、右、下的顺序 移动空格。终止条件：匹配成功。产生式系统的基本过程:Procedure PR0CUCTI0N1. DATA-初始状态描述2. until DATA满足终止条件，do：3. begin4. 在规则集合中，选出一条可用于 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 -初始状态描述2. Di - DATA的分解结果；每个Di看成 是独立的状态描述3. until对所有的Di eDi， Di都满足终 止条件，do:4. begin5. 在Di中选择一个不满足终止条件的D*6. 从Di中删除D*7. 从规则集合中选出一个可应用于D*的规则 R8. D -把R应用于D*的结果9. di - D的分解结果10. 把di

5、加入Di中11. end回溯算法BACKTRACK过程： RecursiveProcedure BACKTRACK（DATA）1.if TERM（DATA）,re turn NIL;2.if DEADEND（DATA）,re turn FAIL;3. RULESAPPRULES（DATA）;4. L00P:if NULL（RULES）,return FAIL;5. RFIRST（RULES）;6. RULESTAIL（RULES）;7. RDATA-R （DATA）;8. PATH-BACKTRACK（RDATA）;9. if PATH二FAIL,go PATH;10. re turn CON

6、S（R,PATH）.Procedure GRAPHSEARCH1. G-s， OPEN （s）.2. CLOSED NIL.3. LOOP： IF OPEN二NIL,THEN FAIL.4. 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 M7. （设置指针，调整指针）对于m M,（1）若 m CLOSED, m OPEN,建立 m 到n的指针，并CONS（m, OPEN）.（2

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

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

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

10、算法发现的解路径的长度，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是算法在寻找这条解路径期间所产生的节点数(不 包括初始节点，包括目标节点)。有效分枝数B，反映目标搜索的集中程度： 设搜索树的深度是L，算法所

11、产生的总节点 数为 T，则 B+B2 十+BL二T 或 B (BL-1) / (B-1)=T与/或图是一种超图.在超图中父亲节点和 一组后继节点用超弧连接. 超弧又叫 k- 连接符.k-连接符：一个父节点指向一组k个有与关系的后继节点，这样一组弧线称为一个k-连 接符.极小极大原则：MAX节点在其MIN子节 点的倒推值中选max； MIN节点在其 MAX子节点的倒推值中选min剪枝规则：(1)a剪枝：如果一个MIN节点的B值小于或等于它的某一个 MAX祖先节点的a值，贝剪枝发生在该 MIN节点之下：中止这个MIN节点以下 的搜索过程。这个MIN节点最终的倒 推值就确定为这个B值。(2) B剪枝

12、：如果一个MAX节点的a 值大于或者等于它的某一个MIN祖先 节点的B值，则剪枝发生在该MAX节 点之下.中止这个MAX节点以下的搜 索过程。该MAX节点的最终返回值可 以置成它的a值. ND=2(BS/2)-1 (D 为偶数)ND二B,D+1)/2+B,DT)/2T (D 为奇数) D为深度，B为平均后继。定理1任意公式G都等价于一个前束范式. 证明 通过如下四个步骤即可将公式G化为 前束范式.步骤1：使用基本等价式FH=(FH) A (HF) FH二FVH可将公式G中的和一删去。步骤2：使用(F)二F和De. Morgan律 及引理1，可将公式中所有否定号放 在原子之前。步骤 3：如果必要

13、的话，则将约束变量改名 步骤4：使用引理1和引理2又将所有量词 都提到公式的最左边。G=3xVyVz3uVv3wP(x,y,z,u,v,w) 则用 a 代 替x，用f(y，z)代替u，用g(y，z，v)代 替w，得公式G的Skolem范式：VyVzVvP(a,y,z,f(y,z),v,g(y,z,v)定理2设S是公式G的子句集.于是，G 是不可满足的，当且仅当S是不可满足的. 医生骗子问题：S=(P(a), D(y) vL(a,y), P(x) vQ(y) vL(x, y),D(b),Q(b)引理1设G是仅含有自由 变量x的公式，记以G (x), H是不含变量 x的公式，于是有(1) Vx(G

14、(x) VH)= VxG(x ) VH(1) 3x(G(x)VH)= 3xG(x )VH(2) Vx(G(x) AH)= VxG(x ) AH(2) 3x(G(x) AH)= 3xG(x ) AH(3) (VxG(x)= 3x (G(x )(4) GxG(x)= Vx (G(x )引理2设H, G是两个仅含有自由变量x的 公式，分别记以H(x)， G(x)，于是有：(1) VxG(x)A Vx H(x)= Vx(G(x )AH(x)(2) 3xG(x) V3x H(x)= 3x(G(x ) VH(x)(3) VxG(x)VVx H(x)= VxVy (G(x )V H(y)(4) 3xG(x)

15、 A3x H(x)= 3x3y (G(x ) AH(y) 基本等价式1)(GoH) = (GtH) a (HtG)；2)(GtH) = (GvH)；3)GvG=G，GaG=G；（等幂律）4)GvH=HvG，GaH=HaG；（交换律）5)Gv(HvS)=(GvH)vS， Ga(HaS)=(GaH)aS；（结合律）6)Gv(GaH)=G，Ga(GvH)=G；（吸收律）7)Gv(HaS)=(GvH)a(GvS)， Ga(HvS)=(GaH)v(GaS)；（分配8)GvF=G，GaT=G；（同一律)9)GaF=F，GvT=T；（零一律)10) (GvH)= GaH，（GaH）=GvH。(DeMorga

16、n 律)11) GvG=T；GaG=F互补律）12)G=G双重否定律）律）将公式VxVy (A(x) B(x,y) GyC(y) 3zD(z)化为前束范式解：(1)消去T联结词。VxVy (A(x) TB(x,y) TGyC(y) tzD(z)=VxVy (A(x) v B(x,y) v (EyC(y) v3zD(z)(2)将公式中所有否定号放在原子之前。 VxVy(A(x) v B(x,y)v(3yC(y) v3zD(z)=3x3y(A(x)人B(x,y) v(VyC(y) v3zD(z)(3) 将约束变量改名.3x3y(A(x)人B(x,y) v (VyC(y) v3zD(z)=ExEy(

17、A(x)人B(x,y) v (VtC(t) v3zD(z)(4) 将量词提到整个公式前。3x3y(A(x)人B(x,y) v (Vt C(t) v3zD(z)=ExEyVtz (A(x)人B(x,y) v C(t) vD(z)=3x3yV tz(A(x)v C(t )vD(z)人( B(x,y)vC(t)vD(z)用a代替x，用b代替y，用f(t)代替z, 得公式的Skolem范式：Vt(A(a) v C(t) vD(f(t)人(B(a,b) v C(t) vD(f(t)例：1) G=3x(P(f(x) aQ(x，f(a) 2) H=Vx(P(x)aQ(x，a)设解释 I：D=2, 3，a2f

18、 f32P(2)P(3)Q(2, 2)Q(2, 3)Q(3,2) Q(3, 3)FTTTFTT(G)= T (P(f(2)aQ(2，f(2)v P(I f(3)aIQ(3，f(2)= T (P(3)aQ(2，3)v(P(2)aQ(3，3) )I=(TaT)v(FaT)=T T (H) = T (P(2)aQ(2，2)aP(3)aQ(3，2)I)I=FaTaTaF=F(Herbrand域)设S为子句集，令H0 是出现于子句集S的常量符号集。如果S中 无常量符号出现，则H0由一个常量符号a 组成。对于i = 1，2，令Hi = Hi-1u 所有形如f(t 1，t n)的项其中一 f(t 1，t n

19、)是出现在S中的所有n元函 数符号，tje Hi-1，j = 1，n. Hi 为 S 的i级常量集，Hs称为S的Herbrand域， 简称S的H域。P(x)，Q (f(y)VR(y) ，于是 S 的 H 域 ia,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,依照I,可

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

21、 果L不出现在S中。纯文字规则设L是S 中纯文字，且S为删除S中所有包含L的 基子句所剩子句集，贝9(1)若S为空集，则 S可满足。(2)否则，S恒假iff S恒 假。分裂规则若S=(A1 vL)人 a (Am vL) a (B1 v L) a a (Bn v L) aR 其中 A i , Bi ,R都不含L或L,令S1 =A1 aa Am aR, S2= B1 a a Bn aR 贝 S恒假iff S1 , S2同时恒假。归结式 对任意两个基子句C1和C2。如果 C1中存在文字L1, C2中存在文字L2,且L1 =L2，则从C1和C2中分别删除L1和L2, 将C1和C2的剩余部分析取起来构成

22、的子句, 称为C1和C2的归结式，记为R(C1, C2)o(归结演绎) 设S是子句集。从S推出子 句C的一个归结演绎是如下一个有限子句序 列：C1, C2,，Ck其中Ci或者是S中子句， 或者是Cj和Cr的归结式(ji, r i)；并 且Ck = Co定理：如果基子句集S是不可满 足的，则存在从S推出空子句的归结演绎。 归结式简化:若S=PVC1，PV Ci,PVCi+1,，PV Cj ,Cj+1 ,Cn则 S二Ci+1,，Cj ,Cj+1 ,，Cn S二C1,，Ci , Cj+1 ,，Cn合一算法：定义(替换)一个替换是形如t 1/v1,tn/vn 的一个有限集合，其 中vi是变量符号，ti

23、是不同于vi的项。 合一算法步骤：W=Q(f(a), g(x), Q(y, y),求 W 的 mguo步骤 1：k=0, W0=W, a0=8o步骤 2： D0 =f(a), y。步骤3：有v0= y eD0, v0不出现在 t0 = f(a )中。步骤 4：令 o1p0t0/v0 = f(a)/y, W1=Q(f(a), g(x),Q(f(a), f(a)步骤 2： D1 =g(x), f(a) o步骤3： D1中无变量符号，算法停止， W不可合一o归结定理的几种改进：支架集归结：子句集 S的子集T称为S的支架集，如果(S-T)是 可满足的。一个支架集归结是一个不同时属 于(S-T)的两个子

24、句的归结。语义归结：(1)PVQVR(2)PVR(3)QV R(4)R令 I=P,Q,R, PQR。于是在I下为假的子句只有两个：Si =PV r, qvr我们可得如下PI-演绎：(5)R 由(2)、(3)、(1) 口 由(5)、(4)(线性归结)设S是一个子句集，C0是S中 的一个子句。以C0为顶子句，从S到Cn的 线性归结演绎是如下一个演绎：对于i=0, 1,，n-1, Ci+1是Ci和Bi的归结式。每 个Bi或者属于S,或者是一个Cj，其中j io 输入归结：边子句都属于S的线性归结演绎 称为输入归结演绎.(锁归结式)将子句中的每个文字配上一个整数。最小锁原则(归结最小锁的子句)， 合并

25、规则(保留最小锁原则) 基于规则的产生式系统：1、如果子表达式 E1,，Ek的父亲节点是(E1VVEk)，则 用k-连接符(带弧)把这些子节点与父节点 连接起来，否则用1-连接符(不带弧)。(替换的相容性集合、合一复合替换)设有 替换集合o1,o2,on，每一 。i具有如下形式：o 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是可合一的，则替换集合o 1 ,o2 ,on称作是相容的，否则 称作是不相容的，U1和U2 的最一般合一替换也叫做。1 ,。2 , ,on的合一复合替换。事实:P(x) VQ(x)规则:P(A)fR(A)Q(B)fR(B)HZRtBjPWQ/ . 7.7 一片見吟弋:曲型傅頁賈坤珂呼屈,.#(R(A)VR(B)不是该AND/OR图的一个子句 表示。