人工智能技术导论总复习

1、人工智能总复习人工智能总复习第第1章章 人工智能概述人工智能概述n什么是人工智能？人工智能的研究目标和意义？什么是人工智能？人工智能的研究目标和意义？n人工智能的研究学派、人工智能的研究学派、途径与方法途径与方法n人工智能的研究目标人工智能的研究目标n人工智能的主要领域（基于应用领域）人工智能的主要领域（基于应用领域）n人工智能基本技术人工智能基本技术第第3章章 图搜索技术图搜索技术n状态图知识表示状态图知识表示n状态图搜索状态图搜索q穷举式搜索穷举式搜索q启发式搜索启发式搜索q加权状态图搜索加权状态图搜索n与或图知识表示与或图知识表示n与或图搜索与或图搜索q启发式与或树搜索启发式与或树搜索n

2、博弈树搜索博弈树搜索q极小极大分析法极小极大分析法q-剪枝剪枝状态图知识表示状态图知识表示n状态空间（状态空间（State SpaceState Space）q问题的状态空间是一个表示该问题全部的可能状态问题的状态空间是一个表示该问题全部的可能状态及相互关系的图。及相互关系的图。q一般包含一般包含nS S：问题的可能有的初始状态的集合；：问题的可能有的初始状态的集合；nF F：操作的集合；：操作的集合；nG G：目标状态的集合。：目标状态的集合。n状态空间常记为三元序列状态空间常记为三元序列SG状态空间中问题求解（状态空间中问题求解（1）n在状态空间图中，问题求解过程转化为在图中寻找从初始在状

3、态空间图中，问题求解过程转化为在图中寻找从初始状态状态S0出发到达目标状态出发到达目标状态Sg的路径问题，也就是寻找操作的路径问题，也就是寻找操作序列的问题。序列的问题。n状态空间的解为三元组状态空间的解为三元组qS0 ：某个初始状态：某个初始状态qSg ：某个目标状态：某个目标状态qO：把：把Qs变换成变换成Qg的有限的操作序列的有限的操作序列O1,O2,Onq状态转换图状态转换图S1S3S2O1O2O3O4S0SgOn状态空间中问题求解（状态空间中问题求解（2）n状态图搜索状态图搜索：从初始节点出发，沿着与之相连的边试：从初始节点出发，沿着与之相连的边试探地前进，寻找目标节点的过程。探地前

4、进，寻找目标节点的过程。n状态图的解状态图的解：搜索成功后，从目标结点反向沿搜索树：搜索成功后，从目标结点反向沿搜索树按所作标记追溯一直到初始结点，所得到一条从初始按所作标记追溯一直到初始结点，所得到一条从初始结点到目标结点的路径就是问题的一个解。结点到目标结点的路径就是问题的一个解。状态图搜索状态图搜索n穷举式搜索穷举式搜索q广度优先广度优先q深度优先深度优先q有界深度优先有界深度优先n启发式搜索启发式搜索q全局择优（广度优先搜索全局择优（广度优先搜索+h(x)）q局部择优（深度优先搜索局部择优（深度优先搜索+h(x)）n加权状态图搜索加权状态图搜索q分支界限（广度优先搜索分支界限（广度优先

5、搜索+g(x)）q最近择优最近择优/瞎子爬山（深度优先搜索瞎子爬山（深度优先搜索+g(x)）nA算法（一般树式搜索算法算法（一般树式搜索算法+f(x)）nA*算法（算法（h(x)=2then a=a-1 If a=1then a=4Pb：if b=2 then b=b-1 If b=1then b=4Pc：if c=2 then c=c-1 If c=1then c=4 广度优先搜索树广度优先搜索树Pb2，2，21，2，22，1，22，2，1PaPbPc4，2，21，1，2PaPc1，2，1Pb1，2，12，1，1PaPc2，2，4PaPbPc1，1，22，4，22，1，13，2，24，1，2

