人工智能-习题优秀PPT.ppt

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

1、人工智能原理人工智能原理习题分析 2022/10/302.1 谓词逻辑表示学问谓词逻辑表示学问用谓词逻辑表示下列学问：用谓词逻辑表示下列学问：武汉是一个美丽的城市，但她不是一个沿海城市。武汉是一个美丽的城市，但她不是一个沿海城市。假如马亮是男孩，张红是女孩，则马亮比张红长得高。假如马亮是男孩，张红是女孩，则马亮比张红长得高。例例第一步第一步第二步第二步第三步第三步定义谓词如下：定义谓词如下：BCity(x)BCity(x)：x x是一个美丽的城市是一个美丽的城市 HCity(x)HCity(x)：x x是一个沿海城市是一个沿海城市Boy(x):xBoy(x):x是男孩是男孩 Girl(x):x

2、 Girl(x):x是女孩是女孩 High(x,y):x High(x,y):x比比y y长得长得高高依据语义，用逻辑连接符连接依据语义，用逻辑连接符连接BCity(wuhan)HCity(wuhan)(Boy(mal)Girl(zhangh)High(mal,zhangh)将个体代入谓词中，得到将个体代入谓词中，得到 BCity(wuhan),HCity(wuhan),Boy(mal),Girl(zhangh),High(mal,zhangh)2022/10/30人人爱劳动。人人爱劳动。全部整数不是偶数就是奇数。全部整数不是偶数就是奇数。自然数都是大于零的整数自然数都是大于零的整数例例第一步

3、第一步第二步第二步第三步第三步MAN(x)：x是人是人 LOVE(x,y):x爱爱yN(x)：x是自然数；是自然数；I(x)I(x)：x x是整数；是整数；E(x)E(x)：X X是偶数是偶数O(x):x是奇数是奇数 GZ(x):x大于大于0 02.1 谓词逻辑表示学问谓词逻辑表示学问2022/10/30第三步第三步2.1 谓词逻辑表示学问谓词逻辑表示学问在一个房间里，有一个机器人在一个房间里，有一个机器人RobotRobot，一个壁橱，一个壁橱AlcoveAlcove，一个积木块一个积木块BoxBox，两个桌子，两个桌子A A和和B B。起先时，。起先时，BobotBobot在在Alcove

4、Alcove旁边且两手是空的，旁边且两手是空的，A A上放着上放着BoxBox，B B上是空的。上是空的。RobotRobot将把将把BoxBox从从A A移到移到B B上上例例3 3第一步第一步第二步第二步TABLE(x)：x是桌子是桌子 EMPTYHANDEDEMPTYHANDED(x)：x双手是空的双手是空的AT(x,y):x在在y旁边旁边 HOLDS(y,w)HOLDS(y,w)：y y拿着拿着w wON(w,x):wON(w,x):w在在x x上上 EMPTYTABLE(x)EMPTYTABLE(x)：桌子：桌子x x上是空的上是空的个体词：个体词：ROBOT,BOX,ALCOVE,

5、A,B 2022/10/30设有如下语句，请用谓词公式把他们表示出来设有如下语句，请用谓词公式把他们表示出来(1)有的人宠爱梅花，有的人宠爱菊花，有的人既宠有的人宠爱梅花，有的人宠爱菊花，有的人既宠爱梅花又宠爱菊花爱梅花又宠爱菊花。(2)要想出国留学，必需通过外语考试要想出国留学，必需通过外语考试(2)全部人都有饭吃全部人都有饭吃1.定义谓词及个体，确定每个谓词及个体的精确含义。定义谓词及个体，确定每个谓词及个体的精确含义。2.依据所要表达的事物或概念，为每个谓词中的变元赋依据所要表达的事物或概念，为每个谓词中的变元赋以特定的值。以特定的值。3.依据所要表达的学问的语义，用适当的连接符将各个依

6、据所要表达的学问的语义，用适当的连接符将各个谓词连接起来谓词连接起来,形成谓词公式。形成谓词公式。2.1 谓词逻辑表示学问谓词逻辑表示学问2022/10/30有的人宠爱梅花，有的人宠爱菊花，有的人既宠爱梅花又有的人宠爱梅花，有的人宠爱菊花，有的人既宠爱梅花又宠爱菊花宠爱菊花第一步第一步第二步第二步第三步第三步定义谓词：定义谓词：LIKE(x,y)：x宠爱宠爱y 定义个体词：定义个体词：Meihua，JuhuaLIKE(x,Meihua),LIKE(y,Juhua)LIKE(z,Meihua)LIKE(z,Juhua)2022/10/30要想出国留学，必需通过外语考试要想出国留学，必需通过外语考

7、试第一步第一步第二步第二步第三步第三步定义谓词：定义谓词：Want(x,y)：x想想y，Pass(x,y)：x通过通过y 定义个体词：定义个体词：goabroad,flanguagePass(x,flanguage),Want(x,goabroad)2022/10/30全部人都有饭吃全部人都有饭吃第一步第一步第二步第二步第三步第三步定义谓词：定义谓词：Havefood(x)：x有饭吃有饭吃2022/10/30自测题目自测题目1.李明每天下午踢足球李明每天下午踢足球2.合肥的夏天潮湿燥热合肥的夏天潮湿燥热3.宠爱打篮球的人必宠爱踢足球宠爱打篮球的人必宠爱踢足球2022/10/30动物动物isa生

8、物生物植物植物isaisaisa鱼鱼鸟鸟飞飞翅膀翅膀水水游泳游泳cancaninhave乌鸦乌鸦isa黑色黑色腐肉腐肉eatingcovering吃吃运动运动cancan2.2 语义网络学问表示语义网络学问表示2022/10/302.2 语义网络学问表示语义网络学问表示语义网络语义网络语义网络语义网络AKOAKOISHAVELocate-at山羊山羊动物动物羊羊猪猪绵羊绵羊野猪野猪哺乳动物哺乳动物头上有角头上有角羊毛羊毛森林森林AKOAKOAKOAKO猪和羊的语义网络2022/10/30框架名：框架名：主机品牌：联想主机品牌：联想1+1 生产厂商：北京联想集团公司生产厂商：北京联想集团公司 C

9、PU：品牌：品牌：Intel 型号：奔腾型号：奔腾/933 主板：品牌：主板：品牌：QDI 型号：型号：ATX VA5 内存：品牌：现代内存：品牌：现代 型号：型号：SDRAM 容量：容量：128MB 硬盘：品牌：硬盘：品牌：Seagate 型号：型号：ST320423A 容量：容量：20GB例例2.3 框架学框架学问问表示表示2022/10/30例：例：新华社新华社9月月16日电日电 国家气象台命名的国家气象台命名的“99年年2号号”台风于昨日下午台风于昨日下午4时在浙江舟山地区登陆，据时在浙江舟山地区登陆，据专家阅历，认为风力大于等于专家阅历，认为风力大于等于8级，但风力的精确级，但风力的

10、精确值，有待数据处理，目前尚未公布。此次台风造成值，有待数据处理，目前尚未公布。此次台风造成的损失，尚未得到报告，若须要具体的损失数字，的损失，尚未得到报告，若须要具体的损失数字，可电询自然灾难统计中心。另据介绍，事前曾得到可电询自然灾难统计中心。另据介绍，事前曾得到国际气象组织预报：昨日上午于太平洋赤道地区生国际气象组织预报：昨日上午于太平洋赤道地区生成的高压气旋，将向北移动，于浙江舟山地区登陆。成的高压气旋，将向北移动，于浙江舟山地区登陆。依国际惯例，将其命名为依国际惯例，将其命名为Carla飓风。我国也予以飓风。我国也予以承认，至于承认，至于Carla是否就是是否就是“99年年2号号”尚

11、须另加核尚须另加核实。实。2.3 框架学问表示框架学问表示2022/10/30Frame：台风：台风slot1：登陆时间：登陆时间 Value：9月月15日下午四时日下午四时 slot2：登陆地点：登陆地点 Value：浙江舟山地区：浙江舟山地区slot3：风力：风力 default：大于等于：大于等于8级级 slot4：损失：损失 If-needed：电询自然灾害统计中心：电询自然灾害统计中心slot5：名称：名称 Value：99年年2号号Default：Carla 飓风飓风 If-added：核查：核查Carla与与“61年年2号的关系并加注释号的关系并加注释2.3 框架学问表示框架学问

12、表示2022/10/303.1 子句集子句集消去存在量词消去存在量词1234谓词公式化为谓词公式化为子句集步骤子句集步骤重新命重新命名变元名变元利用等价利用等价关系消去关系消去谓词公式谓词公式中的中的“”和和“”利用等价关利用等价关系把系把“”“”移到紧靠谓移到紧靠谓词词存在量词不出现在全称量存在量词不出现在全称量词的辖域内，则用新的词的辖域内，则用新的个个体常量体常量替换存在量词；替换存在量词；存在量词位于一个或多个存在量词位于一个或多个全称量词的辖域内，则用全称量词的辖域内，则用全称量词的全称量词的函数函数取代存在取代存在量词量词2022/10/303.1 子句集子句集 把全把全称量词称量

13、词移到公移到公式左边式左边8765谓词公式化为谓词公式化为子句集步骤子句集步骤消去全消去全称量词称量词利用等价关利用等价关系把母式化系把母式化为合取范式为合取范式9使不同子使不同子句中的变句中的变元不同名元不同名消去合取消去合取词，生成词，生成子句集子句集2022/10/303.1 子句集子句集2022/10/30例如：例如：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)取取v

