人工智能知识点归纳

 义人工智能的不同研究流派：符号主义/--逻辑主义学派计算智能；行为主义--符号智能；连接主-低级智能。 人工智能的主要研究领域 （一）自动推理（二）专家系统（三）机器学习（四）自然语言理解（五）机器人学和智能控制（六）模式识别（七）基于模型的诊断 产生式系统 是人工智能系统中常用的一种程序结构，是一种知识表示系统。 三部分组成态描述的数据结构： 综合数据库, 动态变化的:存放问题的状。产生式规则集、控制系统。 / 产生式规则形式：产生式规则集 IF/ 前提条件控制系统 THEN 操作 八数码难题的产生式系统表示综合数据库：以状态为节点的有向图。 状态描述： 3×3矩阵 产生式规则：➢ IF<依次空格不在最左边 >Then<左移空格>；控制系统： 选择规则 :按左、上、右、下的顺序移动空格。 产生式系统的基本过程终止条件：匹配成功。: Procedure PROCUCTION 1.2. DATAuntil DATA ←初始状态描述满足终止条件， do： 3. begin 4. DATA在规则集合中，选出一条可用于的规则R（步骤4是不确定的，只要求选出一条可用的规则R，至于这5. 条规则如何选取，却没有具体说明。） DATA←把R应用于DATA所得的结果 6. End 产生式系统的特点：规则相互，3.规则的形式与逻辑推理相1.模块性强，2.产生式近，易懂。 产生式系统的控制策略策略：优点是空间复杂度小、速度快；缺点：1.不可撤回的控制是多数情况找不到解 2.试探性控制策略：回溯方式：占用空间小，多数情况下能找到解；缺点是如果深度太低就找不到解；和图搜索方式：优点总能找到解，缺点时间空间复杂度高。产生式系统工作方式 ：正向、反向和双向产生式系统 可交换产生式系统D可应用的规则，对于对：1.可应用性，每一条对D应用一条可应用的规则后，所产生的状态描述仍是可应用的。2.应用任何一条可应用的规则所产生的状态描可满足性，如果D满足目标条件，则对D述也满足目标条件。3.无次序性，对D应用一个由可应用于D的规则所构成的规则序列所产生的状态描述不因序列的次序不同而改变。 可分解的产生式系统：能够把产生式系统综合数据库的状态描述分解为若干组成部分，产生式规则可以分别用在各组成部分上，并且整个系统的终止条件可以用在各组成部分的终止条件表示出来的产生式系统，称为可分解的产生式系统。基本过程： Procedure SPLIT 1.DATA 2.{Di} ←← DATA初始状态描述的分解结果；每个 Di看成是的状态描述 3.until 止条件，对所有的do: Di {Di}， Di都满足终4.begin 5. 6. 从在{Di}{Di}中删除中选择一个不满足终止条件的D* D* 7.从规则集合中选出一个可应用于D*的规则R

8.D ← 把R应用于D*的结果 9.{di} ← D的分解结果 10.11.end 把{di}加入{Di}中 回溯算法BACKTRACK过程：Recursive Procedure BACKTRACK(DATA) 1.if TERM(DATA),return NIL; 2.if DEADEND(DATA),return FAIL; 3.RULES4.LOOP:if NULL(RULES),return FAIL; ←APPRULES(DATA); 5.R←FIRST(RULES); 6.RULES7.RDATA←←TAIL(RULES); R（DATA）; 8.PATH←BACKTRACK(RDATA); 910.return CONS(R,PATH).．if PATH=FAIL,go PATH; Procedure GRAPHSEARCH 12．．GCLOSED ←{s}，← OPEN NIL．←（ s）． 3．LOOP：IF OPEN=NIL,THEN FAIL． 4TAIL(OPEN),CONS(n, CLOSED) ． n ← FIRST(OPEN)，OPEN ．← 5． IF TERM(n)，THEN 成功结束 s的指针获得）。（解路径可通过追溯 G中从n到6． 扩展节点n， 点，且m不是n的祖先令M={m} ，︱ G m是←nG 的子节∪M 7． （设置指针，调整指针）对于mM, (1)到n的指针，并若mCLOSED, mCONS(m, OPEN).

OPEN, 建立m (2)(a)mOPEN, 考虑是否修改m的指针 (b)m. CLOSED,考虑是否修改m及在G中后裔的指针。

