《人工智能知识点归纳》由会员分享，可在线阅读，更多相关《人工智能知识点归纳（5页珍藏版）》请在金锄头文库上搜索。
1、可分解的产生式系统：能够把产生式系统综合数据库的状态描述分解为若干组成部分,产生式规则可以分别用在各用在部组上，并分解的产生式系统来基本过程:统称为可人工智能的不同研究流派：符号主义/逻辑主义学派一符号智能；连接主 义一计算智能；行为主义-低级智能。人工智能的主要研究领域（一）自动推理（二）专家系统（三）机器 学习（四）自然语言理解（五）机器人学和 智能控制（六）模式识别（七）基于模型的 诊断产生式系统是人工智能系统中常用的一种 程序结构，是一种知识表示系统。三部分组成： 综合数据库:存放问题的状 态描述的数据结构，动态变化的。产生式规 则集、控制系统。/产生式规则集/控制系统产生式规则形式：
2、IF前提条件THEN 操 作八数码难题的产生式系统表示综合数据库：以状态为节点的有向图。状态描述：3x3矩阵产生式规贝lj： IF空格不在最左边Then左移空格; 依次控制系统：选择规则:按左、上、右、下的顺序 移动空格。终止条件：匹配成功。产生式系统的基本过程：Procedure PR0CUCTI0N1. DATA-初始状态描述2. until DATA满足终止条件，do：3. begin4. 在规则集合中，选出一条可用于 DATA的规则R （步骤4是不确定的， 只要求选出一条可用的规则R,至于这 条规则如何选取，却没有具体说明。）5. DATA-把R应用于DATA所得的结果6. End产生
3、式系统的特点:1.模块性强，2.产生式 规则相互独立，3.规则的形式与逻辑推理相 近，易懂。产生式系统的控制策略：1.不可撤回的控制 策略：优点是空间复杂度小、速度快；缺点 是多数情况找不到解2.试探性控制策略： 回溯方式：占用空间小，多数情况下能找到 解；缺点是如果深度限制太低就找不到解； 和图搜索方式：优点总能找到解，缺点时间 空间复杂度高。产生式系统工作方式：正向、反向和双向产 生式系统可交换产生式系统：1.可应用性，每一条对 D可应用的规则，对于对D应用一条可应用 的规则后，所产生的状态描述仍是可应用的。2. 可满足性，如果D满足目标条件，则对D 应用任何一条可应用的规则所产生的状态描
4、 述也满足目标条件。3.无次序性，对D应用 一个由可应用于D的规则所构成的规则序列 所产生的状态描述不因序列的次序不同而改 变。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加入Di中11. end回溯算法BACKTRACK过程： RecursiveP
5、rocedure 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 CONS（R,PATH）.Procedure GRAPHSEARCH1. G-s，
6、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）（a）m OPEN,考虑是否修改m的 指针.（b）m CLOSED,考虑是否
7、修改m 及在G中后裔的指针。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):对
8、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到目 标的最佳路径上，且满足f(n) Wf*(s) 定理3若存在从s到目标的解路
9、，则算法 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是算法发现的解路径的长度，T是算法在寻找这条解路径期间所产生 的节点数(不包括初
10、始节点，包括目标节点) 有效分枝系数是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，算法所产生的总节点数为 T，则 B+B2 十+BL二T 或 B (BL-1) /
11、 (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剪枝：如果一个MAX节点的a 值大于或者等于它的某一个MIN祖先 节点的B值，则剪枝发生在
12、该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：如果必要的话，则将约束变量改名 步骤4：使用引理1和引理2又将所有量词 都提到公式的最左边。G=3
13、xVyVz3uVv3wP(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(x) VH)= VxG(x ) VH(1) 3x(G(x)VH)= 3xG(x )VH(2
14、) 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) AVx H(x)= Vx(G(x )人 H(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) A3x H(x)= 3x3y (G(x ) AH(y)基本等价式1)(GoH) = (
15、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。(DeMorgan 律)11) GvG=T；GaG=F(互补律)12) G=G(双重否定律)将公式VxVy(A(x) B(x,y) GyC(y)3zD(z)化为前束范式解:(1)消去T联结词。VxVy