14、0=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/10/30(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)(5)令令g3=g2t2/v2,=a/z

15、,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/10/30已知能阅读的都是有文化的；海豚是没有文化的；某些海豚是已知能阅读的都是有文化的；海豚是没有文化的；某些海豚是有智能的；证明：某些有智能的并不能阅读。有智能的；证明：某些有智能的并不能阅读。证明：符号化证明：符号化R(x):x能阅读能阅读 L(x):x有文化有文化 D(x)：x是海豚是海豚 I(x)：x有智能有智能3.3 运用归结原理证明问题运用归结原理证明问题

16、2022/10/30I(w)R(w)I(A)R(A)R(x)L(x)D(y)L(y)L(A)NILD(A)D(A)3.3 运用归结原理证明问题运用归结原理证明问题2022/10/30例例4.6 已知已知F1：王：王(wang)先生是小李先生是小李(Li)的老师的老师 F2：小李和小张：小李和小张(zhang)是是 同班同学同班同学 F3：假如：假如x和和y是同班同学，则是同班同学，则x的老师就是的老师就是y的老师。的老师。求：小张的老师是谁？求：小张的老师是谁？解：解：1)定义谓词：定义谓词：T(x,y):x是是y的老师；的老师；C(x,y):x与与y是同班同学是同班同学3.4 运用归结原理求