名师精编 优秀资料

8． 重排OPEN表中的节点（按某一个硬纸片后面的纸片不是它的目标后继则记任意确定的方式或者根据探索信息）。 2，否则记0，如果中心有硬纸片记1，否则 9． GO LOOP 记0，然后求和。 无信息的图搜索过程：深度优先搜索：排列渗透度，搜索算法的性能的度量：P = L / OPEN表中的节点时按它们在搜索树中的深度T，L是算法发现的解路径的长度，T是算法递减排序 。深度最大的节点放在表的前面，在寻找这条解路径期间所产生的节点数（不深度相等的节点以任意方式排序。宽度优先搜索索图中的深度递增顺序，深度最小的节点放：在排列OPEN表中节点时按它们在搜在表的前面。 A排列OPEN算法表中节点顺序的: 使用估价函数 GRAPHSEARCHf(n)=g(n)+h(n) 算法。 当前的搜索图其中， g(n)G中：对s到g*(n)n的最优路径费用的一个估计 是 g(n)≥g*(n) h(n)（Note:若：对h(n)=0h*(n)，g(n)=d的估计，称为启发函数。，则 f(n)=d，为宽度优先）。 A*算法。算法:对任何节点n都有h(n)≤h*(n)的A➢ 定义： 有解路径的图都能找到一条最佳路径，如果一个搜索算法对于任何具则称此算法为可采纳的。 可以证明：A*算法是可采纳的（如果解路径存在，束） A*一定由于找到最佳解路径而结A*算法的可采纳性：定理1 GRAPHSEARCH对有限图必然终止。定理标的路，则算法A*终止前的任何时刻，2 若存在s到目OPEN表中总存在一个节点n’， n’在从s到目标的最佳路径上，且满足定理3 若存在从s到目标的解路，则算法f(n’) ≤f*(s) A*必终止。 定理存在，4 A*算法一定找到最佳解路径而终止）．A*是可采纳的（即如果解路径 定理5 算法A*选择的任意扩展点都有f(n)≤可采纳的条件：f*(s) 1.与或图有解图，2.对图中所有节点n有h(n)≤h*(n)，3.启发函数满足单调性。则径。 AO*必然终止并找出最佳解路影响算法A启发能力的三个重要因素： （2）算法（1）算法A在寻找这条解路径的过程中所A所找到的解路径的费用。需要 扩展的节点数。 启发能力的度量：渗透度（3）计算启发函数所需要的计算量。P = L / T 其中， L是算法发现的解路径的长度， T的节点数（不包括初始节点，包括目标节点）是算法在寻找这条解路径期间所产生有效分枝系数是B，则有 B＋B2十…＋L

或8数码启发函数 B（BL

B=T-1）h(n)=P(n)+3S(n),p(n)/（B-1）=T 是每个硬纸片离开目标位置的和，S(n)是如果一

包括初始节点，包括目标节点） 。 有效分枝数设搜索树的深度是B，反映目标搜索的集中程度：L，算法所产生的总节点数为T，则B＋B2十…＋BL=T或B（BL-1）/（与B-1/或图）=T 是一种超图．在超图中父亲节点和一组后继节点用超弧连接． 超弧又叫 k-连接符．k-连接符 : 一个父节点指向一组k个有与关系的后继节点，这样一组弧线称为一个k-连接符． 极小极大原则： 点的倒推值中选MAXmax节点在其；MIN节点在其MIN子节 MAX剪枝规则：（子节点的倒推值中选min MIN节点的β值小于或等于它的某一个1）α剪枝：如果一个MAXMIN祖先节点的α值，则剪枝发生在该节点之下：中止这个MIN节点以下的搜索过程。这个MIN节点最终的倒推值就确定为这个β值。（2）β剪枝：如果一个MAX 节点的α值大于或者等于它的某一个MIN祖先节点的β值，则剪枝发生在该点之下．中止这个MAX节点以下的搜MAX节索过程。该MAX节点的最终返回值可 以置成它的α值．ND=2(B^D/2)-1 ND=B^(D+1)/2+B^(D-1)/2-1（D为偶数）（D为奇数）定理 D为深度，B为平均后继。 1 任意公式G都等价于一个前束范式． 证明前束范式． 通过如下四个步骤即可将公式 G化为 步骤1：使用基本等价式 FH=～F∨H ↔H=(F→H) ∧(H→F) F→ 可将公式G中的↔和→删去。 及引理步骤2：使用～1， (～F)=F和De. Morgan律 可将公式中所有否定号～放在原子之前。步骤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，得公式yzvP(a,y,z,f(y,z),v,g(y,z,v)) G的Skolem范式： 名师精编 优秀资料

