《人工智能 习题ppt课件.ppt》由会员分享，可在线阅读，更多相关《人工智能 习题ppt课件.ppt（61页珍藏版）》请在三一办公上搜索。
1、2022/11/22,人工智能原理,习题分析,2022/11/22,2.1 谓词逻辑表示知识,用谓词逻辑表示下列知识：武汉是一个美丽的城市，但她不是一个沿海城市。如果马亮是男孩，张红是女孩，则马亮比张红长得高。,例,定义谓词如下：BCity(x)：x是一个美丽的城市 HCity(x)：x是一个沿海城市Boy(x): x是男孩 Girl(x): x是女孩 High(x,y): x比y长得高,根据语义，用逻辑连接符连接BCity(wuhan)HCity(wuhan)(Boy(mal)Girl(zhangh)High(mal,zhangh),将个体代入谓词中，得到 BCity(wuhan), HCi
2、ty(wuhan), Boy(mal), Girl(zhangh), High(mal,zhangh),2022/11/22,人人爱劳动。所有整数不是偶数就是奇数。自然数都是大于零的整数,例,MAN(x)：x是人 LOVE(x,y): x爱yN(x)：x是自然数；I(x)：x是整数；E(x)：X是偶数O(x): x是奇数 GZ(x): x大于0,2.1 谓词逻辑表示知识,2022/11/22,2.1 谓词逻辑表示知识,在一个房间里，有一个机器人Robot，一个壁橱Alcove，一个积木块Box，两个桌子A和B。开始时，Bobot在Alcove旁边且两手是空的，A上放着Box，B上是空的。Rob
3、ot将把Box从A移到B上,例3,TABLE(x)：x是桌子 EMPTYHANDED(x)：x双手是空的AT(x,y): x在y旁边 HOLDS(y,w)：y拿着wON(w,x): w在x上 EMPTYTABLE(x)：桌子x上是空的,个体词：ROBOT,BOX,ALCOVE,A,B,2022/11/22,设有如下语句，请用谓词公式把他们表示出来(1) 有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花 。(2) 要想出国留学，必须通过外语考试(2) 所有人都有饭吃,1.定义谓词及个体，确定每个谓词及个体的确切含义。2.根据所要表达的事物或概念，为每个谓词中的变元赋以特定的值。3.根据
4、所要表达的知识的语义，用适当的连接符将各个谓词连接起来,形成谓词公式。,2.1 谓词逻辑表示知识,2022/11/22,有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花,定义谓词：LIKE(x,y)：x喜欢y 定义个体词：Meihua，Juhua,LIKE(x,Meihua), LIKE(y,Juhua)LIKE(z,Meihua) LIKE(z,Juhua),2022/11/22,要想出国留学，必须通过外语考试,定义谓词：Want(x,y)：x想y，Pass(x,y)：x通过y 定义个体词：goabroad,flanguage,Pass(x,flanguage),Want(x,go
5、abroad),2022/11/22,所有人都有饭吃,定义谓词：Havefood(x)：x有饭吃,2022/11/22,自测题目,1.李明每天下午踢足球2.合肥的夏天潮湿炎热3.喜欢打篮球的人必喜欢踢足球,2022/11/22,2.2 语义网络知识表示,2022/11/22,2.2 语义网络知识表示,语义网络,猪和羊的语义网络,2022/11/22,框架名： 主机品牌：联想1+1 生产厂商：北京联想集团公司 CPU：品牌：Intel 型号：奔腾/933 主板：品牌：QDI 型号：ATX VA5 内存：品牌：现代 型号：SDRAM 容量：128MB 硬盘：品牌：Seagate 型号：ST3204
6、23A 容量：20GB,例,2.3 框架知识表示,2022/11/22,例：新华社9月16日电 国家气象台命名的 “99年2号” 台风于昨日下午4时在浙江舟山地区登陆，据专家经验，认为风力大于等于8级，但风力的准确值，有待数据处理，目前尚未公布。此次台风造成的损失，尚未得到报告，若需要详细的损失数字，可电询自然灾害统计中心。另据介绍，事前曾得到国际气象组织预报：昨日上午于太平洋赤道地区生成的高压气旋，将向北移动，于浙江舟山地区登陆。依国际惯例，将其命名为Carla飓风。我国也予以承认，至于Carla是否就是“99年2号”尚须另加核实。,2.3 框架知识表示,2022/11/22,2.3 框架知
7、识表示,2022/11/22,3.1 子句集,消去存在量词,1,3,谓词公式化为子句集步骤,重新命名变元,利用等价关系消去谓词公式中的“ ”和“ ”,利用等价关系把“ ”移到紧靠谓词,2022/11/22,3.1 子句集,把全称量词移到公式左边,谓词公式化为子句集步骤,消去全称量词,利用等价关系把母式化为合取范式,使不同子句中的变元不同名,消去合取词，生成子句集,2022/11/22,3.1 子句集,2022/11/22,例如：E1=P(a,x,f(g(y) E2=P(z,f(a),f(u)求mgu 。解： (1) W=E1,E2=P(a,x,f(g(y) ,P(z,f(a),f(u) (2)
8、 W0=W,g= (3) W0未合一，从左到右找不一致集，有D0=a,z (4) 取v0=z,t0=a (5) 令g1= g0t0/v0,=a/z W1= W0 g1= P(a,x,f(g(y) ,P(a,f(a),f(u),3.2 最小合一置换,2022/11/22,(3) W1未合一，从左到右找不一致集，有D1=x,f(a)(4) 取v1=x,t1=f(a)(5) 令g2= g1t1/v1,=a/z,f(a)/x W2= W1 g2= P(a,f(a),f(g(y) ,P(a,f(a),f(u)(3) W2未合一，从左到右找不一致集，有D2=g(y),u)(4) 取v2=u,t2=g(y)
9、(5) 令g3= g2t2/v2,=a/z,f(a)/x,g(y)/u W3= W2 g3= P(a,f(a),f(g(y) ,P(a,f(a),f(g(y)(3)W3已合一，这时g3 =a/z,f(a)/x,g(y)/u,3.2 最小合一置换,2022/11/22,已知能阅读的都是有文化的；海豚是没有文化的；某些海豚是有智能的；证明：某些有智能的并不能阅读。证明：符号化R(x):x能阅读 L(x):x有文化 D(x)：x是海豚 I(x)：x有智能,3.3 使用归结原理证明问题,2022/11/22,3.3 使用归结原理证明问题,2022/11/22,例4.6 已知F1：王(wang)先生是小
10、李(Li)的老师 F2：小李和小张 (zhang) 是 同班同学 F3：如果x和y是同班同学，则x的老师就是y的老师。 求：小张的老师是谁？解：1)定义谓词： T(x,y):x是y的老师；C(x,y):x与y是同班同学,3.4 使用归结原理求解,2022/11/22,C(Li,y)T(Wang,y),T(u,Zhang)T(u,Zhang),C(Li,Zhang),T(Wang,Zhang),Wang/z,Li/x,Wang/u,Zhang/y,3.4 使用归结原理求解,2022/11/22,作业1,某公司招聘工作人员，A、B、C三人应试，经面试后公司表示如下想法： (1)三人中至少录取一人
11、(2)如果录取A而不录取B，则一定录取C (3)如果录取B，则一定录取C 求证：公司一定录取C,2022/11/22,作业2,已知以下的事实：Marcus是人。Marcus是罗马人。Caser是一位统治者。所有罗马人或忠于Caser或仇恨他。每个人都忠于某个人。人们只想暗杀他们不忠于的统治者。Marcus试图暗杀Caser。 求证：Marcus仇恨Caser。,2022/11/22,作业3,设A、B、C三人中有人从不说真话，也有人从不说假话，某人向这三个人分别提出同一个问题：谁是说谎者？A答：“B和C都是说谎者”；B答“A和C都是说谎者”；C答：“A和B中至少有一个是说谎者。”求谁是老实人，谁
12、是说谎者？,2022/11/22,例2 设有如下知识R1：IF A THEN (20，1) B1(0.03)R2：IF B1 THEN (300，0.0001) B2(0.01)求：当证据A必然发生时,P(B2 /A)的值是多少？,解:（1）由于A必发生，由R1得,（2）由于B1不是必发生的，所以需作插值处理。,例1,4.1 主观bayes方法,2022/11/22,当,时，有,，所以在此区间插值。,由于,4.1 主观bayes方法,2022/11/22,例2： 设有如下知识 r1:IF E1 THEN (20，1) Hr2:IF E2 THEN (300, 1) H 已知P(H)=0.03，
13、若证据E1，E2依次出现，求P(H|E1,E2),解法1：合成法O(H)=P(H)/(1-P(H)=0.0309由r1：O(H|E1)=LS1*O(H)=0.618由r2：O(H|E2)=LS2*O(H)=9.27,4.1 主观bayes方法,2022/11/22,解法2：更新法,2022/11/22,例3 设有如下规则：r1:IF E1 THEN (2, 0.000001) H1r2:IF E2 THEN (100, 0.000001) H1 r3:IF H1 THEN (65, 0.01) H2r4:IF E3 THEN (300, 0.0001) H2 且已知P(H1)=0.1, P(H
14、2)=0.01, P(E1)=0.2, P(E2)=0.4, P(E3)=0.03 P(E1|S1)=0.7, P(E2|S2)=0.6, P(E3|S3)=0.02, 求P(H2|S1S2S3),4.1 主观bayes方法,2022/11/22,2022/11/22,解(1)求P(H1|S1),2022/11/22,(2)求P(H1|S2),2022/11/22,2022/11/22,2022/11/22,2022/11/22,2022/11/22,4.2 C-F方法,已知 R1：IF A1 THEN B1 CF(B1,A1)=0.8； R2: IF A2 THEN B1 CF(B1,A2)
15、=0.5； R3: IF B1A3 THEN B2 CF(B2,B1A3)=0.8;初始证据为A1,A2,A3的可信度CF均设为1，即,CF(A1)= CF(A2)= CF(A3)=1,对B1,B2一无所知,求CF(B1)和CF(B2)。,例 1,2022/11/22,解:由于对B1,B2一无所知，所以使用合成算法进行计算。由题意得到推理网络如下图所示。,4.2 C-F方法,2022/11/22,(1)对于知识R1,R2,分别计算CF1(B1),CF2(B1),(2)利用合成算法计算B1的综合可信度,(3)计算B2的可信度，这时，B1作为B2的证据，CF(B1)=0.9，而A3的可信度为初始制
16、定的1。由规则R3得到,4.2 C-F方法,2022/11/22,例2:设有如下规则： R1： IF EI THEN H (0.8) R2： IF E2 THEN H (0.6) R3: IF E3 THEN H (-0.5) R4： IF E4 AND E5 OR E6 THEN E1 (0.7) R5： IF E7 AND E8 THEN E3 (0.9)在系统运行中已从用户处得CF(E2)=0.8，CF(E4)=0.5，CF(E5)=0.6，CF(E6)=0.7，CF(E7)=0.6，CF(E8)=0.9，求H的综合可倍度CF(H)。,4.2 C-F方法,2022/11/22,(1)求C
17、F(E1),CF(E3) CF(E4 AND (E5 OR E6) =minCF(E4),maxCF(E5),CF(E6)=0.5 CF(E1)=0.7max0,CF (E4 AND (E5 OR E6) =0.50.7=0.35 同理可得：CF(E3)=0.54(2)求CF1(H),CF2(H),CF3(H) CF1(H)=0.8max0,CF(E1)=0.80.35=0.28 CF2(H) =0.6max0,CF(E2)=0.60.8=0.48 CF3(H) =-0.5max0,CF(E3)=-0.50.54=-0.27,4.2 C-F方法,2022/11/22,(3)求CF1,2(H),
18、CF1,2,3(H) CF1,2(H)= CF1(H)CF2(H)- CF1(H)CF2(H) =0.28+0.48-0.280.48=0.63 CF1,2,3(H)= CF1,2(H)+CF3(H)=0.63-0.27=0.36,4.2 C-F方法,2022/11/22,将交通图转换为代价树从起始节点A开始，把与它直接相邻的节点作为它的子节点。若一个节点已作为某节点的先辈节点时，就不能再作为这个节点的子节点。 图中除起始节点A外，其它节点都可能要在代价树中出现多次，为区分它的多次出现分别用下标12标出。,5.1 代价树宽度优先搜索,2022/11/22,AB1E1 9AB1D2E3 11AC
19、1D1E2 8AC1D1B2E4 14,5.1 代价树宽度优先搜索,2022/11/22,f(n):从初始结点经过n结点到达目的结点的最优路径的代价估计值。作用是评价open表中各节点的重要性，决定open表的次序,一般地，g(n)的比重越大，越倾向于广度优先搜索，h(n)的比重越大，越倾向于深度优先搜索。,2.估价函数 一般形式：f(n)=g(n)+h(n),5.2 启发信息和估价函数,2022/11/22,f(n)=d(n)+W(n)其中：d(n)表示节点n在搜索树中的深度 W(n)表示节点n中“不在位”的数码个数。计算初始状态S0的估价函数值f(S0),【例】八数码难题。设问题的初始状态
20、S0和目标状态Sg如下图所示，且估价函数为,2 8 31 47 6 5,1 2 38 47 6 5,S0 Sg,5.2 启发信息和估价函数,2022/11/22,2 8 31 47 6 5,1 2 38 47 6 5,S0 Sg,解：取g(n)=d(n)，h(n)=W(n)。它说明是用从S0到n的路径上的单位代价表示实际代价，用结点n中“不在位”的数码个数作为启发信息。一般来说，某节点中的“不在位”的数码个数越多，说明它离目标节点越远对初始节点S0，由于d(S0)=0，W(S0)=3，因此有f(S0)=0+3=3,5.2 启发信息和估价函数,2022/11/22,例：有如下结构的移动将牌游戏B
21、:代表黑色将牌W：代表白色将牌E：代表该位置为空,规则：,要求：把所有B移至所有W的右边，计算h(x),5.2 启发信息和估价函数,当一个将牌移入相邻的空位置时，费用为1个单位。 一个将牌至多可跳过两个将牌进入空位置，其费用等于跳过的将牌数加1,因为W左边的B越少越接近目标因此可用W左边B的个数作为h(x) ;h(x)=3*(每个W左边B的个数的总和）,2022/11/22,广度优先、代价树广度优先是全局择优搜索的特例,估计函数：f(x)=d(x)+h(x) d(x)表示节点x的深度 h(x)表示节点的格局与目标格局不相同的牌数,例：用全局择优搜索求解重排九宫问题,初始状态S0,目标状态Sg,
22、5.2 全局择优搜索,2022/11/22,该问题的解为： S0S1S2S3Sg,5.2 全局择优搜索,2022/11/22,例八数码难题。,S0,Sg,f(n)=d(n)+P(n)d(n) 深度P(n)与目标距离f*=g*+h*,5.3 A*算法应用举例,h*=4 f=4,2022/11/22,例 修道士和野人问题。,解：用m表示左岸的修道士人数，c表示左岸的野人数，b表示左岸的船数，用三元组(m, c, b)表示问题的状态。 对A*算法，首先需要确定估价函数。设g(n)=d(n)，h(n)=m+c-2b，则有f(n)=g(n)+h(n)=d(n)+m+c-2b其中，d(n)为节点的深度。通
23、过分析可知h(n)h*(n)，满足A*算法的限制条件。 M-C问题的搜索过程如下图所示。,5.3 A*算法应用举例,2022/11/22,(3,2,0) (3,1,0) (2,2,0),h(n)=m+c-2b,传教士和野人问题的搜索图,5.3 A*算法应用举例,2022/11/22,6.1 基于决策树的归纳学习方法,1. 决策树 决策树由一个根结点，若干叶结点和若干非叶结点构成。 根结点对应于学习任务。 每个叶结点都包含一个分类名，即包含一个概念。 每个非叶结点都包含一个属性测试，对该属性可能取的每一个值用一个分支引出到另一个结点。2. ID3算法假设：每个例子仅属于两种分类之一：正例和反例。
24、例子的属性集用A表示，单个属性表示为ai(i=1,2,|A|),|A|表示A所含属性的数量。对每个属性ai,其可能的值集用Vi表示，单个值用vij表示，j=1,2,|Vi|,其中|Vi|是ai可能取的值的数目。,2022/11/22,(1) 令根结点包含例子集中所有的实例(2) 如果当前决策树中每一个叶结点包含的例子都属于同一分类，即或者都是目标概念的正例，或者都是反例，则停止划分。(3) 否则需对既包含正例又包含反例的叶结点进一步划分。(a) 需要进一步划分的叶结点所包含的例子组成子集S(b) 找出对S来说E值最小的属性abest(c) 根据属性abest的值Vbest对需要划分的叶结点所包含的子例子集进行划分，每个Vbest,I(I=1,2,|Vbest|)将生成一个分支。(d) 执行步骤(2),6.2 ID3算法描述：,2022/11/22,例：假定按是否“危险”这个概念对狗的集合进行分类，在类别栏正例即“危险”的狗用“”标出，反例用“”标出，属性及取值由下表给出。,对属性“颜色”,2022/11/22,因为E体形E颜色E毛型，所以“体形”被选为划分属性如下图。“大”“小”组成子例子集（8个例子）算出E颜色4 E毛型6.490所以用属性“颜色”作第二步划分如右图,2022/11/22,最后用属性“毛型”进行划分，得到,2022/11/22,