17、解运用归结原理求解2022/10/30C(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(Wang,Zhang)T(Wang,Zhang)Wang/z,Li/xWang/u,Zhang/y3.4 运用归结原理求解运用归结原理求解2022/10/30作业作业1 某公司聘请工作人员，某公司聘请工作人员，A、B、C三人应三人应试，经面试后公司表示如下想法：试，经面试后公司表示如下想法：(1)三人中至少录用一人三人中至少录用一人 (2)假如录用假如录用A而不录用而不录用B，则确定

18、录用，则确定录用C (3)假如录用假如录用B，则确定录用，则确定录用C 求证：公司确定录用求证：公司确定录用C2022/10/30作业作业2 已知以下的事实：已知以下的事实：Marcus是人。是人。Marcus是罗马人。是罗马人。Caser是一位统治是一位统治者。者。全部罗马人或忠于全部罗马人或忠于Caser或仇恨他。或仇恨他。每个人都忠于某个人。每个人都忠于某个人。人们只想暗杀人们只想暗杀他们不忠于的统治者。他们不忠于的统治者。Marcus试图暗杀试图暗杀Caser。求证：求证：Marcus仇恨仇恨Caser。2022/10/30作业作业3 设设A、B、C三人中有人从不说真话，三人中有人从不

19、说真话，也有人从不说假话，某人向这三个人分别也有人从不说假话，某人向这三个人分别提出同一个问题：谁是说谎者？提出同一个问题：谁是说谎者？A答：答：“B和和C都是说谎者都是说谎者”；B答答“A和和C都是说谎都是说谎者者”；C答：答：“A和和B中至少有一个是说谎中至少有一个是说谎者。者。”求谁是醇厚人，谁是说谎者？求谁是醇厚人，谁是说谎者？2022/10/30 例例2 2 设有如下学问设有如下学问R1R1：IF A THEN(20IF A THEN(20，1)B1(0.03)1)B1(0.03)R2R2：IF B1 THEN(300IF B1 THEN(300，0.0001)B2(0.01)0.0

20、001)B2(0.01)求：当证据求：当证据A A必定发生时必定发生时,P(B2/A),P(B2/A)的值是多少？的值是多少？解解:（1）由于）由于A必发生，由必发生，由R1得得 （2）由于）由于B1不是必发生的，所以需作插值处理。不是必发生的，所以需作插值处理。例例1 14.1 主观主观bayes方法方法2022/10/30 当当时，有时，有，所以在此区间插值。，所以在此区间插值。由于由于4.1 主观主观bayes方法方法2022/10/30例例2：设有如下学问设有如下学问 r1:IF E1 THEN (20，1)Hr2:IF E2 THEN (300,1)H 已知已知P(H)=0.03，若

21、证据，若证据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.274.1 主观主观bayes方法方法2022/10/30解法解法2：更新法：更新法2022/10/30例例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

22、)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|S1S2S3)4.1 主观主观bayes方法方法2022/10/30E1H1E2E3H2(2,0.000001)(65,0.01)(300,0.0001)(100,0.000001)0.20.40.030.10.012022/10/30解解(1)求求P(H1|S1)2022/10/30(2)求求P(H1|S2)2022/10/302022/10/302022/10/302022/