定理2 设S是公式G的子句集．于是，G xy(A(x) ～B(x,y))  (y～C(y) 是不可满足的，当且仅当S是不可满足的． zD(z)) 医生骗子问题：S＝｛P(a),～= xy(A(x) ～B(x,y))  (t～C(t) D(y)L(a,y),～P(x)～Q(y)～L(x, zD(z)) y),D(b),Q(b)｝引理1 设G是仅含有自由（4）将量词提到整个公式前。 变量x的公式，记以G（x），H是不含变量xy(A(x) ～B(x,y))  (t～C(t) x的公式，于是有 zD(z)) (1) x(G(x)∨H)= xG(x )∨H = xytz （(A(x) ～B(x,y))  ～C(t) (1)’x(G(x)∨H)= xG(x )∨H (2) x(G(x)∧H)= xG(x ) ∧H (2)’(3) ～(x(G(x) xG(x))= ∧H)= x (xG(x ) ～G(x )) ∧H (4) ～(xG(x))= x (～G(x )) 引理公式，分别记以2 设H，G是两个仅含有自由变量H(x)，G(x)，于是有：x 的(1) xG(x)∧x H(x)= x(G(x )∧H(x)) (2) (3) xG(x)xG(x)∨∨x H(x)= x H(x)= x(G(x )xy (G(x )∨H(x)) ∨H(y)) (4) xG(x)∧x H(x)= xy (G(x )1)  基本等价式(GH)=(G ∧H(y)) H)(HG)； 2) 3) (GGG=GH)=(，G～G=GGH)；； ( 等幂律) 4) 5) GGH=H(HS)=(GG，GH=HH)SG，； (交换律) 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) 10) ～G(GF=FH)= ，G～T=TG～；H (， 零一律) ～(GH)= ～G～H。 (De Morgan11) G～律) G=T；G～G=F （互补律）12) ～～G=G （双重否定律）将公式x y（A(x) B(x,y)）(yC(y) 解：（zD(z))化为前束范式 x1y）消去（A(x) 联结词。B(x,y) ） (yC(y) = ～zD(z))xy（ ～A(x)  B(x,y)）（～（2zD(z))）将公式中所有否定号 yC(y) ～放在原子之前。 ～xy（～A(x)  B(x,y)）（～= yC(y) xy(A(x) zD(z))～ B(x,y)) (y～C(y) （3zD(z))）将约束变量改名 . = D(z)x）y tz((A(x)～C(t)D(z))(～B(x,y)用a代替～xC(t)，用bD(z)))代替y ，用f(t)代替z， 得公式的Skolem范式： t((A(a)  ～C(t)  ～C(t) D(f(t)))) D(f(t))) (～B(a,b) 例：2) H=1) G=x(P(x)x(P(f(x))Q(x，a))Q(x ，f(a))) 设解释I： D={2，3}， a 2 f(2) f(3) P(2) P(3) Q(2, 2) Q(2, 3) Q(3, 3 2 2) Q(3, 3) F T T T F T TI(G) = TI((P(f(2))Q(2，f(2))) P(f(3)) = TQ(3，f(2)))) I((P(3)Q(2，3))(P(2)Q(3，3))) =(TT)(FT)  =TT I(H) = TI(P(2)Q(2，2)P(3)Q(3，2)) =FTTF =F （Herbrand域）设S为子句集，令H0是出现于子句集S的常量符号集。如果S中无常量符号出现，则组成。 对于i＝1，2H0，…，令由一个常量符号Hi = Hi-1a｛所有形如f(t1，…，tn)的项｝其中f(t1数符号，，…，tjtn) Hi-1是出现在，j＝S1，…，中的所有n．nHi元函为S的i级常量集，H 称为S的Herbrand域，简称{P(x)S，的Q（H域。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))..};该H解释与普通解释的关系S的H解释与原子集相同。：1、子句集 S的H

解释是S的普通解释。2、S的普通解释不一

名师精编 优秀资料

