人工智能-习题.ppt

《人工智能-习题.ppt》由会员分享，可在线阅读，更多相关《人工智能-习题.ppt（61页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、人工智能原理人工智能原理习题分析 2023/3/72.1 谓词逻辑表示知识谓词逻辑表示知识用谓词逻辑表示下列知识：用谓词逻辑表示下列知识：武汉是一个美丽的城市，但她不是一个沿海城市。武汉是一个美丽的城市，但她不是一个沿海城市。如果马亮是男孩，张红是女孩，则马亮比张红长得高。如果马亮是男孩，张红是女孩，则马亮比张红长得高。例例第一步第一步第二步第二步第三步第三步定义谓词如下：定义谓词如下：BCity(x)：x是一个美丽的城市是一个美丽的城市 HCity(x)：x是一个沿海城市是一个沿海城市Boy(x):x是男孩是男孩 Girl(x):x是女孩是女孩 High(x,y):x比比y长得高长得高根据语

2、义，用逻辑连接符连接根据语义，用逻辑连接符连接BCity(wuhan)HCity(wuhan)(Boy(mal)Girl(zhangh)High(mal,zhangh)将个体代入谓词中，得到将个体代入谓词中，得到 BCity(wuhan),HCity(wuhan),Boy(mal),Girl(zhangh),High(mal,zhangh)2023/3/7人人爱劳动。人人爱劳动。所有整数不是偶数就是奇数。所有整数不是偶数就是奇数。自然数都是大于零的整数自然数都是大于零的整数例例第一步第一步第二步第二步第三步第三步MAN(x)：x是人是人 LOVE(x,y):x爱爱yN(x)：x是自然数；是自然

3、数；I(xI(x)：x x是整数；是整数；E(xE(x)：X X是偶数是偶数O(x):x是奇数是奇数 GZ(x):x大于大于0 02.1 谓词逻辑表示知识谓词逻辑表示知识2023/3/7第三步第三步2.1 谓词逻辑表示知识谓词逻辑表示知识在一个房间里，有一个机器人在一个房间里，有一个机器人RobotRobot，一个壁橱，一个壁橱AlcoveAlcove，一个积木块一个积木块BoxBox，两个桌子，两个桌子A A和和B B。开始时，。开始时，BobotBobot在在AlcoveAlcove旁边且两手是空的，旁边且两手是空的，A A上放着上放着BoxBox，B B上是空的。上是空的。RobotRo

4、bot将把将把BoxBox从从A A移到移到B B上上例例3 3第一步第一步第二步第二步TABLE(x)：x是桌子是桌子 EMPTYHANDEDEMPTYHANDED(x)：x双手是空的双手是空的AT(x,y):x在在y旁边旁边 HOLDS(y,wHOLDS(y,w)：y y拿着拿着w wON(w,xON(w,x):w):w在在x x上上 EMPTYTABLE(xEMPTYTABLE(x)：桌子：桌子x x上是空的上是空的个体词：个体词：ROBOT,BOX,ALCOVE,A,B 2023/3/7设有如下语句，请用谓词公式把他们表示出来设有如下语句，请用谓词公式把他们表示出来(1)有的人喜欢梅花

5、，有的人喜欢菊花，有的人既喜欢有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花梅花又喜欢菊花。(2)要想出国留学，必须通过外语考试要想出国留学，必须通过外语考试(2)所有人都有饭吃所有人都有饭吃1.定义谓词及个体，确定每个谓词及个体的确切含义。定义谓词及个体，确定每个谓词及个体的确切含义。2.根据所要表达的事物或概念，为每个谓词中的变元赋根据所要表达的事物或概念，为每个谓词中的变元赋以特定的值。以特定的值。3.根据所要表达的知识的语义，用适当的连接符将各个根据所要表达的知识的语义，用适当的连接符将各个谓词连接起来谓词连接起来,形成谓词公式。形成谓词公式。2.1 谓词逻辑表示知识谓词逻

6、辑表示知识2023/3/7有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花喜欢菊花第一步第一步第二步第二步第三步第三步定义谓词：定义谓词：LIKE(x,y)：x喜欢喜欢y 定义个体词：定义个体词：Meihua，JuhuaLIKE(x,Meihua),LIKE(y,Juhua)LIKE(z,Meihua)LIKE(z,Juhua)2023/3/7要想出国留学，必须通过外语考试要想出国留学，必须通过外语考试第一步第一步第二步第二步第三步第三步定义谓词：定义谓词：Want(x,y)：x想想y，Pass(x,y)：x通过通过y 定义个体词：定

7、义个体词：goabroad,flanguagePass(x,flanguage),Want(x,goabroad)2023/3/7所有人都有饭吃所有人都有饭吃第一步第一步第二步第二步第三步第三步定义谓词：定义谓词：Havefood(x)：x有饭吃有饭吃2023/3/7自测题目自测题目1.李明每天下午踢足球李明每天下午踢足球2.合肥的夏天潮湿炎热合肥的夏天潮湿炎热3.喜欢打篮球的人必喜欢踢足球喜欢打篮球的人必喜欢踢足球2023/3/7动物动物isa生物生物植物植物isaisaisa鱼鱼鸟鸟飞飞翅膀翅膀水水游泳游泳cancaninhave乌鸦乌鸦isa黑色黑色腐肉腐肉eatingcovering吃

8、吃运动运动cancan2.2 语义网络知识表示语义网络知识表示2023/3/72.2 语义网络知识表示语义网络知识表示语义网络语义网络语义网络语义网络AKOAKOISHAVELocate-at山羊山羊动物动物羊羊猪猪绵羊绵羊野猪野猪哺乳动物哺乳动物头上有角头上有角羊毛羊毛森林森林AKOAKOAKOAKO猪和羊的语义网络2023/3/7框架名：框架名：主机品牌：联想主机品牌：联想1+1 生产厂商：北京联想集团公司生产厂商：北京联想集团公司 CPU：品牌：品牌：Intel 型号：奔腾型号：奔腾/933 主板：品牌：主板：品牌：QDI 型号：型号：ATX VA5 内存：品牌：现代内存：品牌：现代 型

9、号：型号：SDRAM 容量：容量：128MB 硬盘：品牌：硬盘：品牌：Seagate 型号：型号：ST320423A 容量：容量：20GB例例2.3 框架知框架知识表示表示2023/3/7例：例：新华社新华社9月月16日电日电 国家气象台命名的国家气象台命名的“99年年2号号”台风于昨日下午台风于昨日下午4时在浙江舟山地区登陆，据时在浙江舟山地区登陆，据专家经验，认为风力大于等于专家经验，认为风力大于等于8级，但风力的准确级，但风力的准确值，有待数据处理，目前尚未公布。此次台风造成值，有待数据处理，目前尚未公布。此次台风造成的损失，尚未得到报告，若需要详细的损失数字，的损失，尚未得到报告，若需

10、要详细的损失数字，可电询自然灾害统计中心。另据介绍，事前曾得到可电询自然灾害统计中心。另据介绍，事前曾得到国际气象组织预报：昨日上午于太平洋赤道地区生国际气象组织预报：昨日上午于太平洋赤道地区生成的高压气旋，将向北移动，于浙江舟山地区登陆。成的高压气旋，将向北移动，于浙江舟山地区登陆。依国际惯例，将其命名为依国际惯例，将其命名为Carla飓风。我国也予以飓风。我国也予以承认，至于承认，至于Carla是否就是是否就是“99年年2号号”尚须另加核尚须另加核实。实。2.3 框架知识表示框架知识表示2023/3/7Frame：台风：台风slot1：登陆时间：登陆时间 Value：9月月15日下午四时日

11、下午四时 slot2：登陆地点：登陆地点 Value：浙江舟山地区：浙江舟山地区slot3：风力：风力 default：大于等于：大于等于8级级 slot4：损失：损失 If-needed：电询自然灾害统计中心：电询自然灾害统计中心slot5：名称：名称 Value：99年年2号号Default：Carla 飓风飓风 If-added：核查：核查Carla与与“61年年2号的关系并加注释号的关系并加注释2.3 框架知识表示框架知识表示2023/3/73.1 子句集子句集消去存在量词消去存在量词1234谓词公式化为谓词公式化为子句集步骤子句集步骤重新命重新命名变元名变元利用等价利用等价关系消去关

12、系消去谓词公式谓词公式中的中的“”和和“”利用等价关利用等价关系把系把“”移到紧靠谓移到紧靠谓词词存在量词不出现在全称量存在量词不出现在全称量词的辖域内，则用新的词的辖域内，则用新的个个体常量体常量替换存在量词；替换存在量词；存在量词位于一个或多个存在量词位于一个或多个全称量词的辖域内，则用全称量词的辖域内，则用全称量词的全称量词的函数函数取代存在取代存在量词量词2023/3/73.1 子句集子句集 把全把全称量词称量词移到公移到公式左边式左边8765谓词公式化为谓词公式化为子句集步骤子句集步骤消去全消去全称量词称量词利用等价关利用等价关系把母式化系把母式化为合取范式为合取范式9使不同子使不同

13、子句中的变句中的变元不同名元不同名消去合取消去合取词，生成词，生成子句集子句集2023/3/73.1 子句集子句集2023/3/7例如：例如：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)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 最小合一置换最小合一置换2023/3/7(3)W

14、1未合一，从左到右找不一致集，有未合一，从左到右找不一致集，有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)(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.

15、2 最小合一置最小合一置换换2023/3/7已知能阅读的都是有文化的；海豚是没有文化的；某些海豚是已知能阅读的都是有文化的；海豚是没有文化的；某些海豚是有智能的；证明：某些有智能的并不能阅读。有智能的；证明：某些有智能的并不能阅读。证明：符号化证明：符号化R(x):x能阅读能阅读 L(x):x有文化有文化 D(x)：x是海豚是海豚 I(x)：x有智能有智能3.3 使用归结原理证明问题使用归结原理证明问题2023/3/7I(w)R(w)I(A)R(A)R(x)L(x)D(y)L(y)L(A)NILD(A)D(A)3.3 使用归结原理证明问题使用归结原理证明问题2023/3/7例例4.6 已知已知

16、F1：王王(wang)先生是小李先生是小李(Li)的老师的老师 F2：小李和小张小李和小张(zhang)是是 同班同学同班同学 F3：如果如果x和和y是同班同学，则是同班同学，则x的老师就是的老师就是y的老师。的老师。求：小张的老师是谁？求：小张的老师是谁？解：解：1)定义谓词：定义谓词：T(x,y):x是是y的老师；的老师；C(x,y):x与与y是同班同学是同班同学3.4 使用归结原理求解使用归结原理求解2023/3/7C(Li,y)T(Wang,y)T(Wang,Li)C(x,y)T(z,x)T(z,y)T(u,Zhang)T(u,Zhang)C(Li,Zhang)C(Li,Zhang)T

17、(Wang,Zhang)T(Wang,Zhang)Wang/z,Li/xWang/u,Zhang/y3.4 使用归结原理求解使用归结原理求解2023/3/7作业作业1 某公司招聘工作人员，某公司招聘工作人员，A、B、C三人应三人应试，经面试后公司表示如下想法：试，经面试后公司表示如下想法：(1)三人中至少录取一人三人中至少录取一人 (2)如果录取如果录取A而不录取而不录取B，则一定录取，则一定录取C (3)如果录取如果录取B，则一定录取，则一定录取C 求证：公司一定录取求证：公司一定录取C2023/3/7作业作业2 已知以下的事实：已知以下的事实：Marcus是人。是人。Marcus是罗马人。

18、是罗马人。Caser是一位统治是一位统治者。者。所有罗马人或忠于所有罗马人或忠于Caser或仇恨他。或仇恨他。每个人都忠于某个人。每个人都忠于某个人。人们只想暗杀人们只想暗杀他们不忠于的统治者。他们不忠于的统治者。Marcus试图暗杀试图暗杀Caser。求证：求证：Marcus仇恨仇恨Caser。2023/3/7作业作业3 设设A、B、C三人中有人从不说真话，三人中有人从不说真话，也有人从不说假话，某人向这三个人分别也有人从不说假话，某人向这三个人分别提出同一个问题：谁是说谎者？提出同一个问题：谁是说谎者？A答：答：“B和和C都是说谎者都是说谎者”；B答答“A和和C都是说谎都是说谎者者”；C答

19、：答：“A和和B中至少有一个是说谎中至少有一个是说谎者。者。”求谁是老实人，谁是说谎者？求谁是老实人，谁是说谎者？2023/3/7 例例2 2 设有如下知识设有如下知识R R1 1：IF IF A A THEN(20 THEN(20，1)1)B B1 1(0.03)(0.03)R R2 2：IF IF B B1 1 THEN(300 THEN(300，0.0001)0.0001)B B2 2(0.01)(0.01)求：当证据求：当证据A A必然发生时必然发生时,P(BP(B2 2/A)A)的值是多少？的值是多少？解解:（1）由于）由于A必发生，由必发生，由R1得得 （2）由于）由于B1不是必发

20、生的，所以需作插值处理。不是必发生的，所以需作插值处理。例例1 14.1 主观主观bayes方法方法2023/3/7 当当时，有时，有，所以在此区间插值。，所以在此区间插值。由于由于4.1 主观主观bayes方法方法2023/3/7例例2：设有如下知识设有如下知识 r1:IF E1 THEN (20，1)Hr2:IF E2 THEN (300,1)H 已知已知P(H)=0.03，若证据，若证据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

21、)=LS2*O(H)=9.274.1 主观主观bayes方法方法2023/3/7解法解法2：更新法：更新法2023/3/7例例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(H2)=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|S1S

22、2S3)4.1 主观主观bayes方法方法2023/3/7E1H1E2E3H2(2,0.000001)(65,0.01)(300,0.0001)(100,0.000001)0.20.40.030.10.012023/3/7解解(1)求求P(H1|S1)2023/3/7(2)求求P(H1|S2)2023/3/72023/3/72023/3/72023/3/72023/3/74.2 C-F方法方法 已知已知 R1：IF A1 THEN B1 CF(B1,A1)=0.8；R2:IF A2 THEN B1 CF(B1,A2)=0.5；R3:IF B1A3 THEN B2 CF(B2,B1A3)=0.8

23、;初始证据为初始证据为A1,A2,A3的可信度的可信度CF均设为均设为1，即即,CF(A1)=CF(A2)=CF(A3)=1,对对B1,B2一无所知一无所知,求求CF(B1)和和CF(B2)。例例 1 12023/3/7 解解:由于对由于对B1,B2一无所知，所以使用合成算法进行计算。一无所知，所以使用合成算法进行计算。由题意得到推理网络如下图所示。由题意得到推理网络如下图所示。B B2 2B B1 1A A3 3A A1 1A A2 24.2 C-F方法方法2023/3/7(1)(1)对于知识对于知识R R1 1,R,R2 2,分别计算分别计算CFCF1 1(B(B1 1),CF),CF2

24、2(B(B1 1)(2)(2)利用合成算法计算利用合成算法计算B B1 1的综合可信度的综合可信度(3)(3)计算计算B B2 2的可信度，这时，的可信度，这时，B B1 1作为作为B B2 2的证据，的证据，CF(BCF(B1 1)=0.9)=0.9，而而A A3 3的可信度为初始制定的的可信度为初始制定的1 1。由规则。由规则R R3 3得到得到 4.2 C-F方法方法2023/3/7例例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

25、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方法方法2023/3/7(1)求求CF(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

26、(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.274.2 C-F方法方法2023/3/7(3)求求CF1,2(H),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.364.2 C-F方法方法2023/3

27、/7ABCDE43 4 523例：五个城市间的交通路线图，A城是出发地E是目的地，两城市间的交通费用(代价)如图数字所示。求从A到E最小费用交通路线。将交通图转换为代价树将交通图转换为代价树从起始节点从起始节点A开始，把与它直接相邻的开始，把与它直接相邻的节点作为它的子节点。节点作为它的子节点。若一个节点已作为某节点的先辈节点若一个节点已作为某节点的先辈节点时，就不能再作为这个节点的子节点。时，就不能再作为这个节点的子节点。图中除起始节点图中除起始节点A外，其它节点都可能要在代外，其它节点都可能要在代价树中出现多次，为区分它的多次出现分价树中出现多次，为区分它的多次出现分别用下标别用下标12标

28、出。标出。5.1 代价树宽度优先搜索代价树宽度优先搜索2023/3/7A B1E1 9A B1D2E3 1 1A C1D1E2 8A C1D1B2E4 1 42 4 5AC1B1D1D2E1E2B2C2E3E43 43 4 2 355.1 代价树宽度优先搜索代价树宽度优先搜索2023/3/7f(n):从初始结点经过从初始结点经过n结点到达目的结点的最优路径的代价估结点到达目的结点的最优路径的代价估计值。作用是评价计值。作用是评价open表中各节点的重要性，决定表中各节点的重要性，决定open表表的次序的次序h(n):从从n到目标结点的最佳路径的估计代价，称为启发函数。到目标结点的最佳路径的估计

29、代价，称为启发函数。g(n):从初始结点到从初始结点到n已经付出的实际代价已经付出的实际代价 g(n)和和h(n)各占适当的比重各占适当的比重一般地，一般地，g(n)的比重越大，越倾向于广度优先搜索，的比重越大，越倾向于广度优先搜索，h(n)的比重越大，越倾向于深度优先搜索。的比重越大，越倾向于深度优先搜索。2.估价函数估价函数 一般形式：一般形式：f(n)=g(n)+h(n)5.2 启发信息和估价函数启发信息和估价函数2023/3/7f(n)=d(n)+W(n)其中：其中：d(n)表示节点表示节点n在搜索树中的深度在搜索树中的深度 W(n)表示节点表示节点n中中“不在位不在位”的数码个数。的

30、数码个数。计算初始状态计算初始状态S0的估价函数值的估价函数值f(S0)【例例】八数码难题。设问题的初始状态八数码难题。设问题的初始状态S S0 0和目标状态和目标状态S Sg g如下图所示，且估价函数为如下图所示，且估价函数为2 8 31 47 6 5 1 2 38 47 6 5 S0 Sg5.2 启发信息和估价函数启发信息和估价函数2023/3/72 8 31 47 6 5 1 2 38 47 6 5 S0 Sg解：取解：取g(n)=d(n)，h(n)=W(n)。它说明是用从。它说明是用从S0到到n的路径上的单位代价表示实际代价，用结点的路径上的单位代价表示实际代价，用结点n中中“不在不在

31、位位”的数码个数作为启发信息。一般来说，某节点中的数码个数作为启发信息。一般来说，某节点中的的“不在位不在位”的数码个数越多，说明它离目标节点越远的数码个数越多，说明它离目标节点越远对初始节点对初始节点S0，由于，由于d(S0)=0，W(S0)=3，因此有，因此有f(S0)=0+3=3 5.2 启发信息和估价函数启发信息和估价函数2023/3/7例：有如下结构的移动将牌游戏例：有如下结构的移动将牌游戏B:代表黑色将牌代表黑色将牌W：代表白色将牌：代表白色将牌E：代表该位置为空：代表该位置为空BEBW W BW规则：规则：要求：把所有要求：把所有B移至所有移至所有W的右边，计算的右边，计算h(x

32、)5.2 启发信息和估价函数启发信息和估价函数当一个将牌移入相邻的空位置时，费用为当一个将牌移入相邻的空位置时，费用为1个单位。个单位。一个将牌至多可跳过两个将牌进入空位置，其费用等于跳过的一个将牌至多可跳过两个将牌进入空位置，其费用等于跳过的将牌数加将牌数加1因为因为W左边的左边的B越少越接近目标因此可用越少越接近目标因此可用W左边左边B的个数的个数作为作为h(x);h(x)=3*(每个每个W左边左边B的个数的总和）的个数的总和）2023/3/7广度优先、代价树广度优先是全局择优搜索的特例2 2 8 83 31 14 47 7 6 65 51 12 23 38 84 47 76 65 5估计

33、函数：估计函数：f(x)=d(x)+h(x)d(x)表示节点表示节点x的深度的深度 h(x)表示节点的格局与目标格局不相同的牌数表示节点的格局与目标格局不相同的牌数例：用全局择优搜索求解重排九宫问题例：用全局择优搜索求解重排九宫问题初始状态初始状态S0S0目标状态目标状态SgSg5.2 全局择优搜索全局择优搜索2023/3/72 8 31 47 6 52 8 3 1 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 5 8 32 1 47 6 52 8 37 1 4 6 5 2 31 8 47 6 52 31 8 47 6 51 2 38 47 6 51

34、2 37 8 4 6 51 2 3 8 47 6 54 4 5 55 6 4 644SgS1S2S36该问题的解为：该问题的解为：S0S1S2S3Sg5.2 全局择优搜索全局择优搜索2023/3/7例例八数码难题。八数码难题。S0Sgf(n)=d(n)+P(n)d(n)深度深度P(n)与目标距离与目标距离f*=g*+h*2 8 31 47 6 52 8 3 1 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 5 2 31 8 47 6 52 31 8 47 6 51 2 38 47 6 51 2 37 8 4 6 51 2 3 8 47 6 5f=6 g

35、*=1h*=3 f=6 f=6 g*=2 h*=2 f=6 f=4g*=3 h*=1 f=4g*=4 h*=0 f=4f=6f=45.3 A*算法应用举例算法应用举例h*=4 f=42023/3/7例例 修道士和野人问题。修道士和野人问题。解：用解：用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-

36、2b其中，其中，d(n)为节点的深度。为节点的深度。通过分析可知通过分析可知h(n)h*(n)，满足满足A*算法的限制条件。算法的限制条件。M-C问题的搜索过程如下图所示。问题的搜索过程如下图所示。5.3 A*算法应用举例算法应用举例2023/3/7(3,2,0)(3,1,0)(2,2,0)h(n)=m+c-2b(3,3,1)h=4 f=4(3,2,1)(2,1,0)(3,0,0)(2,2,1)(3,1,1)(0,2,0)(1,1,0)(0,3,1)(0,1,0)(0,2,1)(0,0,0)h=5 f=6h=3 f=5h=3 f=6 h=3 f=6h=2 f=6h=2 f=7h=1 f=7h=

37、1 f=8h=0 f=8h=4 f=5h=4 f=5h=2 f=6h=2 f=7传教士和野人问题的搜索图传教士和野人问题的搜索图5.3 A*算法应用举例算法应用举例2023/3/76.1 基于决策树的归纳学习方法基于决策树的归纳学习方法1.决策树决策树 决策树由一个根结点，若干叶结点和若干非叶结点构成。决策树由一个根结点，若干叶结点和若干非叶结点构成。根结点对应于学习任务。根结点对应于学习任务。每个叶结点都包含一个分类名，即包含一个概念。每个叶结点都包含一个分类名，即包含一个概念。每个非叶结点都包含一个属性测试，对该属性可能取的每一个每个非叶结点都包含一个属性测试，对该属性可能取的每一个值用一

38、个分支引出到另一个结点。值用一个分支引出到另一个结点。2.ID3算法算法假设：每个例子仅属于两种分类之一：正例和反例。假设：每个例子仅属于两种分类之一：正例和反例。例子的属性集用例子的属性集用A表示，单个属性表示为表示，单个属性表示为ai(i=1,2,|A|),|A|表示表示A所含属性的数量。对每个属性所含属性的数量。对每个属性ai,其可能的值集用其可能的值集用Vi表示，表示，单个值用单个值用vij表示，表示，j=1,2,|Vi|,其中其中|Vi|是是ai可能取的值的数可能取的值的数目。目。2023/3/7(1)(1)令根结点包含例子集中所有的实例令根结点包含例子集中所有的实例(2)(2)如果

39、当前决策树中每一个叶结点包含的例子都属于同一分如果当前决策树中每一个叶结点包含的例子都属于同一分类，即或者都是目标概念的正例，或者都是反例，则停止类，即或者都是目标概念的正例，或者都是反例，则停止划分。划分。(3)(3)否则需对既包含正例又包含反例的叶结点进一步划分。否则需对既包含正例又包含反例的叶结点进一步划分。(a)a)需要进一步划分的叶结点所包含的例子组成子集需要进一步划分的叶结点所包含的例子组成子集S S(b)(b)找出对找出对S S来说来说E E值最小的属性值最小的属性a abestbest(c)(c)根据属性根据属性a abestbest的值的值V Vbestbest对需要划分的叶

40、结点所包含的子例对需要划分的叶结点所包含的子例子集进行划分，每个子集进行划分，每个V Vbest,Ibest,I(I(I=1,2,=1,2,|V Vbestbest|)|)将生成一个分将生成一个分支。支。(d)d)执行步骤执行步骤(2)(2)6.2 ID3算法描述：算法描述：2023/3/7例：假定按是否例：假定按是否“危险危险”这个概念对狗的集合进行分类，在类别栏正例即这个概念对狗的集合进行分类，在类别栏正例即“危险危险”的狗用的狗用“”标出，反例用标出，反例用“”标出，属性及取值由下表给出。标出，属性及取值由下表给出。对属性对属性“颜色颜色”序号序号 颜色颜色 体形体形 毛型毛型 类别类别

41、1 1黑黑大大卷毛卷毛2 2棕棕大大光滑光滑3 3棕棕中中卷毛卷毛4 4黑黑小小卷毛卷毛5 5棕棕中中光滑光滑6 6黑黑大大光滑光滑7 7棕棕小小卷毛卷毛8 8棕棕小小光滑光滑9 9棕棕大大卷毛卷毛1010黑黑中中卷毛卷毛1111黑黑中中光滑光滑1212黑黑小小光滑光滑2023/3/7因为因为E体形体形E颜色颜色E毛型毛型，所以，所以“体形体形”被被选为划分属性如下图。选为划分属性如下图。“大大”“小小”组成子例子集（组成子例子集（8个例子）个例子）算出算出E颜色颜色4 E毛型毛型6.490所以用属性所以用属性“颜色颜色”作第二步划分如右图作第二步划分如右图体形体形(+)(-+-)(-+-)大

42、大中中小小体形体形(+)颜色颜色大大中中小小(-)黑黑(+-)棕棕颜色颜色(-)(+-)黑黑棕棕序号序号颜色颜色体形体形毛型毛型类别类别3 3棕棕中中卷毛卷毛4 4黑黑小小卷毛卷毛5 5棕棕中中光滑光滑7 7棕棕小小卷毛卷毛8 8棕棕小小光滑光滑1010黑黑中中卷毛卷毛1111黑黑中中光滑光滑1212黑黑小小光滑光滑2023/3/7最后用属性最后用属性“毛型毛型”进行划分，得到进行划分，得到体形体形(+)颜色颜色大大中中小小(-)黑黑(+-)棕棕颜色颜色(-)(+-)黑黑棕棕(+)(-)(-)(+)光滑光滑光滑光滑卷毛卷毛卷毛卷毛2023/3/7毛型毛型颜色颜色光滑光滑卷毛卷毛体形体形黑黑体形体形棕棕颜色颜色体形体形体形体形黑黑棕棕(+)(+)(-)(-)(-)(-)大大小小中中(+)(+)(+)(+)(-)(-)大大小小中中(+)(+)(-)(-)(-)(-)大大小小中中(+)(+)(-)(-)(+)(+)大大小小中中2023/3/7