名师精编优秀资料人工智能的不同研究流派：符号主义/ 逻辑主义学派 - 符号智能；连接主义- 计算智能；行为主义 -低级智能。人工智能的主要 研究领域（一）自动推理（二）专家系统（三）机器学习（四）自然语言理解（五）机器人学和智能控制（六）模式识别（七）基于模型的诊断产生式系统 是人工智能系统中常用的一种程序结构，是一种知识表示系统。三部分组成 ：综合数据库 : 存放问题的状态描述的数据结构 ,动态变化的 。产生式规则集、控制系统。/ 产生式规则集 / 控制系统产生式规则形式： IF前提条件 THEN 操作八数码难题的产生式系统表示综合数据库：以状态为节点的有向图。状态描述：33 矩阵产生式规则：IFThen；依次控制系统：选择规则 : 按左、上、右、下的顺序移动空格。终止条件：匹配成功。产生式系统的基本过程 :Procedure PROCUCTION 1. DATA 初始状态描述2. until DATA 满足终止条件， do：3. begin 4.在规则集合中，选出一条可用于DATA 的规则 R（步骤 4 是不确定的，只要求选出一条可用的规则R，至于这条规则如何选取，却没有具体说明。）5. DATA 把 R应用于 DATA 所得的结果6. End 产生式系统的特点： 1. 模块性强， 2.产生式规则相互独立， 3. 规则的形式与逻辑推理相近，易懂。产生式系统的控制策略 ：1. 不可撤回的控制策略：优点是空间复杂度小、速度快；缺点是多数情况找不到解 2. 试探性控制策略：回溯方式：占用空间小，多数情况下能找到解；缺点是如果深度限制太低就找不到解；和图搜索方式：优点总能找到解，缺点时间空间复杂度高。产生式系统工作方式 ：正向、反向和双向产生式系统可交换产生式系统 ：1. 可应用性，每一条对D可应用的规则，对于对D应用一条可应用的规则后，所产生的状态描述仍是可应用的。2. 可满足性，如果 D满足目标条件，则对D应用任何一条可应用的规则所产生的状态描述也满足目标条件。 3. 无次序性，对 D应用一个由可应用于 D的规则所构成的规则序列所产生的状态描述不因序列的次序不同而改变。可分解的产生式系统 ：能够把产生式系统综合数据库的状态描述分解为若干组成部分，产生式规则可以分别用在各组成部分上，并且整个系统的终止条件可以用在各组成部分的终止条件表示出来的产生式系统，称为可分解的产生式系统。 基本过程 ：Procedure SPLIT 1.DATA 初始状态描述2.Di DATA的分解结果；每个Di 看成是独立的状态描述3.until 对所有的 Di Di ， Di 都满足终止条件， do: 4.begin 5. 在Di 中选择一个不满足终止条件的D* 6. 从Di 中删除 D* 7. 从规则集合中选出一个可应用于D*的规则R 8.D 把 R应用于 D*的结果9.di D 的分解结果10. 把di 加入Di 中11.end 回溯算法 BACKTRACK过程：Recursive Procedure BACKTRACK(DATA) 1.if TERM(DATA),return NIL; 2.if DEADEND(DATA),return FAIL; 3.RULES APPRULES(DATA); 4.LOOP:if NULL(RULES),return FAIL; 5.RFIRST(RULES); 6.RULES TAIL(RULES); 7.RDATA R（DATA ）; 8.PATH BACKTRACK(RDATA); 9if PATH=FAIL,go PATH; 10.return CONS(R,PATH).Procedure GRAPHSEARCH 1G s ， OPEN （s）2CLOSED 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 M 7 （设置指针，调整指针）对于m M, (1)若 m CLOSED, m OPEN, 建立 m到 n 的指针，并 CONS(m, OPEN). (2)(a)mOPEN, 考虑是否修改 m的指针. (b)mCLOSED, 考虑是否修改 m及在 G中后裔的指针。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 5 页名师精编优秀资料 8 重排 OPEN 表中的节点（按某一任意确定的方式或者根据探索信息）。 9 GO LOOP 无信息的图搜索过程：深度优先搜索：排列OPEN 表中的节点时按它们在搜索树中的深度递减排序。深度最大的节点放在表的前面，深度相等的节点以任意方式排序。宽度优先搜索：在排列 OPEN 表中节点时按它们在搜索图中的深度递增顺序，深度最小的节点放在表的前面。 A算法: 使用估价函数 f(n)=g(n)+h(n) 排列 OPEN 表中节点顺序的 GRAPHSEARCH算法。其中， g(n) ：对 g*(n) 的一个估计是当前的搜索图 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) h*(n) 的 A算法。定义：如果一个搜索算法对于任何具有解路径的图都能找到一条最佳路径，则称此算法为可采纳的。可以证明： A*算法是可采纳的（如果解路径存在， A*一定由于找到最佳解路径而结束）A*算法的可采纳性 ：定理 1 GRAPHSEARCH对有限图必然终止。定理2 若存在 s 到目标的路，则算法 A*终止前的任何时刻， 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）计算启发函数所需要的计算量。启发能力的度量：渗透度P = L / T 其中，L 是算法发现的解路径的长度， T是算法在寻找这条解路径期间所产生的节点数（不包括初始节点，包括目标节点）有效分枝系数是B，则有 B B2十BL=T或 B（BL-1 ）/ （B-1）=T 8 数码启发函数 h(n)=P(n)+3S(n),p(n)是每个硬纸片离开目标位置的和，S(n) 是如果一个硬纸片后面的纸片不是它的目标后继则记2，否则记 0，如果中心有硬纸片记1，否则记 0，然后求和。渗透度，搜索算法的性能的度量：P = L / T，L 是算法发现的解路径的长度，T 是算法在寻找这条解路径期间所产生的节点数（不包括初始节点，包括目标节点）。有效分枝数 B，反映目标搜索的集中程度：设搜索树的深度是L，算法所产生的总节点数为 T，则 BB2十 BL=T或 B（BL-1）/（B-1）=T 与/ 或图是一种超图在超图中父亲节点和一组后继节点用超弧连接超弧又叫 k-连接符k- 连接符: 一个父节点指向一组k 个有与关系的后继节点，这样一组弧线称为一个k- 连接符极小极大原则： MAX 节点在其 MIN子节点的倒推值中选 max ；MIN节点在其MAX 子节点的倒推值中选min 剪枝规则：（ 1）剪枝：如果一个MIN节点的值小于或等于它的某一个MAX 祖先节点的 值，则剪枝发生在该MIN节点之下：中止这个MIN节点以下的搜索过程。这个MIN节点最终的倒推值就确定为这个 值。（2）剪枝：如果一个MAX 节点的 值大于或者等于它的某一个MIN祖先节点的 值，则剪枝发生在该MAX 节点之下中止这个MAX 节点以下的搜索过程。该 MAX 节点的最终返回值可以置成它的 值ND=2(BD/2)-1（D为偶数）ND=B(D+1)/2+B(D-1)/2-1 （D 为奇数）D为深度， B为平均后继。定理 1 任意公式 G都等价于一个前束范式证明通过如下四个步骤即可将公式G化为前束范式步骤 1：使用基本等价式 F? H=(FH) (HF) FH= FH 可将公式 G中的? 和删去。步骤 2：使用 ( F)=F 和 De. Morgan 律及引理 1，可将公式中所有否定号放在原子之前。步骤 3：如果必要的话，则将约束变量改名步骤 4：使用引理 1 和引理 2 又将所有量词都提到公式的最左边。G= x yz u v wP(x,y,z,u,v,w) 则用 a 代替 x，用 f(y ，z) 代替 u，用 g(y ，z，v) 代替 w，得公式 G的 Skolem范式：yz vP(a,y,z,f(y,z),v,g(y,z,v) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 5 页名师精编优秀资料定理 2 设 S是公式 G的子句集于是， G是不可满足的，当且仅当S是不可满足的医生骗子问题： SP(a), D(y)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) H)= xG(x ) H (1) x(G(x) H)= 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 设 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) (3) xG(x) x H(x)= xy (G(x )H(y) (4) xG(x) x H(x)= x y (G(x )H(y) 基本等价式1) (GH)=(GH) (HG)；2) (GH)=(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 ； (同一律 ) 9) G F=F ，G T=T ； (零一律 ) 10) (G H)= G H，(G H)= G H。 (De Morgan律) 11) GG=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) zD(z)（2）将公式中所有否定号放在原子之前。xy（A(x) B(x,y)） （yC(y) zD(z)= x y(A(x) B(x,y) (yC(y) zD(z)（3）将约束变量改名 . x y(A(x) B(x,y) (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 tz （(A(x) B(x,y) C(t) D(z) ）= x y tz(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 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 T T F T TI(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为子句集，令 H0是出现于子句集 S的常量符号集。如果S中无常量符号出现，则H0由一个常量符号 a组成。对于 i 1，2，令 Hi = Hi-1所有形如 f(t1 ， tn) 的项其中f(t1 ， tn) 是出现在 S中的所有 n 元函数符号， tj Hi-1 ，j 1， nHi 为 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的普通解释不一精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 5 页名师精编优秀资料定是 S的 H解释：普通解释不是必须定义在H域上，即使定义在H域上，也不一定是一个 H解释。 3、任取普通解释I，依照 I ，可以按如下方法构造S的一个 H解释 I* ，使得若 S 在 I 下为真则 S 在 I* 下也为真。定理：如果某区域D上的解释 I 满足子句集S，则对应于 I 的任意一个 H解释 I* 也满足S。语义树： S=P(x) Q(x),P(f(x), Q(f(x)分别画出 S的完全语义树与封闭语义树。D-P过程：单文字规则：若S中有一个单元基子句 L，令 S为删除 S中包含 L 的所有基子句所剩子句集，则：1) 若 S为空集，则 S 可满足。 (2) 否则，令S为删除S中所有文字 L 所得子句集（若 S 中有单元基子句 L，则删文字 L 得空子句），于是， S 恒假 iff S恒假。定义（纯文字）：称 S的基子句中文字 L 是纯的，如果L 不出现在 S中。纯文字规则设L 是 S中纯文字，且 S为删除 S中所有包含 L 的基子句所剩子句集，则 (1) 若 S为空集，则S可满足。 (2) 否则， S恒假 iff S恒假。分裂规则若 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 同时恒假。归结式对任意两个基子句C1和 C2 。如果C1中存在文字 L1，C2中存在文字 L2，且 L1L2，则从 C1和 C2中分别删除 L1 和 L2，将 C1和 C2的剩余部分析取起来构成的子句，称为 C1和 C2的归结式，记为 R(C1, C2) 。（归结演绎）设 S是子句集。从 S推出子句 C的一个归结演绎是如下一个有限子句序列： C1，C2 ， Ck其中 Ci 或者是 S中子句，或者是 Cj 和 Cr 的归结式 (ji, r i) ；并且 CkC。定理：如果基子句集S是不可满足的，则存在从 S推出空子句的归结演绎。归结式简化 : 若 S=PC1 , ,P Ci ,PCi+1, , PCj,Cj+1 , , Cn 则S=Ci+1 , ,C j ,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= 。步骤 2： D0 =f(a), y。步骤 3：有 v0= y D0 ，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) PQ R(2)PR(3)QR(4) R 令 I= P, Q, R，P Q R。于是在 I 下为假的子句只有两个：Si =P R, QR我们可得如下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，其中 ji 。输入归结：边子句都属于S的线性归结演绎称为输入归结演绎 . （锁归结式）将子句中的每个文字配上一个整数。最小锁原则（归结最小锁的子句），合并规则（保留最小锁原则）基于规则的产生式系统：1、如果子表达式E1,Ek 的父亲节点是（ E1Ek）, 则用 k- 连接符（带弧）把这些子节点与父节点连接起来，否则用1-连接符（不带弧）。（替换的相容性集合、合一复合替换）设有替换集合 1 ，2 ， n ，每一i 具有如下形式： 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是可合一的，则替换集合 1 ，2 ， n称作是相容的，否则称作是不相容的， U1 和 U2的最一般合一替精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 5 页名师精编优秀资料换也叫做 1 ，2 ， n 的合一复合替换。事实:P(x) Q(x) 规则:P(A) R(A) Q(B)R(B) (R(A) R(B) 不是该 AND/OR 图的一个子句表示。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 5 页