人工智能一纸开卷

1、绪论：人工智能：计算机科学，控制论，信息论，神经生理学，心理学，语言学等多种学科相互渗透而发展起来的一门综合性学科。研究如何运用知识，以便象人类一样完成富有智能的工作人工智能的本质：是一门研究如何制造出人造的智能机器或者智能系统，来模拟人类智能活动的能力，以延伸人们智能的科学图灵测试：计算机和测试者分别在两个房间且测试者看不到，测试者通过提问，判断哪个房间是志愿者，哪个房间是计算机.如果测试者在一系列的这种测试中，不能准确的判断出谁是计算机，谁是人，则说明该计算机通过了图灵测试，具有了图灵测试意义下的智能（提问题由计算情感（机器不会烦躁）两方面来提）人工智能研究的基本内容：搜索技术、知识表示、

2、规划方法、机器学习、认知科学、自然语言理解和机器翻译、专家系统与知识工程、定理证明、搏弈、机器人、数据挖掘与知识发现、多agent系统、复杂系统、足球机器人、人机交互人工智能的发展阶段：第一阶段：萌芽期（1956年以前）第二阶段：形成期（1956年-1961年）第三阶段：发展期（1961年-1980年）第四阶段：新的神经元网时代（80年代初-90年代初）第五阶段：（90年代初-现在）产生式系统：产生式（规则）：用于表示事物间的因果关系（也是前提和结论之间的关系）产生式的一般形式：IF相提/条件THEN咨论/行动或者简写为：前提结论注：前提或条件部分可以是一些事实的合取或析取，结论是某一事实。后

3、件由前件来触发。一个产生式生成的结论可以作为另一个产生式的前提。产生式系统定义：大多数专家系统都是以产生式表示知识，把一组产生式放在一起，让它们相互配合，协同的工作，一个产生式生成的结论可以供另一个产生式作为前提使用，以这种方式求得问题的解的系统叫做产生式系统。产生式系统的结构：组成三要素。1一个综合数据库（存放信息）（2组产生式规则（规则库）（知识）一个控制系统（推理机）-规则的解释或执行程序（控制策略）推理机：1.按照一定策略从规则库中选择规则与数据库的已知事实进行匹配。在匹配中，出现下面三种情况。1匹配成功，则此规则将列入被激活侯选集（冲突集）C2匹配失败，即输入条件与已知条件矛盾，则此

4、条规则被完全放弃，今后不予考虑。匹配无结果，即规则前件与输入事实无关，该规则被放入待测试规则集。2.当匹配成功的规则多于一条时，需要从匹配成功的规则中选出一个加以执行，即根据一定的策略解消冲突（例如选择编号最小的）3.解释执行规则后件的动作。如果该规则的后件不是问题的目标，将其加入数据库中。如果这些后件是一个或者多个操作时，根据一定的策略，有选择有顺序的执行。4.掌握结束产生式系统运行的时机。对要执行的规则，如果该规则的后件满足问题的结束条件，则停止推理。字符转换的例子（手写）产生式系统的推理：正向推理反向推理双向推理产生式系统的特点：数据驱动、知识的无序性、控制系统与问题无关、数据、知识和控

5、制相互独立语义网络：是用实体及其语义关系来表示知识的知识表示方法，由最基本的语义单元组成（称为:语义基元）;由多个语义基元用相应的语义联系关联在一起形成一个语义网络语义基元（手写）:结点代表实体，弧是有方向和标注的：方向体现了结点所代表的实体的主次关系即结点1为主，结点2为辅,弧上的标注表示了它所连接的两个实体之间的语义联系产生式系统的搜索策略：搜索策略的主要任务：确定如何选取规则的方式盲目搜索方法：不考虑给定问题具有的特定知识，系统根据事先确定好的某种固定排序，依次调用规则或者随机调用规则启发式搜索方法：考虑问题领域可应用的知识，动态地确定规则的排序，优先调用较合适的规则搜索问题：如何在一个

6、比较大的问题空间中，只通过搜索比较小的范围，就找到问题的解回溯策略(属于盲目搜索):首先将规则给出固定的排序，在搜索时，1)对当前状态依次测每一条规则，在当前状态未使用的规则中找到第一条可应用的规则，应用于当前状态，得到的新的状态重新设置为当前状态，并重复以上搜索。2)如果当前状态无规则可用，或所有规则都已经试探过，仍未找到问题的解，则将当前状态的前一个状态设置为当前状态3)重复以上搜索，直到找到问题的解，或者找不到问题的解。回溯策略算法：递归过程BACKTRACK(DATA)1, IFTERM(DATA)RETURNNIL;/data满足条件返回空表2, IFDEADEND(DATA)RET

