人工智能导论全.pptx

欢迎大家学习人工智能导论 计算机系绪 论人工智能（Artificial Intelligence）简称AI起源于美国1956年的一次夏季讨论会什么是AI？计算算计图灵实验AI的本质问题研究如何制造出人造的智能机器或系统，来模拟人类智能活动的能力，以延伸人们智能的科学。AI的历史回顾第一阶段（40年代中50年代末）神经元网络时代双层网络 M-P模型、感知器模型等问题：XOR问题不能解决Minsky的著作：Perceptions（感知器）AI的历史回顾（续1）第二阶段（50年代中60年代中）通用方法时代物理符号系统主要研究的问题：GPS、游戏、翻译等对问题的难度估计不足，陷入困境AI的历史回顾（续2）一个笑话（英俄翻译）：The spirit is willing but the flesh is week.（心有余而力不足）The vodka is strong but meat is rotten.（伏特加酒虽然很浓，但肉是腐烂的）AI的历史回顾（续3）出现这样的错误的原因：Spirit：1）精神 2）烈性酒结论：必须理解才能翻译，而理解需要知识AI的历史回顾（续4）第三阶段（60年代中80年代初）知识工程时代专家系统知识工程知识工程席卷全球各国发展计划：美国星球大战计划英国ALVEY计划法国UNIKA 计划日本五代机计划中国“863”计划AI的历史回顾（续5）第四阶段（80年代中90年代初）新的神经元网络时代BP网（算法），解决了多层网的学习问题Hopfield网，成功求解了货郎担问题存在问题：理论依据解决大规模问题的能力新的动向构造化方法螺旋线分类问题AI的历史回顾（续6）第五阶段（90年代初现在）数据与网络时代网络给AI带来无限的机会知识发现与数据挖掘AI走向实用化AI的研究内容搜索技术知识表示规划方法机器学习认知科学AI的研究内容（续1）自然语言理解与机器翻译专家系统与知识工程定理证明博弈机器人数据挖掘与知识发现人机交互技术IBM的“深蓝”北京时间1997年5月12日凌晨4点50分，美国纽约公平大厦，当IBM公司的“深蓝”超级电脑将棋盘上的一个兵走到C4的位置上时，国际象棋世界冠军卡斯帕罗夫对“深蓝”的人机大战落下帷幕，“深蓝”以3.5：2.5的总比分战胜卡斯帕罗夫。IBM的“深蓝”（续1）96年2月第一次比赛结果：“深蓝”：胜、负、平、平、负、负97年5月第二次比赛结果：“深蓝”：负、胜、平、平、平、胜IBM的“深蓝”（续2）“深蓝”的技术指标：32个CPU每个CPU有16个协处理器每个CPU有256M内存每个CPU的处理速度为200万步/秒本课主要学习的内容产生式系统搜索技术盲目搜索方法启发式搜索方法与/或图搜索方法博弈树搜索方法AI中的谓词演算及应用知识表示简介AI中的其它技术介绍第一章 产生式系统1943年Post首先在一种计算形式体系中提出60年代开始，成为专家系统的最基本的结构形式上很简单，但在一定意义上模仿了人类思考的过程1.1 产生式系统的基本组成组成三要素：一个综合数据库存放信息一组产生式规则知识一个控制系统规则的解释或执行程序 （控制策略）1.2 产生式系统的基本过程过程PRODUCTION1，DATA初始数据库2，until DATA满足结束条件，do3，4，在规则集中选择一条可应用于DATA 的规则R5，DATA R应用到DATA得到的结果6，一个简单的例子问题：设字符转换规则ABCACDBCGBEFDE已知：A，B求：F一个简单的例子（续1）一、综合数据库x，其中x为字符二、规则集1，IF AB THEN C2，IF AC THEN D3，IF BC THEN G4，IF BE THEN F5，IF D THEN E一个简单的例子（续2）三、控制策略顺序排队四、初始条件A，B五、结束条件Fx求解过程数据库可触发规则被触发规则A，B（1）（1）A，B，C（2）（3）（2）A，B，C，D（3）（5）（3）A，B，C，D，G（5）（5）A，B，C，D，G，E（4）（4）A，B，C，D，G，E，F1，IF AB THEN C 2，IF AC THEN D3，IF BC THEN G 4，IF BE THEN F5，IF D THEN E1.3 问题表示举例例1：传教士与野人问题（M-C问题）问题：N个传教士，N个野人，一条船，可同时乘坐k个人，要求在任何时刻，在河的两岸，传教士人数不能少于野人的人数。问：如何过河。以N=3，k=2为例求解。M-C问题（续1）左岸 右岸 L R L R m 3 0 m 0 3 c 3 0 c 0 3 B 1 0 B 0 1M-C问题（续2）1，综合数据库 （m,c,b)，其中：0m,c3,b 0,12，初始状态 （3，3，1）3，目标状态（结束状态）（0，0，0）M-C问题（续3）4，规则集IF(m,c,1)THEN(m-1,c,0)IF(m,c,1)THEN(m,c-1,0)IF(m,c,1)THEN(m-1,c-1,0)IF(m,c,1)THEN(m-2,c,0)IF(m,c,1)THEN(m,c-2,0)M-C问题（续4）IF(m,c,0)THEN(m+1,c,1)IF(m,c,0)THEN(m,c+1,1)IF(m,c,0)THEN(m+1,c+1,1)IF(m,c,0)THEN(m+2,c,1)IF(m,c,0)THEN(m,c+2,1)5，控制策略：（略）M-C问题（第二种方法）4，规则集：IF(m,c,1)AND 1 i+j2 THEN(m-i,c-j,0)IF(m,c,0)AND 1 i+j2 THEN(m+i,c+j,0)猴子摘香蕉问题abc猴子摘香蕉问题（续1）1，综合数据库（M,B,Box,On,H）M：猴子的位置B：香蕉的位置Box：箱子的位置On=0：猴子在地板上On=1：猴子在箱子上H=0：猴子没有抓到香蕉H=1：猴子抓到了香蕉猴子摘香蕉问题（续2）2，初始状态（c,a,b,0,0）3，结束状态（x1,x2,x3,x4,1）其中x1x4为变量。猴子摘香蕉问题（续3）4，规则集r1:IF (x,y,z,0,0)THEN (w,y,z,0,0)r2:IF (x,y,x,0,0)THEN (z,y,z,0,0)r3:IF (x,y,x,0,0)THEN (x,y,x,1,0)r4:IF (x,y,x,1,0)THEN (x,y,x,0,0)r5:IF (x,x,x,1,0)THEN (x,x,x,1,1)其中x,y,z,w为变量1.4 产生式系统的类型正向、逆向、双向产生式系统可交换的产生式系统可分解的产生式系统第二章 产生式系统的搜索策略内容：状态空间的搜索问题。搜索方式：盲目搜索启发式搜索关键问题：如何利用知识，尽可能有效地找到问题的解（最佳解）。产生式系统的搜索策略（续1）S0Sg产生式系统的搜索策略（续2）讨论的问题：有哪些常用的搜索算法。问题有解时能否找到解。找到的解是最佳的吗？什么情况下可以找到最佳解？求解的效率如何。2.1 回溯策略例：皇后问题()()Q(1,1)()QQ(1,1)(1,1)(2,3)()Q(1,1)(1,1)(2,3)()QQ(1,1)(1,1)(2,3)(1,1)(2,4)()QQ(1,1)(1,1)(2,3)(1,1)(2,4)Q(1,1)(2,4)(3.2)()QQ(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)()Q(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,2)(2,4)()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,2)(2,4)Q(1,2)(2,4)(3,1)()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,2)(2,4)Q(1,2)(2,4)(3,1)Q(1,2)(2,4)(3,1)(4,3)递归的思想从前有座山 从前有座山 从前有座山递归的思想（续）当前状态目标状态g回溯搜索算法BACKTRACK（DATA）DATA：当前状态。返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。回溯搜索算法递归过程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,R:=FIRST(RULES);6,RULES:=TAIL(RULES);7,RDATA:=GEN(R,DATA);8,PATH:=BACKTRACK(RDATA);9,IF PATH=FAIL GO LOOP;10,RETURN CONS(R,PATH);存在问题及解决办法问题：深度问题死循环问题解决办法：对搜索深度加以限制记录从初始状态到当前状态的路径回溯搜索算法1BACKTRACK1（DATALIST）DATALIST：从初始到当前的状态表（逆向）返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。回溯搜索算法11,DATA:=FIRST(DATALIST)2,IF MENBER(DATA,TAIL(DATALIST)RETURN FAIL;3,IF TERM(DATA)RETURN NIL;4,IF DEADEND(DATA)RETURN FAIL;5,IF LENGTH(DATALIST)BOUND RETURN FAIL;6,RULES:=APPRULES(DATA);7,LOOP:IF NULL(RULES)RETURN FAIL;8,R:=FIRST(RULES);回溯搜索算法1（续）9,RULES:=TAIL(RULES);10,RDATA:=GEN(R,DATA);11,RDATALIST:=CONS(RDATA,DATALIST);12,PATH:=BACKTRCK1(RDATALIST)13,IF PATH=FAIL GO LOOP;14,RETURN CONS(R,PATH);一些深入的问题失败原因分析、多步回溯QQ一些深入问题（续）回溯搜索中知识的利用基本思想：尽可能选取划去对角线上位置数最少的。QQQQ4 3 3 42.2 图搜索策略问题的引出回溯搜索：只保留从初始状态到当前状态的一条路径。图搜索：保留所有已经搜索过的路径。一些基本概念节点深度：根节点深度=0其它节点深度=父节点深度+10123一些基本概念（续1）路径设一节点序列为(n0,n1,nk)，对于i=1,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。一些基本概念（续1）扩展一个节点生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。一般的图搜索算法1,G=G0(G0=s),OPEN:=(s);2,CLOSED:=();3,LOOP:IF OPEN=()THEN EXIT(FAIL);4,n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED);5,IF GOAL(n)THEN EXIT(SUCCESS);6,EXPAND(n)mi,G:=ADD(mi,G);一般的图搜索算法（续）7,标记和修改指针：ADD(mj,OPEN),并标记mj到n的指针；计算是否要修改mk、ml到n的指针；计算是否要修改ml到其后继节点的指针；8,对OPEN中的节点按某种原则重新排序；9,GO LOOP；节点类型说明.mjmkml2.3 无信息图搜索过程深度优先搜索宽度优先搜索深度优先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IF OPEN=()THEN EXIT(FAIL);3,n:=FIRST(OPEN);4,IF GOAL(n)THEN EXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,IF DEPTH(n)Dm GO LOOP;7,EXPAND(n)mi,G:=ADD(mi,G);8,IF 目标在mi中 THEN EXIT(SUCCESS);9,ADD(mj,OPEN),并标记mj到n的指针;10,GO LOOP;2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 6123456789abcd1 2 3 8 47 6 5目标深度优先搜索的性质一般不能保证找到最优解当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制最坏情况时，搜索空间等同于穷举与回溯法的差别：图搜索是一个通用的与问题无关的方法宽度优先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IF OPEN=()THEN EXIT(FAIL);3,n:=FIRST(OPEN);4,IF GOAL(n)THEN EXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)mi,G:=ADD(mi,G);7,IF 目标在mi中 THEN EXIT(SUCCESS);8,ADD(OPEN,mj),并标记mj到n的指针;9,GO LOOP;2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 51256731 2 3 8 47 6 5目标82 3 41 8 7 6 54宽度优先搜索的性质当问题有解时，一定能找到解当问题为单位耗散值，且问题有解时，一定能找到最优解方法与问题无关，具有通用性效率较低属于图搜索方法2.4 启发式图搜索利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。启发信息的强度强：降低搜索工作量，但可能导致找不到最 优解弱：一般导致工作量加大，极限情况下变为 盲目搜索，但可能可以找到最优解希望：引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。基本思想定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。1，启发式搜索算法A（A算法）评价函数的格式：f(n)=g(n)+h(n)f(n)：评价函数h(n)：启发函数符号的意义g*(n)：从s到n的最短路径的耗散值h*(n)：从n到g的最短路径的耗散值f*(n)=g*(n)+h*(n)：从s经过n到g的最短路径的耗散值g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值A算法1,OPEN:=(s),f(s):=g(s)+h(s);2,LOOP:IF OPEN=()THEN EXIT(FAIL);3,n:=FIRST(OPEN);4,IF GOAL(n)THEN EXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)Mi,计算f(n,mi):=g(n,mi)+h(mi);A算法（续）ADD(mj,OPEN),标记mj到n的指针；IF f(n,mk)f(mk)THEN f(mk):=f(n,mk),标记mk到n的指针；IF f(n,ml)f*(s)。A*算法的性质（续2）引理2.2：A*结束前，OPEN表中必存在f(n)f*(s)。A*算法的性质（续3）定理2：对无限图，若从初始节点s到目标节点t有路径存在，则A*一定成功结束。A*算法的性质（续4）推论2.1：OPEN表上任一具有f(n)h1(n)，则在具有一条从s到t的路径的隐含图上，搜索结束时，由A2所扩展的每一个节点，也必定由A1所扩展，即A1扩展的节点数至少和A2一样多。简写：如果h2(n)h1(n),则A1扩展的节点数A2扩展的节点数3，A*算法的改进问题的提出：因A算法第6步对ml类节点可能要重新放回到OPEN表中，因此可能会导致多次重复扩展同一个节点，导致搜索效率下降。s(10)A(1)B(5)C(8)G 目标631118一个例子：OPEN表CLOSED表s(10)s(10)A(7)B(8)C(9)A(7)s(10)B(8)C(9)G(14)A(5)C(9)G(14)C(9)G(12)B(7)G(12)A(4)G(12)G(11)B(8)s(10)A(5)B(8)s(10)C(9)A(5)s(10)B(7)C(9)s(10)A(4)B(7)C(9)s(10)出现多次扩展节点的原因在前面的扩展中，并没有找到从初始节点到当前节点的最短路径，如节点A。解决的途径对h加以限制能否对h增加适当的限制，使得第一次扩展一个节点时，就找到了从s到该节点的最短路径。对算法加以改进能否对算法加以改进，避免或减少节点的多次扩展。改进的条件可采纳性不变不多扩展节点不增加算法的复杂性对h加以限制定义：一个启发函数h，如果对所有节点ni和nj，其中nj是ni的子节点，满足h(ni)-h(nj)c(ni,nj)h(t)=0则称h是单调的。h(ni)ninjh(nj)c(ni,nj)h单调的性质定理5：若h(n)是单调的，则A*扩展了节点n之后，就已经找到了到达节点n的最佳路径。即：当A*选n扩展时，有g(n)=g*(n)。h单调的性质（续）定理6：若h(n)是单调的，则由A*所扩展的节点序列其f值是非递减的。h单调的例子8数码问题：h为“不在位”的将牌数 1h(ni)-h(nj)=0(nj为ni的后继节点)-1 h(t)=0c(ni,nj)=1 满足单调的条件。对算法加以改进一些结论：OPEN表上任以具有f(n)f*(s)的节点定会被扩展。A*选作扩展的任一节点，定有f(n)f*(s)。改进的出发点OPEN=()f*(s)f值小于f*(s)的节点f值大于等于f*(s)的节点fm：到目前为止已扩展节点的最大f值，用fm代替f*(s)修正过程A1,OPEN:=(s),f(s)=g(s)+h(s),fm:=0;2,LOOP:IF OPEN=()THEN EXIT(FAIL);3,NEST:=ni|f(ni)a b(z)(x)(y)(P(x)Q(x)R(y)U(z)2,移动否定符理论根据：(a b)=a b (a b)=a b(x)P(x)=(x)P(x)(x)P(x)=(x)P(x)(z)(x)(y)(P(x)Q(x)R(y)U(z)化子句集的方法（续1）3,变量标准化即：对于不同的约束，对应于不同的变量(x)A(x)(x)B(x)=(x)A(x)(y)B(y)4,量词左移(x)A(x)(y)B(y)=(x)(y)A(x)B(y)5,消存在量词(skolem化）原则：对于一个受存在量词约束的变量，如果他不受全程量词约束，则该变量用一个常量代替，如果他受全程量词约束，则该变量用一个函数代替。(z)(x)(y)(P(x)Q(x)R(y)U(z)=(x)(P(x)Q(x)R(f(x)U(a)化子句集的方法（续2）6,化为合取范式即(ab)(cd)(ef)的形式 (x)(P(x)Q(x)R(f(x)U(a)=(x)(P(x)Q(x)R(f(x)U(a)=(x)P(x)R(f(x)U(a)Q(x)R(f(x)U(a)7,隐去全程量词 P(x)R(f(x)U(a)Q(x)R(f(x)U(a)化子句集的方法（续3）8,表示为子句集 P(x)R(f(x)U(a),Q(x)R(f(x)U(a)9,变量标准化（变量换名）P(x1)R(f(x1)U(a),Q(x2)R(f(x2)U(a)定理：若S是合式公式F的子句集，则F永假的充要条件是S不可满足。S不可满足：若nilS，则S不可满足。证明的思路：目标的否定连同已知条件一起，化为子句集，并给出一种变换的方法，使得 S S1 S2.Sn同时保证当Sn不可满足时，有S不可满足。4.2 归结方法（命题逻辑）设子句：C1=LC1C2=(L)C2则归结式C为：C=C1 C2定理：子句集S=C1,C2,Cn与子句集S1=C,C1,C2,Cn的不可满足性是等价的。其中，C是C1和C2的归结式。归结的例子设公理集：P,(PQ)R,(ST)Q,T求证：R子句集：(1)P(2)PQR(3)SQ(4)TQ(5)T(6)R（目标求反）化子句集：(PQ)R=(PQ)R=PQR(ST)Q=(ST)Q=(ST)Q=(SQ)(TQ)=SQ,TQ子句集：(1)P(2)PQR(3)SQ(4)TQ(5)T(6)R（目标求反）归结：(7)PQ (2,6)(8)Q (1,7)(9)T (4,8)(10)nil (5,9)4.3 谓词逻辑的归结原理问题：如何找归结对例：P(x)Q(y),P(f(y)R(y)P(A)Q(y),P(f(y)R(y)基本概念置换s=t1/v1,t2/v2,tn/vn对公式E实施置换s后得到的公式称为E的例，记作Es。例：s1=z/x,Ay,则：Px,f(y),Bs=Pz,f(A),B合一如果存在一个S置换，使得Ei中 E1s=E2s=E3s=Ens，则称Ei是可合一的。S为Ei的合一者。例：P(x,f(y),B),P(z,f(B),B)置换s=A/x,B/y,A/z是一个合一者,因为：P(x,f(y),B)s=P(A,f(B),B)P(z,f(B),B)s=P(A,f(B),B)置换s=z/x,B/y和置换s=x/z,B/y也都是合一者。结论：合一者不唯一。最一般合一者（mgu）置换最少，限制最少，产生的例最具一般性。如前面的例子：P(x,f(y),B),P(z,f(B),B)对于置换A/x,B/y,A/z，产生的例是：P(A,f(B),B)对于置换=z/x,B/y，产生的例是：P(z,f(B),B)mgu也不是唯一的。合一算法例：P(x,x,B),P(f(y),f(B),y)前缀表示：(P x x z)(P(f y)(f B)y)置换：(f y)/x(P(f y)(f y)z)(P(f y)(f B)y)置换：B/y,并使得(f B)/x(P(f B)(f B)z)(P(f B)(f B)B)置换：B/z得到置换：(f B)/x，B/y，B/z置换后的结果：(P(f B)(f B)B)谓词逻辑的归结方法对于子句C1L1和C2L2，如果L1与L2可合一，且s是其合一者，则(C1C2)s是其归结式。例：P(x)Q(y),P(f(z)R(z)=Q(y)R(z)归结举例设公理集：(x)(R(x)L(x)(x)(D(x)L(x)(x)(D(x)I(x)求证：(x)(I(x)R(x)化子句集：(x)(R(x)L(x)=(x)(R(x)L(x)=R(x)L(x)(1)(x)(D(x)L(x)=(x)(D(x)L(x)=D(x)L(x)(2)(x)(D(x)I(x)=D(A)I(A)=D(A)(3)I(A)(4)目标求反：(x)(I(x)R(x)=(x)(I(x)R(x)=(x)(I(x)R(x)=I(x)R(x)(5)换名后得字句集：R(x1)L(x1)D(x2)L(x2)D(A)I(A)I(x5)R(x5)例题得归结树R(x1)L(x1)D(x2)L(x2)D(A)I(A)I(x5)R(x5)I(A)I(x5)R(x5)R(A)A/x5 R(x1)L(x1)L(A)A/x1 D(x2)L(x2)D(A)A/x2 D(A)nil4.4 基于归结的问答系统例：已知：(x)AT(John,x)AT(Fido,x)AT(John,School)求证：(x)AT(Fido,x)子句集：AT(John,x1)AT(Fido,x1)AT(John,School)AT(Fido,x2)AT(Fido,x2)AT(John,x1)AT(Fido,x1)子句集：AT(John,x1)AT(Fido,x1)AT(John,School)AT(Fido,x2)AT(John,x2)x2/x1AT(John,School)nilSchool/x2AT(Fido,x2)AT(Fido,x2)AT(Fido,School)提取回答的过程先进行归结，证明结论的正确性；用重言式代替结论求反得到的子句；按照证明过程，进行归结；最后，在原来为空的地方，得到的就是提取的回答。修改后的证明树称为修改证明树例：猴子摘香蕉问题c问题的表示已知：1,ON(s0)2,(x)(s)(ON(s)AT(box,x,push(x,s)3,(s)(ON(climb(s)4,(s)(ON(s)AT(box,c,s)HB(grasp(s)5,(x)(s)(AT(box,x,s)AT(box,x,climb(s)求解：(s)HB(s)问题的子句集1,ON(s0)2,ON(s1)AT(box,x1,push(x1,s1)3,ON(climb(s2)4,ON(s3)AT(box,c,s3)HB(grasp(s3)5,AT(box,x4,s4)AT(box,x4,climb(s4)6,HB(s5)返回HB(s5)ON(s3)AT(box,c,s3)HB(grasp(s3)ON(s3)AT(box,c,s3)grasp(s3)/s5ON(climb(s2)climb(s2)/s3 AT(box,c,climb(s2)ON(s0)ON(s1)AT(box,x1,push(x1,s1)s0/s1AT(box,x1,push(x1,s0)AT(box,x4,s4)AT(box,x4,climb(s4)x4/x1,push(x4,s0)/s4AT(box,x4,climb(push(x4,s0)NILc/x4,push(c,s0)/s2HB(s5)HB(grasp(s3)HB(grasp(climb(s2)HB(grasp(climb(push(c,s0)归结方法小结求子句集，进行归结，方法简单通过修改证明树的方法，提取回答方法通用求解效率低，不宜引入启发信息不宜理解推理过程4.5 基于规则的正向演绎系统问题：归结方法不自然可能会丢失蕴涵关系中所包含的控制信息例：以下蕴涵式：A B CC A BA C BA C BB C A B A C均与子句(A B C)等价，但显然上面的蕴涵式信息更丰富。事实表达式的与或形及其表达与或形无量词约束否定符只作用于单个文字只有“与”、“或”例：(u)(v)(Q(v,u)(R(v)P(v)S(u,v)=(u)(v)(Q(v,u)(R(v)P(v)S(u,v)=Q(v,A)(R(v)P(v)S(A,v)Skolem化=Q(w,A)(R(v)P(v)S(A,v)主合取元变量换名事实的与或树表示例：Q(w,A)(R(v)P(v)S(A,v)Q(w,A)(R(v)P(v)S(A,v)Q(w,A)(R(v)P(v)S(A,v)R(v)P(v)S(A,v)R(v)P(v)解图集：Q(w,A),R(v)S(A,v),P(v)S(A,v)应用规则对与或图作变换对规则的形式：L W其中，L是单文字，W是与或形，变量受全称量词约束例：(x)(y)(z)P(x,y,z)(u)Q(x,u)=(x)(y)(z)P(x,y,z)(u)Q(x,u)=(x)(y)(z)P(x,y,z)(u)Q(x,u)=(x)(y)(z)(u)(P(x,y,z)Q(x,u)=P(x,y,f(x,y)Q(x,u)=P(x,y,f(x,y)Q(x,u)=P(x1,y1,f(x1,y1)Q(x1,u1)换名例：(L1 L2)W=L1 W 和 L2 W 命题逻辑的情况例：事实：(P Q)R)(S (T U)规则：S (X Y)Z(P Q)R)(S (T U)(P Q)R S (T U)P Q R ST UPQTUSX YZX YP Q SP Q T US RR T UP Q X ZP Q Y ZR X ZR Y Z规则的子句：S (X Y)Z=S(X Y)Z=S X Z S Y Z结论：加入规则后得到的解图，是事实与规则对应子句的归结式例：事实：A B规则集：A C D B E G目标公式：C GA BABACDBEGCG目标谓词逻辑的情况事实表达式化成与或形规则化成L W的形式，其中L为单文字目标用Skolem 化的对偶形式，即消去全称量词，用Skolem函数代替保留存在量词对析取元作变量换名例：(y)(x)(P(x,y)Q(x,y)=(y)(P(f(y),y)Q(f(y),y)=P(f(y1),y1)Q(f(y2),y2)换名规则每使用一次，都要进行一次换名例：事实：P(x,y)(Q(x,A)R(B,y)规则集：P(A,B)(S(A)X(B)Q(B,A)U(A)R(B,B)V(B)目标：S(A)X(B)U(A)V(B)P(x,y)(Q(x,A)R(B,y)P(x,y)Q(x,A)R(B,y)Q(x,A)R(B,y)P(A,B)A/x,B/yS(A)X(B)Q(B,A)B/xU(A)R(B,B)B/yV(B)一致解图如果一个解图中所涉及的置换是一致的，则该解图称为一致解图。设有置换集u1,u2,un,其中:ui=ti1/vi1,tin/vin，定义表达式：U1=(v1,1,v1,m1,vn,1,vn,mn)U2=(t1,1,t1,m1,tn,1,tn,mn)置换集u1,u2,un称为一致的，当且仅当U1和U2是可合一的。U1、U2的mgu是u1,u2,un的合一复合。置换集的合一复合运算是可结合和可交换的。一致置换举例举例事实：D(F)(B(F)I(F)规则：R1:D(x)T(x)R2:B(y)N(y)目标：T(u)N(v)D(F)(B(F)I(F)D(F)B(F)I(F)B(F)I(F)D(x)F/xT(F)R1T(u)F/uB(y)F/yN(F)R2N(v)F/v目标目标U1=(x,u,y,v)U2=(F,F,F,F)合一复合u：F/x,F/u,F/y,F/v作用于目标：T(u)N(v)u=T(F)N(F)正向演绎系统小结事实表达式为与或形规则形式：L W,其中L为单文字目标公式为文字析取对事实和规则进行Skolem化，消去存在量词，变量受全称量词约束，对主合取元和规则中的变量换名用“对偶形”对目标进行Skolem化，消去全称量词，变量受存在量词约束，对析取元中的变量换名事实表达成与或树，其中，“”对应树中“与”，“”对应树中“或”从事实出发，正向应用规则，到得到目标节点为结束的一致解图为止存在合一复合时，则解图是一致的4.6 基于规则的逆向演绎系统目标为任意形的表达式用“对偶形”对目标进行Skolem化，即消去全称量词，变量受存在量词约束，对主析取元中的变量换名目标用与或树表示，其中，“”对应树中“与”，“”对应树中“或”事实表达式是文字的合取规则形式：L W,其中W为单文字，如形为：L W1 W2，则变换为：L W1 和 L W2从目标出发，逆向应用规则，到得到事实节点为结束条件的一致解图为止例：事实：D(F)B(F)W(F)M(N)规则：R1:(W(x1)D(x1)F(x1)R2:(F(x2)B(x2)A(y2,x2)R3:D(X3)A(x3)R4:C(x4)A(x4)R5:M(x5)C(x5)目标：C(x)D(y)A(x,y)C(x)D(y)A(x,y)C(x)D(y)A(x,y)C(x5)x/x5M(x)R5M(N)N/xD(F)F/yA(y2,x2)x/y2,y/x2F(y)B(y)R2B(F)F/yF(x1)y/x1W(y)D(y)R1W(F)F/yD(F)F/y一致性检查置换集x/x5,N/x,F/y,x/y2,y/x2,F/y,y/x1,F/y,F/yU1=(x5,x,y,y2,x2,y,x1,y,y)U2=(x,N,F,x,y,F,y,F,F)合一复合N/x5,N/x,F/y,N/y2,F/x2,F/x1目标得到的解答 C(x)D(y)A(x,y)=C(N)D(F)A(N,F)4.7 一些深入的问题修剪不一致的局部解图建立规则连接图结构规则的多次调用规则的递归调用加快匹配的速度4.8 正、逆向系统对比事实表达式任意形规则形式：单文字 W目标公式为文字析取对事实、规则消存在量词，Skolem化用对偶形消目标的全称量词，Skolem化事实表达式与或树，“”对“与”，“”对应“或”从事实出发，正向应用规则以目标为结束的一致解图事实表达式是合取形规则形式：L 单文字目标公式任意形对事实、规则消存在量词，Skolem化用对偶形消目标的全称量词，Skolem化目标公式的与或树，“”对“与”，“”对应“或”从目标出发，逆向应用规则以事实为结束的一致解图结束 第五章 一个面向AI的C程序环境问题的提出本章主要内容环境的实现原理一些实例可改进的地方学习要求读程序有条件的话，自己写些程序希望提出一些改进意见不要束缚住自己一些基本概念原子文字原子(符号)：abc,sin 数字原子：15,12.3表(a b c),(10 20 30),(a(1 23),(a b)(c d)S-表达式原子和表统称为S-表达式表头和表尾(a)：头=a，尾=NULL/()(a b c)：头=a，尾=(b c)(a b)(c d)：头=(a b)，尾=(c d)表结构示意图基本结构：表头表尾例：(a),头=a，尾=()a例：(a b),头=a，尾=(b)ab例：(a b)(10 20),头=(a b)，尾=(10 20)ab 1020(10 20)(10 20)(a b)例：(a b)10 20),头=(a b)，尾=(10 20)ab 1020(10 20)(a b)基本数据结构typedef struct node/*节点结构*/char mark;/*无用单元收集标志，暂不说明*/union struct node*node_ptr;char*string;int i;float f;head;/*表头*/union struct node*t;P_FUNC p;tail;/*表尾*/char type;/*类型标记*/NODE;type域说明 f:head.f为符点数 i:head.i为整数 c:head.string为常量字符串指针,tail.t为属性表 v:head.string为变量字符串指针,tail.t为属性表 l:节点为表,head.node_ptr为表头,tail.t为表尾 p:tail.p为函数指针,head.string为函数名 内存管理 node_buffNODE_BUFF_NUM:node区数组 node_num_in_buff:一个node区含有的单元数 free_node_list:自由单元表 string_buff:文字原子名存储空间.abc0def0sin0sum0 string0 string_buff_ptrstring_buff_end无用单元收集为什么进行无用单元收集局部变量引起变量指针改变例：p指向(a b c)改为指向(d e f)后，如果再没有其他指针指向(a