人工智能 知识点归纳

人工智能的不同研究流派人工智能的不同研究流派：符号主 义/逻辑主义学派-符号智能；连接主 义-计算智能；行为主义-低级智能。 人工智能的主要研究领域研究领域 （一）自动推理（二）专家系统（三）机器 学习（四）自然语言理解（五）机器人学和 智能控制（六）模式识别（七）基于模型的 诊断产生式系统产生式系统是人工智能系统中常用的一种 程序结构，是一种知识表示系统。 三部分组成三部分组成： 综合数据库:存放问题的状存放问题的状 态描述的数据结构态描述的数据结构, , 动态变化的动态变化的。产生式规 则集、控制系统。 / 产生式规则集/ 控制系统 产生式规则形式：产生式规则形式： IF前提条件 THEN操 作 八数码难题的产生式系统表示八数码难题的产生式系统表示 综合数据库：以状态为节点的有向图。状态描述： 3×3 矩阵 产生式规则： IFThen ；依次 控制系统：选择规则:按左、上、右、下的顺序 移动空格。终止条件：匹配成功。 产生式系统的基本过程产生式系统的基本过程: : Procedure PROCUCTION 1. DATA初始状态描述 2. until DATA 满足终止条件，do： 3. begin 4. 在规则集合中，选出一条可用于 DATA 的规则 R（步骤步骤 4 4 是不确定的，是不确定的， 只要求选出一条可用的规则只要求选出一条可用的规则 R 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 回溯算法回溯算法 BACKTRACKBACKTRACK 过程过程：Recursive Procedure BACKTRACK(DATA) 1.if TERM(DATA),return NIL; 2.if DEADEND(DATA),return FAIL; 3.RULESAPPRULES(DATA); 4.LOOP:if NULL(RULES),return FAIL; 5.RFIRST(RULES); 6.RULESTAIL(RULES); 7.RDATAR（DATA）; 8.PATHBACKTRACK(RDATA); 9if PATH=FAIL,go PATH; 10.return CONS(R,PATH). ProcedureProcedure GRAPHSEARCHGRAPHSEARCH 1Gs， OPEN （s） 2CLOSED NIL3LOOP：IF OPEN=NIL,THEN FAIL4 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 M7 （设置指针，调整指针）对于 mM,(1)若 mCLOSED, mOPEN, 建立 m 到 n 的指针，并 CONS(m, OPEN).(2)(a)mOPEN, 考虑是否修改 m 的 指针.(b)mCLOSED,考虑是否修改 m 及在 G 中后裔的指针。8 重排 OPEN 表中的节点（按某一 任意确定的方式或者根据探索信息）。9 GO LOOP无信息的图搜索过程：深度优先搜索无信息的图搜索过程：深度优先搜索：排列 OPEN 表中的节点时按它们在搜索树中的深度 递减排序 。深度最大的节点放在表的前面， 深度相等的节点以任意方式排序。宽度优先宽度优先 搜索搜索：在排列 OPEN 表中节点时按它们在搜 索图中的深度递增顺序，深度最小的节点放 在表的前面。A 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*A*算法算法:对任何节点 n 都有 h(n)h*(n)的 A 算法。 定义：定义：如果一个搜索算法对于任何具如果一个搜索算法对于任何具 有解路径的图都能找到一条最佳路径，有解路径的图都能找到一条最佳路径， 则称此算法为可采纳的。则称此算法为可采纳的。 可以证明：可以证明：A*A*算法是可采纳的（如果解算法是可采纳的（如果解 路径存在，路径存在，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 A 启发能力的三个重要因素：启发能力的三个重要因素：（1）算法 A 所找到的解路径的费用。 （2）算法 A 在寻找这条解路径的过程中所 需要 扩展的节点数。（3）计算启发函数所需要的计算量。 启发能力的度量：渗透度启发能力的度量：渗透度 P P = = L L / / T T 其中， L 是算法发现的解路径的长度，T 是算法在寻找这条解路径期间所产生 的节点数（不包括初始节点，包括目标节点）有效分枝系数是有效分枝系数是 B B，则有，则有 B BB B2 2十十B BL L=T=T 或或 B B（B BL L-1-1）/ /（B-1B-1）=T=T 8 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：使用基本等价式FH=(FH) (HF) FH=FH 可将公式 G 中的和删去。步骤 2：使用(F)=F 和 De. Morgan 律 及引理 1，可将公式中所有否定号放 在原子之前。 步骤 3：如果必要的话，则将约束变量改 名 步骤 4：使用引理 1 和引理 2 又将所有量词 都提到公式的最左边。 G=xyzuvwP(x,y,z,u,v,w) 则用 a 代 替 x，用 f(y，z)代替 u，用 g(y，z，v)代 替 w，得公式 G 的 Skolem 范式： yzvP(a,y,z,f(y,z),v,g(y,z,v) 定理 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