6、4，2，1PaPbPc深度优先搜索树深度优先搜索树Pb2，2，21，2，22，1，22，2，1PaPbPcPcPbPc4，2，21，1，2PaPc1，2，13，2，24，2，1PaPb4，1，22，2，2Pa3，1，23，2，1补充例题：加权状态图搜索n代价树如下图所示：分别给出宽度优先及深度优先搜索策略下的搜索过程和解。其中，F、I、 J、L是目标节点。ABCDEFGHIJKLMOP32215213233132宽度优先搜索过程：宽度优先搜索过程：A C B GED M J，G（J）=6，解为：解为：A B E J深度优先搜索过程为：深度优先搜索过程为：A C GMPOL，G（L）=7，解为：

7、解为：A CGL图搜索图搜索解：用宽度优先搜索搜索树为：SABHCDFEG用宽度优先搜索过程为：SABHCGDF解为：SABCF代价树搜索代价树搜索n下图是五城市间的交通路线图，下图是五城市间的交通路线图，A是出发地，是出发地，E是目的地，两城市间的交通费用（代价）如是目的地，两城市间的交通费用（代价）如图中数字所示。求图中数字所示。求A到到E的最小费用交通路线。的最小费用交通路线。 代价树代价树AC1B1D1D2E1E2B2E4C2E33423454523图4-2广度优先搜索广度优先搜索n所以，最优路径为所以，最优路径为A-C-D-E扩展节点，将其子节点放入扩展节点，将其子节点放入open表

8、中，计算各子节点的代价，并按各节点的代表中，计算各子节点的代价，并按各节点的代价对价对open表中全部节点按从小到大的顺序进行排序（队列）表中全部节点按从小到大的顺序进行排序（队列） 深度优先搜索深度优先搜索n扩展节点，将其子节点按代价从小到大的顺序扩展节点，将其子节点按代价从小到大的顺序放到放到open表的首部（栈）表的首部（栈） 435AC1B1D12AC1B143435AC1B1D18934E2B2E为目标节点，E2-D1-C1-A所以路径为A-设如图与或树，请分别按和代价法及最设如图与或树，请分别按和代价法及最大代价法求解树代价。大代价法求解树代价。n按和代价法：按和代价法：h(B)=

9、7,h(C)=3,h(A)=7+3+5+6=21n按最大代价法：按最大代价法：h(B)=5,h(C)=2,h(A)=5+5=10BCDt2t1t4At357223621书82页图3-19 剪枝例7 72 24 4 -1-12 24 4 -2-2 6 64 43 34 45 56 6 -5-5 6 68 86 63 31 1N2 26 68 822-23441-51242知识表示知识表示知 识表示谓词表示法产生式表示法框架表示法语义网络表示法框架通常由指定事物各个方面的槽组成，每个槽拥有若干个侧面，而每个侧面又可拥有若干个值。语义网络由节点和弧线或链线组成，节点用于表示物体、概念和状态，弧线用于

10、表示节点间的关系。产生式系统由3个基本部分组成：规则库、综合数据库、控制系统。首先定义谓词，指出每个谓词的确切含义，然后再用连接词把有关的谓词连接起来，形成一个谓词公式表达一个完整的意义。归结原理证明定理应用归结原理证明定理应用2 任何兄弟都有同一个父亲，任何兄弟都有同一个父亲，John和和Peter是兄弟，是兄弟，John的的父亲是父亲是David，问，问Peter的父亲是谁？的父亲是谁？解：第一步：定义谓词：解：第一步：定义谓词： 设设Father(x,y)表示表示x是是y的父亲。的父亲。 设设Brother(x,y)表示表示x和和y是兄弟。是兄弟。第二步：将已知事实、要证结论用谓词公式表

