2022年人工智能知识点归纳 .docx

精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_人工智能的不同讨论流派 ：符号主义/ 规律主义学派 - 符号智能.连接主义- 运算智能.行为主义 - 低级智能.人工智能的主要 讨论领域（一）自动推理（二）专家系统（三）机器学习（四）自然语言懂得（五）机器人学和智能掌握（六）模式识别（七）基于模型的诊断产生式系统 是人工智能系统中常用的一种程序结构,是一种学问表示系统.三部分组成 ： 综合数据库 : 存放问题的状态描述的数据结构 ,动态变化的 .产生式规章集、掌握系统./产生式规章集 /掌握系统产生式规章形式： IF前提条件 THEN 操作八数码难题的产生式系统表示综合数据库：以状态为节点的有向图.状态描述： 3×3矩阵产生式规章：IF< 空格不在最左边>Then<左移空格 >. 依次掌握系统：挑选规章 : 按左、上、右、下的次序移动空格.终止条件：匹配胜利.产生式系统的基本过程 :Procedure PROCUCTION1. DATA初始状态描述2. until DATA满意终止条件, do：3. begin4. 在规章集合中,选出一条可用于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 SPLIT1. DATA 初始状态描述2. Di DATA的分解结果.每个 Di 看成是独立的状态描述3. until对全部的 DiDi , Di 都满意终止条件, do:4.begin5. 在Di 中挑选一个不满意终止条件的 D*6. 从Di 中删除 D*7. 从规章集合中选出一个可应用于 D*的规章R8.D 把 R 应用于 D*的结果9.di D 的分解结果10. 把di加入Di 中11.end回溯算法 BACKTRAC过K程： Recursive Procedure BACKTRACKDATA1. if TERMDATA,return NIL;2. if DEADENDDATA,return FAIL;3. RULESAPPRULESDATA;4. LOOP:if NULLRULES,return FAIL;5. R FIRSTRULES; 6.RULESTAILRULES; 7.RDATAR（DATA） ; 8.PATHBACKTRACKRDATA; 9if PATH=FAIL,go PATH; 10.return CONSR,PATH. Procedure GRAPHSEARCH 1G s , OPEN（ s） 2CLOSEDNIL 3 LOOP： IF OPEN=NIL,THEN FAIL4 n FIRSTOPEN, OPEN TAILOPEN,CONSn, CLOSED5 IF TERMn ,THEN胜利终止（解路径可通过追溯 G中从 n 到s 的指针获得）.6. 扩展节点 n,令 M=m m 是 n 的子节点,且 m不是 n 的祖先, GG M 7 （设置指针,调整指针）对于 mM,1如 mCLOSED, m OPEN, 建立 m到 n 的指针,并 CONSm, OPEN.2amOPEN, 考虑是否修改 m的指针.bmCLOSED考, 虑是否修改 m及在 G中后裔的指针.可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_8 重排 OPEN表中的节点（按某一任意确定的方式或者依据探究信息）.9 GO LOOP无信息的图搜寻过程：深度优先搜寻 ：排列OPEN表中的节点时按它们在搜寻树中的深度递减排序 .深度最大的节点放在表的前面, 深度相等的节点以任意方式排序. 宽度优先搜寻：在排列 OPEN表中节点时按它们在搜 索图中的深度递增次序,深度最小的节点放 在表的前面.A算法:使用估价函数 fn=gn+hn 排列 OPEN表中节点次序的 GRAPHSEARC算H法.其中, gn ：对 g*n 的一个估量 是当前的搜寻图 G中 s 到 n 的最优路径费用gn g*nhn：对 h*n 的估量,称为启示函数.（ Note: 如 hn=0 ,gn=d ,就 fn=d,为宽度优先）.A*算法: 对任何节点 n 都有 hn h*n 的 A算法.定义： 假如一个搜寻算法对于任何具有解路径的图都能找到一条正确路径, 就称此算法为可接受的.可以证明： A*算法是可接受的（假如解路径存在, A*肯定由于找到正确解路径而终止）A*算法的可接受性 ：定理 1 GRAPHSEARCH对有限图必定终止.定理 2如存在 s 到目标的路,就算法 A*终止前的任何时刻, OPEN 表中总存在一个节点 n, n 在从 s 到目标的正确路径上,且满意 fn f*s定理 3如存在从 s 到目标的解路,就算法A*必终止.定理 4算法 A*是可接受的（即假如解路径存在, A*肯定找到正确解路径而终止） 定理 5算法 A*挑选的任意扩展点都有 fnf*s可接受的条件： 1. 与或图有解图, 2. 对图中全部节点 n 有 hn h*n , 3. 启示函数满意单调性.就 AO*必定终止并找出正确解路径.影响算法 A 启示才能的三个重要因素：（ 1）算法 A所找到的解路径的费用.（2） ）算法 A在查找这条解路径的过程中所需要 扩展的节点数.（ 3）运算启示函数所需要的运算量.启示才能的度量：渗透度P = L / T其中,L 是算法发觉的解路径的长度,2LT是算法在查找这条解路径期间所产生的节点数（不包括初始节点,包括目标节点）个硬纸片后面的纸片不是它的目标后继就记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=2BD/2-1 （ D为偶数） ND=BD+1/2+BD-1/2-1 （ D 为奇数） D为深度, B 为平均后继.定理 1 任意公式 G都等价于一个前束范式 证明 通过如下四个步骤即可将公式 G化为前束范式步骤 1：使用基本等价式F. H=FH H FFH=F H可将公式 G中的. 和删去.步骤 2：使用 F=F 和 De. Morgan 律及引理 1,可将公式中全部否定号放在原子之前.步骤 3：假如必要的话,就将约束变量改名 步骤 4：使用引理 1 和引理 2 又将全部量词都提到公式的最左边.G= xyz uv wPx,y,z,u,v,w就用 a 代可编辑资料 - - - 欢迎下载精品_精品资料_L有效分枝系数是 B,就有 B B 十 B =T或B（ B -1 ）/ （B-1 ）=T替 x,用 fy ,z 代替 u,用 gy ,z,v 代替 w,得公式 G的 Skolem 范式：可编辑资料 - - - 欢迎下载精品_精品资料_8 数码启示函数 hn=Pn+3Sn,pn是每个硬纸片离开目标位置的和, Sn 是假如一yzvPa,y,z,fy,z,v,gy,z,v可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_定理 2 设 S 是公式 G的子句集于是, G 是不行满意的,当且仅当 S 是不行满意的 医生骗子问题： S Pa, DyLa,y,PxQyLx,y,Db,Qb 引理 1 设 G是仅含有自由变量 x 的公式,记以 G（x）, H是不含变量x 的公式,于是有1xGx H=xGx H1 xGx H=xGx H2xGx H=xGx H2 xGx H=xGx H3xGx=x Gx 4xGx=x Gx 引理 2 设 H,G是两个仅含有自由变量 x 的公式,分别记以 Hx , Gx ,于是有：1xGx x Hx=xGx Hx2xGx x Hx=xGx Hx3xGx x Hx=xy Gx Hy4xGx x Hx=x y Gx Hy基本等价式1GH=GHHG.2GH= 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,GH S=G H S.结合律6) G G H=G, G G H=G. 吸取律7G H S=G H G S,GH 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) G G=T. G G=F（互补律）12) G=G（双重否定律）将公式xy（ AxBx,y ） yCy zDz 化为前束范式解：（ 1）消去联结词.xy（ AxBx,y ） yCyzDz= xy（ AxBx,y） （ yCyzDz（ 2）将公式中全部否定号放在原子之前. xy（AxBx,y） （ yCyzDz=x yAxBx,yyCy zDz（3） ）将约束变量改名 .x yAxBx,yy Cy zDz=x yAxBx,yt CtzDz（4） ）将量词提到整个公式前.x yAxBx,yt Ct zDz=x ytz （ AxBx,y Ct Dz ）=x ytzAxCtDz Bx,yCtDz用 a 代替 x,用 b 代替 y,用 ft代替 z, 得公式的 Skolem 范式：tAa CtDft Ba,bCtDft例： 1 G=xPfxQx, fa2 H=xPxQx,a设说明 I ：D=2, 3 , a2f2f332P2P3Q2, 2Q2, 3Q3, 2Q3, 3FTTTFTTI G = T I Pf2Q2,f2Pf3Q3,f2= T I P3Q2,3P2Q3,3=TTFT=TTI H = T I P2Q2,2P3Q3, 2=F T T F=F（ Herbrand 域）设 S 为子句集,令 H0 是显现于子句集 S 的常量符号集.假如 S 中无常量符号显现,就 H0 由一个常量符号 a 组成. 对于 i 1, 2,令 Hi = Hi-1全部形如 ft1, tn 的项其中ft1, tn 是显现在 S 中的全部 n 元函数符号, tjHi-1, j 1, nHi 为 S 的 i 级常量集, H称为 S 的 Herbrand 域, 简称 S 的 H域.Px , Q（ fyVRy） ,于是 S 的 H域a,fa,ffa 原子集Pa,Qa,Ra,Pfa.子句的一个基例=QfaVRa,QffaVRFa.;该 S 的 H说明与原子集相同.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=Px Qx,Pfx,Qfx分别画出 S 的完全语义树与封闭语义树.D-P 过程：单文字规章：如 S 中有一个单元基子句 L,令 S为删除 S 中包含 L 的全部基子句所剩子句集,就： 1 如 S为空集,就 S 可满意. 2否就,令 S为删除 S 中全部文字 L 所得子句集（如 S 中有单元基子句 L,就删文字 L 得空子句）,于是, S 恒假 iffS恒假.定义（纯文字）：称 S 的基子句中文字 L 是纯的,如果 L 不显现在 S 中.纯文字规章设 L 是 S 中纯文字,且 S为删除 S 中全部包含 L 的基子句所剩子句集,就 1 如 S为空集,就S 可满意. 2否就, S恒假 iffS恒假.分裂规章如 S=A1LAmLB1LBnLR其中A i , Bi ,R都不含 L 或 L,令 S1 =A1AmR,S2= B1BnR 就S 恒假 iff S1, S2 同时恒假.归结式对任意两个基子句 C1 和 C2.假如C1中存在文字 L1, C2 中存在文字 L2,且 L1 L2,就从 C1 和 C2 中分别删除 L1 和 L2, 将 C1 和 C2 的剩余部分析取起来构成的子句, 称为 C1和 C2的归结式,记为 RC1, C2 .（归结演绎）设 S 是子句集.从 S推出子句 C的一个归结演绎是如下一个有限子句序列：C1, C2, Ck 其中 Ci 或者是 S 中子句, 或者是 Cj 和 Cr 的归结式 ji, ri.并且 Ck C.定理：假如基子句集 S 是不行满意的,就存在从 S 推出空子句的归结演绎.归结式简化 : 如 S=P C1 , ,P Ci , PCi+1, , PCj ,Cj+1 , , Cn就S=Ci+1 , ,C j ,Cj+1 , , CnS =C1, ,C i ,Cj+1 , , Cn合一算法：定义 替换 一个替换是形如t1/v1, , tn/vn 的一个有限集合,其中 vi 是变量符号, ti是不同于 vi 的项.合一算法步骤： W=Qfa, gx, Qy,y,求 W的 mgu.步骤 1： k=0, W0=W,0= .步骤 2： D0 =fa, y.步骤 3：有 v0=yD0, v0 不显现在t0 fa 中.步骤 4：令1= 0 t0/v0=fa/y, W1=Qfa, gx,Qfa, fa步骤 2： D1 =gx, fa .步骤 3：D1 中无变量符号,算法停止,W不行合一.归结定理的几种改进：支架集归结：子句集 S 的子集 T 称为 S 的支架集,假如（ S-T）是可满意的.一个支架集归结是一个不同时属 于（ S-T）的两个子句的归结.语义归结： 1 P Q R2PR3Q R4 R令 I= P, Q, R, P Q R.于是在 I 下为假的子句只有两个： Si =P R, Q R我们可得如下PI- 演绎： 5R由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 的父亲节点是（ E1 Ek）, 就用 k- 连接符（带弧）把这些子节点与父节点连接起来,否就用 1- 连接符（不带弧）.（替换的相容性集合、合一复合替换）设有替换集合 1 , 2 , n ,每一i具有如下形式： i=ti1/vi1, timi/vimi其中ti1 , timi是项, vi1 , vimi是变量.我们用这些替换构造两个表达式 U1 和 U2如下：U1 =v11 , v1m1 , vn1, vnmn U2 =t11 , t1m1 ,tn1 , tnmn ）假如 U1 和 U2是可合一的,就替换集合 1 , 2 , n 称作是相容的,否就称作是不相容的, U1 和 U2的最一般合一替可编辑资料 - - - 欢迎下载精品_精品资料_换也叫做 1 , 2 , n 的合一复合替换.事实:Px Qx规章:PA RAQB RBRA RB 不是该 AND/OR图的一个子句表示.可编辑资料 - - - 欢迎下载