定是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的完合一算法：定义(替换)一个替换是形如{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}, 全语义树与 封闭语义树。

D-P过程：单文字规则：若S中有一个单元基子句L，令S’为删除S中包含L的所有基子句所剩子句集，则：则S可满足。(2) 否则，令1) 若S’’为删除S’为空集，S’中所有文字～L所得子句集（若S’ 中有单元基子句～于是， S恒假L，则删文字～ iff S’’恒假。定义（纯L 得空子句），文字）：称S的基子句中文字L是纯的，如果～中纯文字，且L不出现在S’为删除S中。纯文字规则设S中所有包含L是L的S基子句所剩子句集，则(1)若S’为空集，则S假。可满足。 (2) 否则，S恒假 iff S’恒规则若S=(A1 L) …  (Am L) A i , Bi ,R(B1  ～L) 都不含 … L或～ (Bn L，令 ～ S1 =A1 L) R其中S…  Am R，S2= B1  …  Bn R 归结式恒假 iff S1 对任意两个基子句， S2同时恒假。C1和 则C2。如果C1中存在文字L1，C2中存在文字L2，且L1＝～将C1L2和，则从C2的剩余部分析取起来构成的子句，C1和C2中分别删除L1和L2，称为C1和C2的归结式，记为R(C1, C2)。 （归结演绎）句C的一个归结演绎是如下一个有限子句序 设S是子句集。从S推出子列： C1或者是，C2Cj，…，和CrCk的归结式其中Ci (j或者是i, rS中子句， i)；并且Ck＝C。定理：如果基子句集S是不可满足的，则存在从归结式简化:若S={PS推出空子句的归结演绎。∨C1’, … ,P∨ Ci’ , ～P∨Ci+1’,… ,～P∨CjS’’={Ci+1,Cj+1 ,’,… ,C… , Cn}j’则,Cj+1 , … , Cn} S’’={C1’, … ,Ci’ , Cj+1 ,… , Cn}

W1={Q(f(a), g(x)), Q(f(a), f(a))}

 步骤步骤2W不可合一。3：： D1 ={g(x), f(a) }D1中无变量符号，算法停止，。

归结定理的几种改进：支架集归结：子句集S可满足的。一个支架集归结是一个不同时属的子集T称为S的支架集，如果（S-T）是于（S-T）的两个子句的归结。

语义归结：R(4)～R (1)令～ I={P∨～～P, Q∨～R(2)PQ, ～∨R}R(3)Q，P∨QR。

于是在I下为假的子句只有两个：Si ={P∨R, QPI-演绎：∨R}我们可得如下(5)R 由(2) 、(3) 、(1) (6) 由(5)、(4) （线性归结）设的一个子句。以SC0是一个子句集，为顶子句，从SC0到是CnS的中线性归结演绎是如下一个演绎：对于 i=0, 1, … ,n个Bi或者属于-1，Ci+1S，或者是一个是Ci和Bi的归结式。每Cj，其中j i。 输入归结：边子句都属于称为输入归结演绎. S的线性归结演绎（锁归结式） 将子句中的每个文字配上一个整数。最小锁原则（归结最小锁的子句），合并规则（保留最小锁原则） 基于规则的产生式系统：1、如果子表达式E1,用k-…连接符（带弧）把这些子节点与父节点,Ek的父亲节点是（E1∨…∨Ek）,则连接起来，否则用1-连接符（不带弧）。 （替换的相容性集合、合一复合替换）设有替换集合{σ1 ，σ2 ，……，σn}，每一σi 具有如下形式：σi =

{ti1/vi1 ti1，……，，……，tim(i) tim(i)/vim(i)}是项，vi1，……，其中vim(i)是变量；我们用这些替换构造两个表达式U1 ={v11U1和，……，U2如下：v1m(1) ，……，vn1，……，vnm(n) } U2 ={t11tn1，……，，……，tnm(n)t1m(1)）} ，……，如果U1 和U2是可合一的，则替换集合{σ1 称作是不相容的，，σ2 ，……，σU1 n}和称作是相容的，否则U2的最一般合一替名师精编 优秀资料

换也叫做{σ1 ，σ2 ，……，σn}的合一复合替换。

事实:P(x)∨Q(x)

规则:P(A)→R(A) Q(B)→R(B)

(R(A)∨R(B))不是该AND/OR图的一个子句表示。