7、URNFAIL;似口果状态不合法返回fall必须回溯3, RULESkAPPRULES(DATA);APPRULESDATA的可应用规贝U集以某种原贝U排序后赋给RULES4, LOOP:IFNULL(RULES)RETURNFAIL;/隹部规则应用均失败，回溯5, R:=FIRST(RULES);取第一条可应用规则6, RULESkTAIL(RULES)删除第一条规贝U7, RDATA:=GEN(R,DATA);M据规贝UR与DATA生成新状态RDATA8, PATHkBACKTRACK(RDATA对新状态递归调用本过程9, IFPATH=FAILGOLOOP;/递归调用失败，则转移调用另一

8、规则进行测试10, RETURNCONS(R,PATH);边程返回解路径规则表(或局部解路径字表)两个回溯点分别在2、4存在的问题：分支具有无穷个状态，算法可能会落入某个“深渊”，永远也回溯不回来。2某一分支具有环路进入死循环解决办法：。对搜索深度加以限制。2记录从初始状态到当前状态的路径。即增加两个回溯点。DATALIST从初始到当前的状态表(逆向)初始状态排在表的最后，当前状态排在最前返回值：从当前状态到目标状态的路径(以规则表的形式表示)或FAILBACKTRACK1(DATALIST1, ,DATA:=FIRST(DATALIST)2, IFMENBER(DATA,TAIL(DATAL

9、IST如果DATA在DATALIS伸存在表示有回路必须回溯RETURNFAIL;/TALL是取表尾操作3, IFTERM(DATA)RETURNNIL;4, IFDEADEND(DATA)RETURNFAIL;5, IFLENGTH(DATALIST)>BOUNDt索长度大于给定值BOUND时回溯RETURNFAIL;6, RULES:=APPRULES(DATA);7, LOOP:IFNULL(RULES)RETURNFAIL;8, R:=FIRST(RULES);9, RULES:=TAIL(RULES);10, RDATA:=GEN(R,DATA);11, RDATALIST:=C

10、ONS(RDATA,DATALIS将新状态力口入至U表DATALIST12, PATH:=BACKTRCK1(RDATALIST表递归调用本过程13, IFPATH=FAILGOLOOP;14, RETURNCONS(R,PATH);回溯策略一举例：四皇后问题(手写)图搜索策略：因为回溯搜索只保留从初始状态到当前状态的一条路径，节省存储空间但被回溯掉的已经搜索过的部分，不能被以后利用。所以引出图搜索：保留所有已经搜索过的路径基本概念：根节点深度=0;路径：即n0到nk的结点序列；路径耗散值：一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散

11、值；扩展一个节点：生成该节点的所有后继节点，并给出他们之间的耗散值。一般的图搜索算法：1, G=G0(G0=s),OPEN:=(s);/G图；s-初始结点；设置open表最初只含s2, CLOSED:=();3, LOOP:IFOPEN=()THENEXIT(FAIL);4, n:=FIRST(OPEN),REMOVE(n,OPEN),/当前节点ADD(n,CLOSED);5, IFGOAL(n)THENEXIT(SUCCESS成/功返回n至Us的路径指针，可给出解路径6, EXPAND(n户mi,G:=ADD(mi,G);扩展当前结点，否则不能向下求解7,标记和修改指针：/mj为open表和

12、closed表中均未出现过的点ADD(mj,OPEN),并标记mj到n的指针；/mk已出现在open表中的子节点计算是否要修改mk、ml到n的指针；/ml已出现在closed表中的子节点计算是否要修改ml到其后继节点的指针；8,对OPEN中的节点按某种原则重新排序；9,GOLOOP无信息图搜索：深度优先搜索宽度优先搜索1, G:=G0(G0=s),OPEN:=(s),CLOSED:=();2, LOOP:IFOPEN=()THENEXIT(FAIL);3, n:=FIRST(OPEN);4, IFGOAL(n)THENEXIT(SUCCESS);5, REMOVE(n,OPEN),ADD(n,

13、CLOSED);5',IFDEPTH(n异DmGOLOOP;只在深度优先中存在此步骤6, EXPAND(n)-mi,G:=ADD(mi,G);s7,ADD(mj,OPEN)并标记mj到n的指针;/体现深度优先K7,ADD(OPEN,mj)并标记mj到n的指针;/体现宽度优先8,GOLOOP;深度优先：一般不能保证找到最优解；若不限制深度可能进入深渊宽度优先：当问题有解时一定能找到解；当问题为单位耗散值，且问题有解时，一定能找到最优解。二者均属于图搜索、效率不高、方法于问题无关具有通用性。启发式图搜索：基本思想：定义一个评价函数f,对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。

14、(引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率)启发式搜索算法A算法：评价函数：f(n)=g(n)+h(n)注：f(n):评价函数/h(n)：启发函数/g*(n):从s到n的最短路径的耗散值/h*(n):从n至ijg的最短路径的耗散值/f*(n)=g*(n)+h*(n):从s经过n到g的最短路径的耗散值/g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值算法：1,OPEN:=(s),f(s):=g(s)+h(s);2, LOOP:IFOPEN=()THENEXIT(FAIL);3, n:=FIRST(OPEN);4, IFGOAL(n)TH

15、ENEXIT(SUCCESS);5, REMOVE(n,OPEN),ADD(n,CLOSED);6, EXPAND(n)-mi,计算f(n,mi):=g(n,mi)+h(mi);ADD(mj,OPEN),标记mj到n的指针;最佳图搜索算法若存在初始节点IFf(n,mk)<f(mk)THENf(mk):=f(n,mk),标记mk至ijn的指针；IFf(n,ml)<f(ml,)THENf(ml):=f(n,ml),标记ml到n的指针，ADD(ml,OPEN);/见注7, OPEN中的节点按f值从小到大排序；8, GOLOOPA*：在A算法中，如果满足条件h(n)wh*(n)则A算法称为

16、A*算法。性质s到目标节点t的路径，则A*必能找到最佳解结束。注：A/A*算法在第六步ADD(ml,OPEN);导致多次扩展同一结点。原因:在前面的扩展中，并没有找到从初始节点到当前节点的最短路径。解决途径：G)对h加以限制。2对算法加以改进(未仔细看)与或图搜索：搜索从初始节点到一组终节点集N的一个解图基本概念：C1与或图是一个超图，节点间通过连接符连接。2K-连接符：指向K个后继节点就是k阶连接符。O耗散值的计算：k(n,N)=Cn+k(n1,N)+;耐阳节点集Cn为连接符的耗散值C4若n是N的一个元素，则k(n,N)=0解图的求法是：从节点n开始，正确选择一个外向连接符，再从该连接符所指

17、的每一个后继结点出发，继续选一个外向连接符，如此进行下去直到由此产生的每一个后继节点成为集合N中的一个元素为止。6具有最小耗散值的解图称为最佳解图能解节点(SOLVED®终节点是能解节点。2若非终节点有“或”子节点时，当且仅当其子节点至少有一个能解时，该非终节点才能解。3若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。注：其他情况均为不能解节点与或图的启发式搜索算法AO*:通过评价函数f(n),通过对某一个结点的评价来实现对整个局部图的评价从而选择待扩展的节点(注：普通图：f(n)=g(n)+h(n)表面上是对结点n的评价，实际上是对从s到目标结点(通过n)的

18、这条路径的评价)AO*算法一过程AO*:C1建立一个搜索图G,G:=s,计算q(s)=h(s),IFGOAL(s)THENM(s,SOLVED)©Untils已标记为SOLVED,do:C3Begin0G':=FIND(G)/根据连接符找出一个彳f扩展的局部图G'C5)n:=G中的任一非终节点(选一个非终节点作为当前节点)。®EXPAND(n)生成子节点集ni,其中ni不属于G,G:=ADD(ni,G),计算q(ni)=h(ni),IFGOAL(ni)THENM(ni,SOLVED);/对G中未出现的子结点添加到G中，并计算其耗散值，若有终节点则加能解标记。

19、然后把n的子节点添加到G中S:=n;建立含n的单一节点集合S.(待修正的节点集合)©UntilS为空，do:C9BeginREMOVE(m,S),mc不属于S;这个m的子结点mc应不在S中。初修改m的耗散值q(m):对m指向节点集(n1i,n2i,nki)的每个连接符i分别计算qi,qi(m)=Ci+q(n1i)+q(nki),q(m):=minqi(m);加指针到minqi(m)的连接符上，或把指针修改到minqi(m)的连接符上，即原来指针与新确定的不一致时应删去.IFM（nji,SOLVED）THENM（m,SOLVED）,（j=1,）/若力方k接符的所有子节点都是能解的，则m

20、也标上能解.IFM（m,SOLVED）V（q（m）!=q0（m）THENADD（ma,S）;/m能解或修正的耗散值与原先估算q0不同，则把m的所有先辈节点ma,添加到S中.（修正向上传递）Oend（与9匹配）end（与3匹配）算法分为两个部分：。4-是一个自上而下的图生长过程，先通过有标记的连接符，找到目前为止最好的一个局部解图。7-是一个自下而上的耗散值修正计算，连接符的标记以及结点的能解标记。AO*算法例子见书博弈树搜索：（博弈:双人、一人一步）Grundy博弈（分钱币游戏）：（手写）极小极大搜索过程：假定一个评价函数可以对所有的棋局进行评价，当评价函数>0时，表示对我方有利，越大越

21、有利；当评价函数<0时，表示对对方有利，越小越有利。2极小极大搜索策略是：是考虑双方对弈若干步之后，从可能的走步中选一个相对较好的走法来走，即在有限的搜索深度范围内进行求解。定义静态估计函数f;f>0,表对我方有利，f<0,表对方有利，f=0,表势均力敌；f=正无穷，表我方胜，£=负无穷表对方胜。4过程;端点值用静态函数计算得到，其他节点用倒推法取值（MAX考虑最好情况选最大）算法的三个阶段：用宽度优先法生成规定深度的全部博弈树，然后对其端结点计算其静态估计函数（对应算法234）（2从底向上逐级求非端结点的倒推估计值，直到求出初始结点的倒推值f（s）为止（对应算法6

22、78）再由f（s）选出相对较好的走步算法的一点说明：对手回应后当以当时的态作为起始状态s,重复调用该过程。举例:九宫格棋牌（手写）a-P剪枝:基本思想：把生成和倒推估值结合起来进行，再根据一定的条件判定，有可能尽早剪掉一些无用的分支极大节点的下界为ao极小节点的上界为P口剪枝：若任一极小值层节点的B值M它任一先辈极大值层节点的口值；即后辈节点的P值w祖先节点的a值时，西枝：若任一极大值层节点的u值大于或等于它任一先辈极小值层节点的口值，即a（后继层）P（先辈层）例子见书口串剪枝注意的问题：比较实在极大与极小间进行。2比较是与先辈（已经有了值的节点）比较当只有一个节点的值固定后，其值才能向父结点

23、传递。4：一剪枝与极大极小结果一致。5：-一：剪枝效率高，极大极小效率低谓词逻辑与归结原理：（命题以及公式自己写）归结原理是一种主要基于谓词逻辑知识表示的推理方法。是一种形式语言，具有严密的理论体系Q是一种常用的知识表示方法谓词基本概念：联结词：，A,V,T,H优先级：最优先其次是同级最后T,1同级；同级从左向右计算量词：-，-I子句：如下形式的合式公式（wff）：（Liw,.vLs）每个Li是文字（原子或原子的非）/一些文字的析取（文字：不含任何连接词的谓词公式）子句集：所有子句的集合化子句集的方法：例：3<(p(X)由(p(YAq(YX,f(a)x(p(X)-y(p(Y)，q(YX,

24、f(a)(1)去掉蕴涵理论根据：abab3(p(X)Wy(q(YX,f(a)vp(Y)kH(p(X)冠y(q(YX,f(a)5P(Y)(2)移动否定符，将内移到原子公式前：理论根据：(ab)=a-b(ab)-a-b(x)P(x).(-x)P(x)(-x)P(x>(x)P(x)3(p(X)而(q(YX,f(a)5P(Y)丽(p(X)亘(q(YX,f(a)八p(Y)(3)变量标准化，将各约束变量换名，以避免混淆，即：不同的约束，对应于不同的变量(x)A(x)(x)B(x).(x)A(x)(y)B(y)3(p(X),Ny(q(YX,f(a)v-p(Y)A-u(-p(U)v(q(V,U,f(a)

25、p(V)(4)去掉三(skolem变换)原式为:%p(X)而y(q(YX,f(a)5P(Y)-u(-p(U)v(q(V,U,f(a)p(V)去掉三后：(p(c)-y(q(Yc,f(a)p(Y)u(p(U)(q(h(U),U,f(a)p(h(U)(5)将全称量词提到最前面：所用公式：(B-yA(X)-y(BA(X)VyVu(p(c)Mq(Yc,f(a)v-p(Y)(p(U)(q(h(U),U,f(a)p(h(U)略去全称量词为：(p(c)八(q(Yc,f(a)v-p(Y)A(p(U)(q(h(U),U,f(a)p(h(U)(6)将上式化为合取范式(p(c)八(q(Yc,f(a)5P(Y)a(p(

26、U)(q(h(U),U,f(a)(-p(U)p(h(U)(7)表不为子句的形式p(c),q(Yc,f(a)Mp(Y),-p(U)Vq(h(U),U,f(a),-p(U)Vp(h(U)注:转化不意味着等价性，但可保证其保持“不可满足性”这里h(X)称为Skolem函数.skolem变换：将谓词公式中所有存在量词消去得到该谓词公式的skolem标准型.在消去存在量词时，有两种情况：a.存在量词不在任何全称量词的辖域内例如：x：(X)变为:(c),(注：c必须是一个新的常量，称为skolem常数,不能在原来的a中)b.存在量词在某些全称量词的辖域内，例如：弘三yheight(X,Y)(公式中X依赖于

27、Y)变为"xheight(X,h(X)归结原理：基本思想：将待证明的逻辑公式的结论(F),通过等值公式转换成附加前提(结论取反)，再证明该逻辑公式是不可满足的归结方法：G=LQ'；G=(L)vQ'(消去互补)构成一个新的子句C=G'谓词逻辑中，由于子句中包含有变元，所以不能直接消去互补文字(L和L)所以要做变量的置换和合一置换提形如tl/xi,tn/Xn的有限集淇中Xi是互不相同的变量，ti是不等于X的项，且Xi与ti互不循环出现.若&,则称为空置换(表示不做置换，记为置换就是将Xi替换成ti置换乘法：令日=s1/y1,Sm/ym,仃=t1/X1,tn

28、/Xn,乘法曲的直观含义是先做B,在彳仃.上述乘法仕!的意思、是从S1Hy1,Smcr/ym,t1/X1,tn/Xn中删除：(1)若S1G=yi,则删除Sicr/yi项.(2)若XiW(y1，ym,则删除ti/Xi.所得到的新的置换.比前的，即乘法是不可交换的.合一:公式集S=E1,.石,若存在置换刚日6=E1H，则例为S的一个合一，S称是可合一的最广合一(mgu):如果对S的任意一个合一仃,存在一个置换¥使的审,则称6是S的一个最广合一记为mgu.求最广合一的目的是：使子句集中子句的文字形式结构完全一致，从而达到取消互补文字的目的差异集：合一算法：谓词逻辑的归结举例：是否能进行归结

29、可以通过置换看出设集合：归结图手写(1) (VX)(R(xHL(x)(2) (-x)(D(x)>-L(x)(3) (x)(D(x)I(x)求证：(x)(I(x)R(x)化子句集：(-x)(R(x)>L(x)=>(-x)(-R(x)L(x)去全称量词：R(x)L(x)(2) (-x)(D(x)L(x)=>(-x)(-D(x)L(x)去全称量词：D(x)L(x)(3) (x)(D(x)l(x)Skolem标准化D(A)I(A)H-域即得：D(A)1(A)目标求反：(x)(l(x)R(x)彳#(-x)(I(x)R(x)彳#(-x)(-I(x)R(x)彳#l(x)R(x)换名后

30、的子句集：R(X1)L(X1)-D(X2)L(X2)D(A)1(A)1(X5)R(X5)H-基局部搜索算法：每次运行不能保证最优解，但多次运行后，可以找到满意解。放弃找到最佳解，换取降低时间复杂度组合优化问题：设x是决策变量，D是x的定义域，f(x)是指标函数，g(x)是约束条件集合。则优化问题可以表示为，求解满足g(x)的f(x)最小值问题。如果在定义域D上，满足条件g(x)的解是有限的，则优化问题称为组合优化问题邻域:是一个点附近的其他点的集合注：G)在一个邻域内的最优解称为局部最优解。2在整个定义域上的最优解称为全局最优解局部搜索算法：局部搜索算法(LocalSearch)随机的选择一个初始的可能X0CD,如果f(Xn)<f(Xb)，则Xb=Xn,P=N(X),Xb=Xo,P=N（Xb）；求Xb的邻域如果不满足结束条件，则Begin选才IP的一个子集PXn为P'中的最优解求更新后的Xb邻域转（2）;f（X）为指标函数。否贝UP=P-P转（2）。End输出计算结果结束注：按照局部搜索