11、示出来：第二步：将已知事实、要证结论用谓词公式表示出来： F1:xyz(Brother(x,y)Father(z,x)Father(z,y) F2: Brother(John, Peter) F3: Father(David, John) G : Father(u, Peter) 归结原理证明定理应用归结原理证明定理应用第三步，将它们化成子句集，得第三步，将它们化成子句集，得F1：Brother(x,y)Father(z,x)Father(z,y), F2：Brother(John, Peter), F3：Father(David, John) G: Father(u, Peter)增配辅助谓

12、词，即将其增配辅助谓词，即将其G的否定与谓词的否定与谓词ANSWER做析取。做析取。 G: Father(u, Peter) ANSWER(u)第四步：应用归结原理进行归结。第四步：应用归结原理进行归结。（1）Brother(x,y)Father(z,x)Father(z,y)（2）Brother(John, Peter)（3）Father(David, John)（4）Father(u, Peter) ANSWER(u)（5）Brother(John,y) Father(David,y) 1,3, = David/z, John/x（6）Brother(John, Peter) ANSWER

13、(David) 4,5，= David/u, Peter/y（7）ANSWER(David) 2,6即即Peter的父亲是的父亲是David。产生式系统系统产生式系统系统设有如下问题：设有如下问题：（1）有五个相互可直达且距离已知的城市）有五个相互可直达且距离已知的城市A、B、C、D、E，如图所示；，如图所示；（2）某人从）某人从A地出发，去其它四个城市各参观一次后回到地出发，去其它四个城市各参观一次后回到A;（3）找一条最短的旅行路线）找一条最短的旅行路线请用产生式规则表示旅行过程。请用产生式规则表示旅行过程。解：解：综合数据库（综合数据库（x）：）：(x)中中x可以是一个字母，也可以是一个

14、字符串。可以是一个字母，也可以是一个字符串。初始状态（初始状态（A）目标状态（目标状态（Ax1x2x3x4A） 规则集：规则集： r1: IF L(S)=5 THEN GOTO(A) r2: IF L(S)5 THEN GOTO(B) r3: IF L(S)5 THEN GOTO(C) r4: IF L(S)5 THEN GOTO(D) r5: IF L(S)5 THEN GOTO(E)其中其中L(S)为走过的城市数，为走过的城市数，GOTO(x)为走向城市为走向城市x路线如下图所示路线如下图所示:( A )( AB )( AC )( AD )( AE )( A CB)( A CD)( ACE

15、 )( A CDB)( ACDE )( ACDEB )( ACDEBA)751010769108107起始目标推理推理推 理经典逻辑推理不确定与非单调推理归结演绎推理与/或形演绎推理自然演绎推理谓词逻辑的归结原理谓词逻辑的归结原理用谓词公式表示下列刑侦知识，并用归结原理求取结论。用谓词公式表示下列刑侦知识，并用归结原理求取结论。（1）用子句集表示下述知识）用子句集表示下述知识 A John是贼；是贼； B Paul喜欢酒喜欢酒 C Paul也喜欢奶酪也喜欢奶酪 D 如果如果Paul喜欢某物，则喜欢某物，则John也喜欢也喜欢 E 如果某人是贼，而且喜欢某物，则他可能会偷窃该物如果某人是贼，而且

16、喜欢某物，则他可能会偷窃该物 （2）求取结论：）求取结论：John可能会偷窃什么？可能会偷窃什么？（1）定义谓词）定义谓词thief（x）：表示）：表示x是贼是贼likes(x,y):表示某人表示某人x喜欢某物喜欢某物ymay_steal(x,y)：表示某人：表示某人x可能会偷某物可能会偷某物y将已知事实表示成谓词公式并化子句集将已知事实表示成谓词公式并化子句集A：thief(John)B:likes(Paul,wine)C: likes(Paul,cheese)D: x(likes(Paul,x) likes(Johnl,x)E: x y(thief(x) likes(x,y) may_steal(x,y)化子句集：化子句集：1：thief(John)2:likes(Paul,wine)3: likes(Paul,cheese)4: likes(Paul,z) likes(John,z)5: thief(x) likes(x,y) may_steal(x,y)目标为：目标为： x may_steal(John,x)目标谓词否定增配辅助谓词：目标谓词否定增配辅助谓词：6:may_steal(John,u) Answer(u)（2）利用归结原理求