23、10/302022/10/304.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;初始证据为初始证据为A1,A2,A3的可信度的可信度CF均设为均设为1，即即,CF(A1)=CF(A2)=CF(A3)=1,对对B1,B2一窍不通一窍不通,求求CF(B1)和和CF(B2)。例例 1 12022/10/30 解解:由于对由于对B1,B2一窍不通，所以运用合成算法进行计算。一窍不通，所以运用合成算法进行计算。由题意得到推理网络

24、如下图所示。由题意得到推理网络如下图所示。B B2 2B B1 1A A3 3A A1 1A A2 24.2 C-F方法方法2022/10/30(1)(1)对于学问对于学问R1,R2,R1,R2,分别计算分别计算CF1(B1),CF2(B1)CF1(B1),CF2(B1)(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得

25、到得到 4.2 C-F方法方法2022/10/30例例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/10

26、/30(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(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方法方法2022/10/30(3)求求CF1

27、,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方法方法2022/10/30ABCDE43 4 523例：五个城市间的交通路线图，A城是出发地E是目的地，两城市间的交通费用(代价)如图数字所示。求从A到E最小费用交通路线。将交通图转换为代价树将交通图转换为代价树从起始节点从起始节点A起先，把与它干脆相邻的起先，把与它干脆相邻的节点作为它的子节点。节点作为它的子节点。若一个节点已作为某节点的先辈节点若

28、一个节点已作为某节点的先辈节点时，就不能再作为这个节点的子节点。时，就不能再作为这个节点的子节点。图中除起始节点图中除起始节点A外，其它节点都可能要在代外，其它节点都可能要在代价树中出现多次，为区分它的多次出现分价树中出现多次，为区分它的多次出现分别用下标别用下标12标出。标出。5.1 代价树宽度优先搜寻代价树宽度优先搜寻2022/10/30A B1E1 9A B1D2E3 1 1A C1D1E2 8A C1D1B2E4 1 42 4 5AC1B1D1D2E1E2B2C2E3E43 43 4 2 355.1 代价树宽度优先搜寻代价树宽度优先搜寻2022/10/30f(n):从初始结点经过从初始

29、结点经过n结点到达目的结点的最优路径的代价估结点到达目的结点的最优路径的代价估计值。作用是评价计值。作用是评价open表中各节点的重要性，确定表中各节点的重要性，确定open表表的次序的次序h(n):从从n到目标结点的最佳路径的估计代价，称为启发函数。到目标结点的最佳路径的估计代价，称为启发函数。g(n):从初始结点到从初始结点到n已经付出的实际代价已经付出的实际代价 g(n)和和h(n)各占适当的比重各占适当的比重一般地，一般地，g(n)的比重越大，越倾向于广度优先搜寻，的比重越大，越倾向于广度优先搜寻，h(n)的比重越大，越倾向于深度优先搜寻。的比重越大，越倾向于深度优先搜寻。2.估价函数

30、估价函数 一般形式：一般形式：f(n)=g(n)+h(n)5.2 启发信息和估价函数启发信息和估价函数2022/10/30f(n)=d(n)+W(n)其中：其中：d(n)表示节点表示节点n在搜寻树中的深度在搜寻树中的深度 W(n)表示节点表示节点n中中“不在位不在位”的数码个数。的数码个数。计算初始状态计算初始状态S0的估价函数值的估价函数值f(S0)【例例】八数码难题。设问题的初始状态八数码难题。设问题的初始状态S S0 0和目标状态和目标状态S Sg g如下图所示，且估价函数为如下图所示，且估价函数为2 8 31 47 6 5 1 2 38 47 6 5 S0 Sg5.2 启发信息和估价函

31、数启发信息和估价函数2022/10/302 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 启发信息和估价函数

32、启发信息和估价函数2022/10/30例：有如下结构的移动将牌游戏例：有如下结构的移动将牌游戏B:代表黑色将牌代表黑色将牌W：代表明色将牌：代表明色将牌E：代表该位置为空：代表该位置为空BEBW W BW规则：规则：要求：把全部要求：把全部B移至全部移至全部W的右边，计算的右边，计算h(x)5.2 启发信息和估价函数启发信息和估价函数当一个将牌移入相邻的空位置时，费用为当一个将牌移入相邻的空位置时，费用为1个单位。个单位。一个将牌至多可跳过两个将牌进入空位置，其费用等于跳过的一个将牌至多可跳过两个将牌进入空位置，其费用等于跳过的将牌数加将牌数加1因为因为W左边的左边的B越少越接近目标因此可用越

33、少越接近目标因此可用W左边左边B的个数的个数作为作为h(x);h(x)=3*(每个每个W左边左边B的个数的总和）的个数的总和）2022/10/30广度优先、代价树广度优先是全局择优搜寻的特例2 28 83 31 14 47 76 65 51 12 23 38 84 47 76 65 5估计函数：估计函数：f(x)=d(x)+h(x)d(x)表示节点表示节点x的深度的深度 h(x)表示节点的格局与目标格局不相同的牌数表示节点的格局与目标格局不相同的牌数例：用全局择优搜寻求解重排九宫问题例：用全局择优搜寻求解重排九宫问题初始状态初始状态S0S0目标状态目标状态SgSg5.2 全局择优搜寻全局择优搜

34、寻2022/10/302 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 2 37 8 4 6 51 2 3 8 47 6 54 4 5 55 6 4 644SgS1S2S36该问题的解为：该问题的解为：S0S1S2S3Sg5.2 全局择优搜寻全局择优搜寻2022/10/30例例八数码难题。八数码难题。S0Sgf(n)=d(n)+P(n)d(n)深度深度P(n)与目标距离与目标

35、距离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*=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=42022/10/30例例 修道士和野人问题。修道士和野人问题。解：用解：用m表示左岸的修道士人数，表示左岸的修道士人数，

36、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)为节点的深度。为节点的深度。通过分析可知通过分析可知h(n)h*(n)，满足满足A*算法的限制条件。算法的限制条件。M-C问题的搜寻过程如下图所示。问题的搜寻过程如下图所示。5.3 A*算法应用举例算法应用举例2022/10/30(3,2,0)(3,1,0)(2,2,0)h

37、(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=1 f=8h=0 f=8h=4 f=5h=4 f=5h=2 f=6h=2 f=7传教士和野人问题的搜寻图传教士和野人问题的搜寻图5.3 A*算法应用举例算法应用举例2022/10/306.1 基于决策树的归纳学习方法基于决策树的归纳学习方法1.决策树决策树 决策树由一个根结点，若干叶结点和若干

38、非叶结点构成。决策树由一个根结点，若干叶结点和若干非叶结点构成。根结点对应于学习任务。根结点对应于学习任务。每个叶结点都包含一个分类名，即包含一个概念。每个叶结点都包含一个分类名，即包含一个概念。每个非叶结点都包含一个属性测试，对该属性可能取的每一个每个非叶结点都包含一个属性测试，对该属性可能取的每一个值用一个分支引出到另一个结点。值用一个分支引出到另一个结点。2.ID3算法算法假设：每个例子仅属于两种分类之一：正例和反例。假设：每个例子仅属于两种分类之一：正例和反例。例子的属性集用例子的属性集用A表示，单个属性表示为表示，单个属性表示为ai(i=1,2,|A|),|A|表示表示A所含属性的数

39、量。对每个属性所含属性的数量。对每个属性ai,其可能的值集用其可能的值集用Vi表示，表示，单个值用单个值用vij表示，表示，j=1,2,|Vi|,其中其中|Vi|是是ai可能取的值的数可能取的值的数目。目。2022/10/30(1)(1)令根结点包含例子集中全部的实例令根结点包含例子集中全部的实例(2)(2)假如当前决策树中每一个叶结点包含的例子都属于同一分假如当前决策树中每一个叶结点包含的例子都属于同一分类，即或者都是目标概念的正例，或者都是反例，则停止类，即或者都是目标概念的正例，或者都是反例，则停止划分。划分。(3)(3)否则需对既包含正例又包含反例的叶结点进一步划分。否则需对既包含正例

40、又包含反例的叶结点进一步划分。(a)(a)须要进一步划分的叶结点所包含的例子组成子集须要进一步划分的叶结点所包含的例子组成子集S S(b)(b)找出对找出对S S来说来说E E值最小的属性值最小的属性abestabest(c)(c)依据属性依据属性abestabest的值的值VbestVbest对须要划分的叶结点所包含的子对须要划分的叶结点所包含的子例子集进行划分，每个例子集进行划分，每个Vbest,I(I=1,2,|Vbest|)Vbest,I(I=1,2,|Vbest|)将生成将生成一个分支。一个分支。(d)(d)执行步骤执行步骤(2)(2)6.2 ID3算法描述：算法描述：2022/10

41、/30例：假定按是否例：假定按是否“紧急紧急”这个概念对狗的集合进行分类，在类别栏正例即这个概念对狗的集合进行分类，在类别栏正例即“紧急紧急”的狗用的狗用“”标出，反例用标出，反例用“”标出，属性及取值由下表给出。标出，属性及取值由下表给出。对属性对属性“颜色颜色”序号序号 颜色颜色 体形体形 毛型毛型 类别类别1 1黑黑大大卷毛卷毛2 2棕棕大大光滑光滑3 3棕棕中中卷毛卷毛4 4黑黑小小卷毛卷毛5 5棕棕中中光滑光滑6 6黑黑大大光滑光滑7 7棕棕小小卷毛卷毛8 8棕棕小小光滑光滑9 9棕棕大大卷毛卷毛1010黑黑中中卷毛卷毛1111黑黑中中光滑光滑1212黑黑小小光滑光滑2022/10/

42、30因为因为E体形体形E颜色颜色E毛型，所以毛型，所以“体形体形”被选为划分属性如下图。被选为划分属性如下图。“大大”“小小”组成子例子集（组成子例子集（8个例子）个例子）算出算出E颜色颜色4 E毛型毛型6.490所以用属所以用属性性“颜色颜色”作其次步划分如右图作其次步划分如右图体形体形(+)(-+-)(-+-)大大中中小小体形体形(+)颜色颜色大大中中小小(-)黑黑(+-)棕棕颜色颜色(-)(+-)黑黑棕棕序号序号颜色颜色体形体形毛型毛型类别类别3 3棕棕中中卷毛卷毛4 4黑黑小小卷毛卷毛5 5棕棕中中光滑光滑7 7棕棕小小卷毛卷毛8 8棕棕小小光滑光滑1010黑黑中中卷毛卷毛1111黑黑中中光滑光滑1212黑黑小小光滑光滑2022/10/30最终用属性最终用属性“毛型毛型”进行划分，得到进行划分，得到体形体形(+)颜色颜色大大中中小小(-)黑黑(+-)棕棕颜色颜色(-)(+-)黑黑棕棕(+)(-)(-)(+)光滑光滑光滑光滑卷毛卷毛卷毛卷毛2022/10/30毛型毛型颜色颜色光滑光滑卷毛卷毛体形体形黑黑体形体形棕棕颜色颜色体形体形体形体形黑黑棕棕(+)(+)(-)(-)(-)(-)大大小小中中(+)(+)(+)(+)(-)(-)大大小小中中(+)(+)(-)(-)(-)(-)大大小小中中(+)(+)(-)(-)(+)(+)大大小小中中2022/10/30