人工智能原理及其应用王万森第版课后习题答案

人工智能原理及其应用王万森第版课后习题答案LELEwasfinallyrevisedonthemorningofDecember16,20201什么是智能智能包含哪几种能力解：智能主要是指人类的自然智能。一般认为，智能是是一种认识客观事物和运用知识解决问题的综合能力。智能包含感知能力，记忆与思维能力，学习和自适应能力，行为能力人类有哪几种思维方式各有什么特点解：人类思维方式有形象思维、抽象思维和灵感思维形象思维也称直感思维，是一种基于形象概念，根据感性形象认识材料，对客观对象进行处理的一种思维方式。抽象思维也称逻辑思维，是一种基于抽象概念，根据逻辑规则对信息或知识进行处理的理性思维形式。灵感思维也称顿悟思维，是一种显意识与潜意识相互作用的思维方式。什么是人工智能它的研究目标是什么解：从能力的角度讲，人工智能是指用人工的方法在机器（计算机）上实现智能；从学科的角度看，人工智能是一门研究如何构造智能机器或智能系统，使它能模拟、延伸和扩展人类智能的学科。研究目标：对智能行为有效解释的理论分析；解释人类智能；构造具有智能的人工产品；什么是图灵实验图灵实验说明了什么图灵实验可描述如下，该实验的参加者由一位测试主持人和两个被测试对象端进行会话。测试开始后，由测试主持人向被测试对象提出各种具有智能性的问题，但不能询问测试者的物理特征。被测试对象在回答问题人工智能的发展经历了哪几个阶段？兴起解：与脑科学与认知科学的交叉研究智能模拟的方法和技术研究人工智能有哪几个主要学派各自的特点是什么解：符号主义：又称为逻辑主义、心理学派或计算机学派，是基于物理符号系统假设和有限合理性原理的人工智能学派。符号主义认为人工智能起源于数理逻辑，人类认知（智能）的基本元素是符号，认知过程是符号表示上的一种运算。联结主义：又称为仿生学派或生理学派，是基于神经网络及网络间的联结机制与学习算法的人工智能学派。联结主义认为人工智能起源于仿生学，特别是人脑模型的研究。行为主义：又称进化主义或控制论学派，是基于控制论和“感为，取决于对外界复杂环境的适应，而不是表示和推理。人工智能有哪些主要研究和应用领域其中哪些是新的研究热点解：机器思维:推理、搜索、规划机器学习：符号学习、联结学习、知识发现和数据挖掘机器感知：机器视觉、模式识别、自然语言理解机器行为：智能控制、智能制造计算智能：神经计算、进化计算、模糊计算分布智能智能系统：专家系统、智能决策支持系统人工心理与人工情感研究热点：智能机器人、智能检索、智能游戏等。人工智能未来发展有哪些值得思考和关注的重要问题？解：多学科交叉研究集成智能研究智能网络研究认知计算与情感计算研究智能系统与智能服务确定性知识系统参考答案什么是知识有哪几种主要的知识分类方法解：知识是人们在改造客观世界的实践中积累起来的认识和经验；知识是对信息进行智能性加工中形成的对客观世界规律性的认识。分类：按适用范围：常识性知识、领域性知识按确定性：确定性知识、不确定性知识什么是知识表示知识表示有哪些要求解：知识表示就是对知识的描述，即用一些约定的符号把知识编码成一组可以被计算机直接识别，并便于系统使用的数据结构一介谓词逻辑表示法非结构化方法产生式陈述性知识表示语义网络结构化方法框架结构知识表示方法要求：表示能力，可利用性，可组织性与可维护性，可理解性和可实现性从心理学的角度看，推理有哪两种比较典型的观点它们的含义是什么结构观点：这种观点从结构的角度出发，认为推理由两个以上判断所组肯定或否点的思维活动。基础上所进行的一系列加工操作，其代表人物克茨提出了如下人类推理的公式：什么是推理它有哪些分类方法解：推理是由具体事例归纳出一般规律，或者根据已有的知识推出新的结论的思维过程分为演绎法和归纳法推理中的控制策略包括哪几个方面的内容主要解决哪些问题解：包括推理策略和搜索策略推理策略主要解决推理方向，求解策略，限制策略，冲突消解策略等搜索策略主要解决推理线路，推理效果，推理效率等问题什么是命题什么是命题的真值解：一个陈述句称为一个断言，凡有真假意义的断言称为命题。命题的意义通常称为真值，当命题的意义为真时，则称该命题的真值为真。什么是论域？什么是谓词解：论域是由所讨论对象之全体构成的非空集合。论域中的元素称为个体，论域也常称为个体域。在谓词逻辑中，命题是用谓词来表示的。一个谓词可分为谓词名和个体两部分。什么是自由变元什么是约束变元当一个谓词公式含有量词时，区分个体变元是否受量词的约束是很重要辖域，辖域内与量词中受约束的变元称为约束变元，不受约束的变元称为自由变元。设有如下语句，请用相应的谓词公式分别把他们表示出来：(1)有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花。解：定义谓词P(x)：x是人L(x,y)：x喜欢y将知识用谓词表示为：(有人每天下午都去打篮球。解：定义谓词将知识用谓词表示为：(x)(定义谓词将知识用谓词表示为：定义谓词使用计算机将知识用谓词表示为：凡是喜欢编程序的人都喜欢计算机。解：定义谓词P(x)：x是人L(x,y)：x喜欢y将知识用谓词表示为：(用谓词表示法求解机器人摞积木问题。设机器人有一只机械手，要处理的世界有一张桌子，桌上可堆放若干相同的方积木块。机械手有4个操作积木的典型动作：从桌上拣起一块积木；将手中的积木放到桌之上；在积木上再摞上一块积木；从积木上面拣起一块积木。积木世界的布局如下图所示。ABCCA解先定义描述状态的谓词ABCCA空的。

人摞积木问题

CLEAR(x)：积木x上面是ON(x,y)：积木x在积木y的上面。)：积木x)：机械手抓住。y问题的初始状态是：ONTABLE(A)ONTABLE(B)ON(C,A)CLEAR(B)CLEAR(C)HANDEMPTY问题的目标状态是：ONTABLE(C)ON(B,C)ON(A,B)CLEAR(A)HANDEMPTY再定义描述操作的谓词4。)：在积木x。)：从积木x。其中，每一个操作都可分为条件和动作两部分，具体描述如下：Pickup(x)条件：ONTABLE(x)，HANDEMPTY，CLEAR(x)Putdown(x)条件：HOLDING（x）动作：删除表：HOLDING（x）添加表：ONTABLE(x)，CLEAR(x)，HANDEMPTYStack(x,y)条件：HOLDING（x），CLEAR(y)动作：删除表：HOLDING（x），CLEAR(y)Upstack(x,y)条件：HANDEMPTY，CLEAR(x)，ON(x,y)问题求解过程利用上述谓词和操作，其求解过程为：ONTABLE(A)

ONTABLE(A)ONTABLE(B)

Upstack(C,

ONTABLE(B)

Putdown(CONTABLE(B)Pickup(ONTABLE(A) ONTABLE(A)ON(C,A)

ONTABLE(NTABLE(C)ONTABLE(C)ONTABLE(C)

Stack(B,ONTABLE(C)

Pickup( Stack(A,ON(B,C)用谓词表示法求解农夫、狼、ftLA(NBC菜全部放ON(B,C)左岸，现在ON(B,C

全部送到河的右岸去，农夫有一条船，过河时，除CLEAR(A)农夫外船上至多能载狼、ft羊、白菜中的一种。狼要吃ft羊，ft羊要吃白菜，除非农夫在那里。似规划出一个确保全部安全过河的计划。请写出所用谓词的定义，并给出每个谓词的功能及变量的个体域。解：(1)先定义描述状态的谓词要描述这个问题，需要能够说明农夫、狼、羊、白菜和船在什么位置，为简化问题表示，取消船在河中行驶的状态，只描述左岸和右岸的状态。并且，由于左岸和右岸的状态互补，因此可仅对左岸或右岸的状态做直接描述。本题选择对左岸进行直接描述的方法，即定义谓词如下：AL(x)：x在左岸x问题的初始状态：AL(农夫)AL(白菜)(2)再定义描述操作的谓词本题需要以下4)：农夫带着x)：农夫带着x对上述每个操作，都包括条件和动作两部分。它们对应的条件和动作如下：L-R：农夫划船从左岸到右岸添加表：AL(船)，AL(农夫)L-R(羊)：农夫带着羊划船从左岸到右岸添加表：AL(船)，AL(农夫)，AL(羊)R-L：农夫划船从右岸到左岸R-L(羊)：农夫带着羊划船从右岸到左岸AL(农夫)(船)AL(白菜)

AL(狼)AL(白菜)R-LAL(农夫)

AL(农) AL(船)

(农夫)AL(农

AL(羊)

AL(农夫)求解修道士和野L题。在河的北有三个修道士、三个野人和) 农

AL(船)

AL(船)一条船，修道士们想用这条船将所有的人都运过河去，但要受到以下条件限制：

AL(船)

AL(羊)

AL(羊)修道士和野人都会划船，但船一次只能装运两个人。在任何岸边，野人数不能超过修道士，否则修道士会被野人吃掉。假定野人愿意服从任何一种过河安排，请规划出一种确保修道士安全的过河方案。要求写出所用谓词的定义、功能及变量的个体域。解：（1）定义谓词先定义修道士和野人人数关系的谓词：G(x,y,S)：在状态S下x大于yGE(x,y,S)：在状态S下x大于或等于y再定义船所在岸的谓词和修道士不在该岸上的谓词：SzSx其中，z,x,y的含义同上。该谓词的含义是：状态S下，在z岸，保证修道士安全，当且仅当修道士不在该岸上，或者修道士在该岸上，但人数超过野人数。该谓词同时也描述了相应的状态。再定义描述过河方案的谓词：y1Safety(L,x-x1,y-y1,Safety(R,3-x+x1,3-y+y1,S’)∧Boat(L,S)y2条件：Safety(R,3-x-x2,3-y-y2,Safety(L,x+x2,y+y2,Boat(R,S)动作：Safety(R,3-x-x2,3-y-y2,Safety(L,x+x2,y+y2,Boat(L,L-R(3,1,3,1,S0)L-R(3,0,3,2,S0)Safety(L,2,2,S1)∧Safety(R,1,1,S1)∧Boat(R,S1)Safety(L,3,1,S1’)∧Safety(R,0,2,S1’)∧Boat(R,S1’)R-L(2,1,2,0,S1)R-L(3,0,1,1,1)L-R(3,0,2,2,S2)R-L(3,0,0,1,S3)L-R(3,2,1,0,S4)R-L(1,1,1,1,S5)L-R(2,2,2,0,S6)R-L(0,0,2,1,S7)L-R(0,0,3,2,S8)R-L(0,1,1,0,S9)L-R(1,1,1,1,S10)什么是产生式它的基本形式是什么代表什么含义（）1934规则提出了一种称为波斯特机的计算模型，模型中的每条规则称为产生式。产生式的基本形式PQPPQQ产生式表示的特征是什么？解：优点：自然性、模块性、有效性缺点：效率低性、不方便表示结构性知识的有向图何谓语义网络它有哪些基本的语义关系解：语义网络：用实体以及语义关系来表达知识的有向图基本的语义关系：①实例关系（ISA）:(是一个)(一个事物是另一个事物的具体例子)②分类关系（AKO）:(是一种)子类与超类③成员关系(A-member-of):是一名:HaveCanAge⑤包含关系⑥位置关系:Before，after⑦located-onlocated-underlocated-outsidelocated-atlocated-insideAKOAKOAKOAKO学生 职业 人计算计算AKOowner设备owns占有AKO占有资情况高老师从7解：ISA7ISA高老老Sua高老老

8月计算机系学End计算机系学ObjecActio

讲课事

Caurs解：男 女研究生本HaveHavHave创新公司在科海大街32Address 56 创新公

3经Age经刘 IsaHave硕士学位解：Participa红队

比赛AKO足球赛

Outcome

3:2Participan请把下列命题用一个语义网络出来：树和草都是植物；植物解：植物AKOAKOAKOAKO草叶和根；草解：叶Have植物

根Have是一 是一水草是草，且草解：AKO植物

AKO

Live水草 水中果树是树，且会结果；解：AKO植物

AKO树

Can果树 结果梨树是果树中的一种，它会结梨。解：AKO AKO Can树 果 梨树 结梨试述语义网络中求解问题的一般过程解：语义网络的推理过程主要有两种，一种是继承，另一种是匹配。继承是指把对事物的描述从抽象节点传递到具体节点。匹配是指在知识库的语义网络中寻找与待求解问题相符的语义网络模式。试述语义网络表示法的特点联想性自然性缺点：非严格性，复杂性何谓框架框架的一般形式是什么解：框架表示法是在框架理论的基础上发展起来的一种结构化知识表示方法。框架通常由描述事物各个方面的若干槽组成，每一个槽也可以根据实际情况拥有若干个侧面，每一个侧面又可以拥有若干个值。何谓实例框架它与框架有什么关系解：当人们把观察或认识到的具体细节填入框架后，就得到了该框架的一个具体实例，框架的这种具体实例被称为实例框架。通用结构与具体实例，抽象与具体。何谓框架系统何谓框架系统的横向联系何谓框架系统的纵向联系解：在框架理论中，框架是知识的基本单位，把一组有关的框架连接起来便可形成一个框架系统。在框架系统中，系统的行为由该系统内框架的变化来实现，系统的推理过程由框架之间的协调完成。纵向联系：表示那种具有演绎关系的知识结构，下层框架与上层框架之间具有一种继承关系，这种具有继承关系的框架之间的联系称为纵向联系。横向联系：由于一个框架的槽值或侧面值可以是另外一个框架的名字，这就在框架之间建立了另外一种联系，称为横向联系。3，降水概率解：Frame<天气预报>地域：北京时段：今天白天天气：晴风向：偏北风力：3级降水概率：15%按“师生框架”、“教师框架”、“学生框架”的形式写出一个框架系统的描述。解：师生框架Frame<Teachers-Students>Name：Unit（Last-name，First-name）Telephone：HomeUnit（Number）MobileUnit（Number）教师框架Frame<Teachers>AKO<Teachers-Students>Major：Unit（Major-Name）学生框架Frame<Students>AKO<Teachers-Students>Major：Unit（Major-Name）在框架系统中，问题求解的一般过程是什么？解：特性继承框架的匹配与填槽框架表示法的特点有哪些？解：优点：结构性，深层性，继承性，自然性。缺点：缺乏框架的形式理论，缺乏过程性知识表示，清晰性难以保证何谓产生式系统产生式推理的基本结构由哪几部分组成解：利用产生式知识表示方法所进行的推理称为产生式推理，由此产生的系统为产生式系统基本结构：综合数据库，规则库，控制系统什么是产生式的正向推理其基本过程是什么解：从已知事实出发，正向使用推理规则的推理方法。过程：把用户提供的初始证据放入综合数据库；出，否则，执行下一步；否则转推出的新事实加入综合数据库中，然后转）；综合数据库中，然后转否则表示无解，失败退出。什么是逆向推理其基本过程是什么解：以某个假设目标作为出发点的推理方法过程：将问题的初始证据和要求证的目标（称为假设）假设集；该假设成立。此时，若假设集为空，则成功退出。否则，扔执行）。若该假设不在数据库中，则执行下一步；则询问用户寻找新的假设。若不是，则转），若能由某个知识导出，则执行下一步；将知识库中可以导出该假设的所有知识构成一个可用知识集；检查可用知识集是否为空，若空，失败退出。否则执行下一步；按冲突消解策略从可用知识集中取出一个知识，继续执行下一步；将该知识的前提中的每个子条件都作为新的假设放入假设集，转）什么是混合推理它由哪几种实现方式实现：先正后逆，先逆后正，随机什么是置换什么是合一：在不同谓词公式中，往往会出现多个谓词的谓词名相同但个体不同的情变元进行替换叫置换。合一利用置换使两个或多个谓词的个体一致。判断下列公式是否为可合一，若可合一，则求出其相应的置换解：(1)可合一，其最一般和一为：σ={a/x,b/y}。：σ={f(x)/y,b/z}σ={f(b)/y,b/x}：σ={y/x}。什么是自然演绎推理它所依据的推理规则是什么从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理推理规则：等价式，永真蕴涵式，置换，合一什么是谓词公式的可满足性什么是谓词公式的不可满足性教材页什么是谓词公式的前束范式什么是谓词公式的Skolem范式教材P56什么是字句集如何将谓词公式化为字句集教材把下列谓词公式化成子句集：(1)(x)((2)(x)((3)(x)((4)(x)(y)(x)(Skolem标准型，且{P(x,y),Q(x,y)}再进行变元换名得子句集：S={P(x,y),Q(u,v)}x)(x)(此公式已为Skolem标准型。再消去全称量词得子句集：S={P(x,y)∨Q(x,y)}(3)对谓词公式(x)(y)(P(x,y)∨(Q(x,y)→R(x,y)))，先消去连接词“→”得：x)(此公式已为前束范式。再消去存在量词，即用Skolem函数y此公式已为Skolem标准型。最后消去全称量词得子句集：S={P(x,f(x))∨Q(x,f(x))∨R(x,f(x))}(4)对谓词(x)(y)(z)(P(x,y)→Q(x,y)∨R(x,z))，先消去连接词“→”得：(x)(y)(再消去存在量词，即用Skolem函数yx)(此公式已为Skolem标准型。最后消去全称量词得子句集：鲁滨逊归结原理的基本思想是什么？解：鲁滨逊归结原理也称为消解原理。其基本思想是把永真性的证明转化为不可满足性的证明。可满足性的证明。即要证明P->Q判断下列子句集中哪些是不可满足的：(1)(2)(3)(4){P(xQ(x),P(yR(y),P(a),S(a),S(zR(z)}(5)(6)解：(1)不可满足，其归结过程为：QP∨QQ不可满足，其归结过程为：P PQ

ILQ Q不是不可满足的，原因是不能由它导出空子句。NIL不可满足，其归结过程略对下列各题分别证明GF,F,…,F1 2 n(1)F:(x)(y)(P(x,y)G:(y)(x)(P(x,y)(2)F:(G:((3)F:(x)(G:P(f(a))∧P(y)∧Q(y)(4)F:(L))1F:(2G:(Q(x))(5)F:(1F:(2G:(x)(S(x)∧R(x))FGS={P(a,b),P(x,b)}再对S进行归结：{a/x} P(a, NIL所以，G是F的逻辑结论FG由F1由于G(x)(P(x)∨Q(x))，可得：S={P(x)∨Q(x)}2因此，扩充的子句集为：再对S进行归结：{a/b}

Q(a)∨Q(a{a/x}

P(x)∨Q(x){a/x}

P(a)

P(x)NIL所以，G是F的逻辑结论设已知：如果xyzxz(2)，一定存在一个人uyz再用谓词把问题描述出来：已知x)(y)(求证结论 u)(然后再将和G化成子句集：①F(x,y)∨F(y,z)∨GF(x,z)②P(r)∨F(s,r)③P(u)④GF(v,u))对上述扩充的子句集，其归结推理过程如下GF(v,u{x/v,z/u}

{x/s,y/r}

P(r)∨F(s,F(y,z/r}

P(r)∨F(s,{y/z}{y/u}

P(y)∨P(z由于导出了空子句，故结论得证P(y) P(u)假设张被盗，公安局派出5个人去调查。案情分析时，贞察员A说：“赵与钱NIL中至少有一个人作案”，贞察员B说：“钱与孙中至少有一个人作案”，贞察员C说：“孙与李中至少有一个人作案”，贞察员D说：“赵与孙中至少有一个人与此案无关”，贞察员E5员的话都是可信的，使用归结演绎推理求出谁是盗窃犯。解：(1)先定义谓词和常量设x设作案者为，则要求的结论是C(u)∨C(u)对上述扩充的子句集，按归结原理进行归结，其修改的证明树如下：{Q/u} 因此，钱是盗窃犯。实际上，本案的盗窃犯不止一人。根据归结原理还可以得出C(SC((Q)

C(Q(S

C(uC(S)

C(u)∨C(u{S/u}

C(Q)C(S)因此，孙也是盗窃犯。C(S)设已知：

C(S)

C(u)∨C(u请用归结演绎推理证明：有些很聪明的人并不识字。解：第一步，先定义谓词，设xyz第二步，将已知事实和目标用谓词公式表示出来能阅读的人是识字的：(x)(R(x))→K(x))海豚不识字：(y)(K(y))有些海豚是很聪明的 z)W(z)有些很聪明的人并不识字 第三步，将上述已知事实和目标的否定化成子句集：K(y)W(z)W(z)∨K(x))第四步，用归结演绎推理进行证明W(z)∨K(x))K(z章确定性推理部分

W(z)W(z答案什么是搜索有哪两大类不同的搜索方法两者的区别是什么推理路线，使问题得以解决的过程称为搜索或搜索盲目搜索是按预定的控制策略进行搜索，在搜索过程中获得的中间信息并不改变控制策略启发式搜索是在搜索中加入了与问题有关的启发性信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解过程，并找到最优解。状态空间搜索是指用状态空间法来表示问题所进行的搜索。与/或搜索是指用问题归约法来表示问题时所进行的搜索。什么是状态空间用状态空间表示问题时，什么是问题的解什么是最优解最优解唯一吗状态空间相互关系所构成的集合，它可用一个三元祖S,F,）,S由初始状态到目标状态所使用的算符序列就是该问题的一个解。使某目标函数达到最优值（最大值或最小值）的任一可行解，都称为该问题的一个最优解。最优解不唯一。什么是与树什么是或树什么是与/或树什么是可解节点什么是解树解：把一个原问题分解为若干个子问题可用一个“与树”来表示。把一个原问题变换为若干个子问题可用一个“或树”来表示。如果一个问题既需要通过分解，有需要通过变换才能得到其本原问题，则其归约过程可用一个“与/或树”来表示在与/或树中，满足以下三个条件之一的节点为可解节点：任何终止节点都是可解节点是可解节点节点。解树：由可解节点构成，并且有这些可解节点可以推出初始节点为可解节点的子树为解树。closedopen有一农夫带一条狼，一只羊和一筐菜从河的左岸乘船到右岸，但受下列条件限制：船太小，农夫每次只能带一样东西过河如果没有农夫看管，则狼要吃羊，羊要吃菜请设计一个过河方案，使得农夫、狼羊都能不受损失的过河，画出相应的状态空间图有一农夫带一条狼，一只羊和一框青菜与从河的左岸乘船倒右岸，但受到下列条件的限制：船太小，农夫每次只能带一样东西过河；(2)请设计一个过河方案，使得农夫、浪、羊都能不受损失的过河，画出相应的状态空间图。（农夫，狼，羊，菜）001把每次过河的一种安排作为一种操作，每次过河都必须有农夫，因为只解：第一步，定义问题的描述形式用四元组v110第二步，用所定义的问题状态表示方式，把所有可能的问题状态表示出来，包括问题的初始状态和目标状态。由于状态变量有4216状态：S0 1 2 3S=(0,1,1,1)4 5 6 7S=(1,0,1,1)8 9 10 11S=(1,1,1,1)12 13 14 15其中，状态S

和

分别是初始状态和目标3 6 7

9

0 15状态。第三步，定义操作，即用于状态变换的算符组F由于每次过河船上都必须有农夫，且除农夫外船上只能载狼，羊和菜中的一种，故算符定义如下：i）表示省略。i）。同样，对农夫的表示省略。这样，所定义的算符组F8第四步，根据上述定义的状态和操作进行求解。该问题求解过程的状态空间图如下：(0,0,0R(0(0,0,1L(1

L(3(0,1,0L(3

(1,0,1R(2(0,0,0L(2(1,1,0R(0(0,1,0L(2111C90°，其初始状态S0

和目标状态Sg

如图所示，请用广度优先搜索和深度优先搜索，求出从S0

到Sg

C1223131C12231314BA4243

和q2 A B CCB2333A2111344初始状态目标状态Sg图圆盘问题

别表示把ACqA B C应用广度优先搜索，可得到如下搜索树。在该搜索树中，重复出现的状态不再划出，节点旁边的标识Si态标识。由该图可以看出，从初始状态S0

到目标状态Sg

的路径是S)0 gCCBA222S0q33341144q22S3S1q34421323214434S2123321411123342114q43q2233143244S421S512qS621S84S711322 441232 4143 3112313 1322312144q4333443424qqqS922S1021S11334 211443321234344124S即Sg1242133211231243314442题的广度优先搜索树题的广度优先搜索树其深度优先搜索略。5要求从AA解：这个问题又称为旅行商问题travellingsalesmanproblem,TP

A10B289C1163128货郎担问题，是一个较有普遍性的实际应用问题。根据数学理论，对n个城市的旅行商问题，其封闭路径的排列总数为：

D9E

交通费用图(n!)/n=(n-1)!n=20350下图是对图4-32按最小代价搜索所得到的搜索树，树中的节点为城市名称，节点边上的数字为该节点的代价g。其计算公式为g(n)=g(n)+c(n,n)i+1 i i i+1,n)为节点n到

节点的边代价。i i+1 i i+1AA0102911B10C2D98C12D968B3D581239E116 891816E10E10B21C12E18386B17812C19312698812D203C25E31C8912986868D22E16B16D19B20E20C25D293B C3223D21E2624D25B E17142026B2427228991212CE276CB D63899E3333E31D2766D28B3188E26B2612D28B31E30D35D27C28E23B20E28C32B342A3010A30的最小代价搜索树A-C-D-E-B-A或A-B-E-D-C-A其实，它们是同一条路经。为什么说深度优先搜索和代价树的深度优先搜索可以看成局部择优搜索的两个特例？解：深度优先搜索、代价树的深度优先搜索以及局部优先搜索都是以子节点作为考察范围，但节点选择的标准不同。如果取估价函数f(n)=g(n)，则它将退化为代价树的深度优先搜索。如果取估价函数f(n)=d(n)，则它将退化为深度优先搜索。因此，深度优先搜索和代价树的深度优先搜索是局部择优搜索的两个特例。何谓估价函数在估价函数中，g（n）和h（n）各起什么作用见教材P82设有如下结构的移动将牌游戏：BBBWWE1。WB函数设WBf(x)=1+12=1BBWEWf(x)=2+12=1

BBWWE BBEWWBBEWBBEWW BEWBWEBWBWWBEBWWBWBEWBWEB局部择优搜索与全局择优搜WBWEBf(x)=6+3=f(x)=7+0=

f(x)=1+12=1f(x)=3+9=f(x)=4+6=f(x)=5+3=索的相同之处与区别是什么？根据搜索过程中选择扩展节点的范围，启发式搜索算法可分为全局择优搜从Open点进行扩展。设有如图所示的与/或树，请分别用与/或树的广度优先搜索和深度优先搜索求出解树。AABCDttt5t3t或树解：广度优先搜索：ABABCDttt5tt深度优先搜索：ABABCDttt5tt设有如图的与/或/树，请分别按和代价法及最大代价法求解树的代价。55A6BC7221DE23tttt或树解：若按和代价法，则该解树的代价为：h(A)=2+3+2+5+2+1+6=21若按最大代价法，则该解树的代价为：h(A)=max{h(B)+5,h(C)+6}=max{(h(E)+2)+5,h(C)+6}=max{(max(2,3)+2)+5,max(2,1)+6}=max((5+5,2+6)=10设有如图所示的博弈树，其中最下面的数字是假设的估值，请对该博弈树作如下工作：计算各节点的倒推值；剪枝技术剪去不必要的分枝。SASABCDEFGHIJKLMN05-3336-2354-30689-3图习题的博弈树值和剪≥SA≥SA≤≤B≥C≥D≥E≥F≤G≤-H≤IJ≤K≤L≤MN05-3336-2354-30689-3习题的倒推值和剪枝情况索策略部分参习题的倒推值和剪枝情况考答案什么是计算智能它包括哪些主要分支解：计算智能是借鉴仿生学的思想，基于对生物体的结构、进化、行为与机理的认识，以模型为基础，以分布、并行、仿生计算为特征去模拟生物体和人类的智能；P97请说明计算智能（CI）、人工智能（AI）及生物智能（BI）之间的关系。层是计算智能C），它通过数值计算来实现的；中层人工智能A），它是通过生物神经系统来实现的；顶层是生物智能B），它是通过生物神经系统来实现的。生物神经元由哪几部分组成各部分的功能是什么解：生物神经元由细胞体，轴突和树突三个主要部分组成细胞体是神经元主体，用于处理有树突接受的其他神经元传来的信号；轴突是用来向外传递神经元产生的输出电信号；树突是神经元输出端，用于接收从其他神经元的突触传来的信号什么是人工神经元它有哪几种主要模型解：人工神经元是对生物神经元的抽象和模拟。阈值型分段成性型积型什么是人工神经网络它有哪些联结方式解：人工神经网络是对人类神经系统的一种模拟。它有几种联结方式：前馈网络和反馈网络。人工神经网络的典型模型有哪几种？简述其中的两种主要模型。感知器模型hopfield网络模型P104什么是进化计算它包括哪些主要内容进化计算以达尔文进化论的“物竞天择，适者生存”作为算法的进化规引入到算法中。什么是遗传算法？简述其基本思想和基本结构。解：遗传算法是在模拟自然界生物遗传进化过程中形成的一种自适应优化的概率搜索算法。遗传算法的基本思想是用模拟生物和人类进化的方法来求解复杂问题遗传算法的基本结构：染色体编码，初始种群设定，适度函数设定，遗传操作设计等P112什么是种群什么是个体什么是染色体个体和染色体之间的关系是什么解：种群是指用遗传算法求解问题时，初始给定的多个解的集合，它是问题解空间的子集个体是指种群中的单个元素，它通常是由一个用于描述其基本遗传结构的数据结构来表示染色体是对个体进行编码后所得到的编码串。什么是遗传编码有哪几种常用的编码算法遗传编码是指把实际问题的结构变换为遗传算法的染色体结构。什么是适应度函数常用的适应度函数有哪几种解：适应度函数是一种用来对种群中各个个体的环境适应性进行度量的函数。其函数值决定着染色体的优劣程度，是遗传算法实现优胜劣汰的主要依据。常用的适用度函数有原始适应度函数什么是选择操作常用的选择操作有哪几种解：选择操作是指根据选择概率按某种策略从当前种群中挑选出一定数目的个体，使它们能够有更多的机会遗传到下一代中，常用的选择策略可分为比例选择，排序选择和竞技选择三种类型。什么是交叉操作常用的交叉操作有哪几种解：交叉选择是指按照某种方式对选择的父代个体的染色体的部分基因进行交配重组，从而形成新的个体。常用的交叉操作有二进制值交叉和实值交叉两种。什么是变异操作常用的变异操作有哪几种解：变异操作是指对选择中个体的染色体中的某些基因进行变动，以形成新的个体。常用的变异操作有二进制值变异和实值变异两种。设种群规模为4，采用二进制编码，适应度函数f（x）=x2，初始种群如表所示。编号编号个体串x适应度百分比累计百分比选中次数1010 100100 41100 120111 7若遗传操作规定如下：选择概率P4X和；交叉概率Pc

=1，交叉算法为单点交叉，交叉点为3，交叉顺序按个体在种群中的顺序；变异概率

=0。请完成本轮选择，交叉和变异操作，并给出所得到的下一m代种群。编号个体串x适应度百分比累计百分比选中次数101010100101004160110012144201117491001S01S02S03=0111，S=110004（2）编号个体串交对象交叉位子代适应值11003110014410103101010001113011036110031101169P=0S=1100S=1010S=0110S=1101m 11121314什么是模糊性它与随机性有什么区别请举出日常生活中的例子。解：人们把因没有严格边界划分而无法精确刻画的现象称为模糊现象。随机性是偶然性的一种形式，只有某概率的事件集合中的各个事件所表现出来的不确定性。请说明模糊概念、模糊集及隶属函数三者之间的关系。解：模糊集是一种用来描述模糊现象和模糊概念的数学工具。一个模糊集与其隶属函数之间是一一对应关系，即一个模糊集只能有一个隶属函数来刻画，一个隶属函数也只能刻画一个模糊集。设某小组有5S,S,S,S,S1 2 3 4 5分：S:95S:85S:80S:70S:901 2 3 4 5这样就确定了一个模糊集程度，请写出该模糊集。解：对模糊集为F，可表示为：F={S,S,S,S,S}1 2 3 4 5设有论域U={u,u,u,u,u}1 2 3 4 5并设F、G是U上的两个模糊集，且有F=u+u+u+u1 2 3 4G=u+u+1/u3 4 5请分别计算F∩G，F∪G，﹁F。∧/u+∧/u1 2 3 4 5=0/u+0/u+u+u+0/u1 2 3 4 5=u+u3 4+∨/u1 2 3 4 5=u+u+u+u+1/u1 2 3 4 5F=/u+/u+/u+/u+(1-0)/u1 2 3 4 5=u+u+u+u+1/u1 2 3 4 5何谓模糊关系它如何表示关系是通过笛卡尔乘积定义的设有如下两个模糊关系：0.3 0.7 R1 0 10 0.5 1

0.2 0.8 R 2请写出R与R的合成R1 2 1 2因此有设FURF0.1 0.3 0.5 R 0.3 0求模糊变换FοR。解：={∨∨,∨∨,∨∨0}={,,}什么是等价类什么是等价划分解：等价类设BA对任意对象X∈U，关于B的等价类［X］B［X］B等价类的集合称为等价划分什么是上近似什么是下近似如何由上近似和下近似定义边界区域如何由边界区域定义粗糙集解：近似：变XU，BAXBB可定义为XBB可定义为XB—B—|[x]B BXBB—（x）可定义为XBB—|[x]B B设，对象集XBBNB(x)=B——设，由对象集XBBNBBNB)是对象集xB什么是决策表约简决策表约简主要有哪几个阶段解：决策约简表是指化简决策表中的条件属性和属性值，使决策表在保持原有决策能力的同时具有较少的条件属性和属性值决策表约简有以下几个阶段一致性检查属性约简什么是分明矩阵分明矩阵的作用是什么对信息系统u={u，，...u，为1 2 3 4 n、中元素个数则IS、中元素个数则ISAM是一个A阵元素定义为mij构造分明矩阵可得到约简核设决策表如表所示，求该决策表的分明矩阵。其中a，b，c，d为条件属性，e为决策属性。AabcdeU1021000121202100022211210解：acde aadebacdeceabcdeadeababde设化简后的决策表如图所示，请分别求该决策表的核值表和约简表。AAUace120011220022解：属性集A的分明矩阵aceaceaaceaeceae约简核的构造CORE（A）={a}与约简核交集为空的m

有{c，e}ij选择e属性加入到约简核得到一个约简{a，e}AAUace1x00x12x00x2第5章计算智能部分参考答案什么是不确定性推理为什么要采用不确定推理不确定性推理中需要解决的基本问题有哪些？不确定性的表示不确定性的匹配算不确定性的更新不确定性结论的合成不确定性推理可以分为哪几种类型？解：按数值的方法类型划分，可分为基于概率论的有关理论发展起来的方法和基于模糊逻辑理论发展起来的方法。按是否采用数值的方法划分可分为数值方法和非数值方法两大类型。何谓可信度？由规则强度CF(H,E)的定义说明它的含义。解：可信度是指人们根据以往经验对某个事物或现象为真的程度做出的一个判断。设有如下一组推理规则:r:IFETHENE1 1 2r:IFEANDETHENE2 2 3 4r:IFETHENH3 4r:IFETHENH4 5且已知CF(E)=,CF(E)=,CF(E)=。求CF(H)=?1 3 5r1

求CF(E2CF(E)=×max{0,CF(E)}2 1=×max{0,}=r2

求CF(E4CF(E)}}4 2 3=×max{0,min{,}}=r3

求CF(H)1CF1 4=×max{0,}=r4

求CF(H)2CF2 5=×max{0,}=CFCF)进行合成，求出CF(H)1 2CF(H)=CF(H)+CF(H)+CF(H)×CF(H)1 2 1 2=请说明主观Bayes方法中LS与LN的含义及它们之间的关系EH量。LNEHLNLS设有如下推理规则r:IFETHEN(2,H1 1 1r:IFETHEN(100,H2 2 1r:IFETHEN(200,H3 3 2r:IFHTHEN(50,H4 1 2且已知P(E)=P(E)=P(H)=,P(H)=,P(H)=,又由用户告知：1 2 3 1 2P(E|S)=,P(E|S)=,P(E|S)=1 1 2 2 3 3请用主观BayesP(H|S,S,S2 1 2 3r计算O(H|S1 1 1先把HEP(H|E1 1 1 1P(H|E)=(LS×P(H))/((LS-1)×P(H)+1)1 1 1 1 1 1=(2×/((2-1)×+1)=由于P(E|S)=>P(E)，使用S1 1 1 1概率P(H|SO(H|S1 1 1 1P(H|S)=P(H)+((P(H|E))/(1-P(E)))×(P(E|S))1 1

1 1 1

1 1 1=+–/(1–)×–=+×=O(H|S)=P(H|S)/(1-P(H|S))1 1 1 1 1 1=r计算O(H|S2 1 2先把HEP(H|E1 2 1 2P(H|E)=(LS×P(H))/((LS-1)×P(H)+1)1 2 2 1 2 1=(100×/((100-1)×+1)=由于P(E|S)=>P(E)，使用S2 2 2 2概率P(H|SO(H|S1 2 1 2P(H|S)=P(H)+((P(H|E))/(1-P(E)))×(P(E|S))1 2

1 2 1

2 2 2=+–/(1–)×–=O(H|S)=P(H|S)/(1-P(H|S))1 2 1 2 1 2=O(H|S,SP(H|S,S1 1 2 1 1 2先将H1

O(H)=P(H)/(1-P(H))==1 1 1再根据合成公式计算H1

的后验几率O(H|S,S)=(O(H|S)/O(H))×(O(H|S)/O(H))×O(H)1 1

1 1

1 2 1 1=×/×=再将该后验几率转换为后验概率P(H|S,S)=O(H|S,S)/(1+O(H|S,S))1 1 2

1 1

1 1 2=r计算O(H|S3 2 3先把HEP(H|E2 3 2 3P(H|E)=(LS×P(H))/((LS-1)×P(H)+1)2 3 3 2 3 2=(200×/((200-1)×+1)=由于P(E|S)=<P(E)，使用S3 3 3 3概率P(H|SO(H|S2 3 2 3P(H|S)=P(H|E)+(P(H)–P(H|E))/P(E))×P(E|S)2 3 2 3 2 2 3 3 3 3由当E3

肯定不存在时有P(H|E)=LN×P(H)/((LN-1)×P(H)+1)2 3 3 2 3 2=×(×+1)=因此有P(H|S)=P(H|E)+(P(H)–P(H|E))/P(E))×P(E|S)2 3 2 3 2 2 3 3 3 3r计算O(H|H4 2 1先把HHP(H|H2 1 2 1P(H|H)=(LS×P(H))/((LS-1)×P(H)+1)2 1 4 2 4 2=(50×/((50-1)×+1)=由于P(H|S,S)=>P(H)，使用S,S下H1 1 2 1 1 2 2的后验概率P(H|S,SO(H|S,S2 1 2 2 1 2P(H|S,S)=P(H)+((P(H|H))/(1-P(H)))×(P(H|S,S))2 1 2

2 1 2

1 1 2 1=+–/(1–)×–=O(H|S,S)=P(H|S,S)/(1-P(H|S,S))2 1

2 1

2 1 2==O(H|S,S,SP(H|S,S,S2 1 2 3 2 1 2 3先将H2

O(H)=P(H)/(1-P(H))==2 2 2再根据合成公式计算H1

的后验几率O(H|S,S,S)=(O(H|S,S)/O(H))×(O(H|S)/O(H))×O(H)2 1 2

2 1 2

2 3 2 2=×/×=再将该后验几率转换为后验概率P(H|S,S,S)=O(H|S,S,S)/(1+O(H|S,S,S))2 1 2 3

1 1 2

1 1 2 3=(1+=可见，H2

原来的概率是，经过上述推理后得到的后验概率是，它相当于先验概率的6倍多。设有如下推理规则rIFETHEN(100,H1: 1 1r:IFETHEN(50,H2 2 2r:IFETHEN(5,H3 3 3且已知P(H)=,P(H)=,P(H)=，请计算当证据EP(H|E1 2 3 1 2 3 i iP(HE(i=1,2,3)i iEEErrr1 2 3 1 2 3P(H|E)=(LS×P(H))/((LS-1)×P(H)+1)1 1 1 1 1 1=(100×/((100-1)×+1)=P(H|E)=(LS×P(H))/((LS-1)×P(H)+1)2 2 2 2 2 2=(50×/((50-1)×+1)=P(H|E)=(LS×P(H))/((LS-1)×P(H)+1)3 3 3 3 3 3=(5×/((5-1)×+1)=EEErrr1 2 3 1 2 3P(H|E)=(LN×P(H))/((LN-1)×P(H)+1)1 1 1 1 1 1=×/(×+1)=P(H|E)=(LN×P(H))/((LN-1)×P(H)+1)2 2 2 2 2 2=×/(×+1)=P(H|E)=(LN×P(H))/((LN-1)×P(H)+1)3 3 3 3 3 3=×/(×+1)=请说明证据理论中概率分配函数、信任函数、似然函数及类概率函数的含义解设函数m:[0,1满足m()=0 （A1则称m是上的概率分配A函数对任何命题A其信任函数 siA

m({si})+m（n）=1B

i1对任何命题A其似然函数为（

{si=1-[siA

i1

-{si]=msiA设为有限域对任何命题A，命题A的类概率函数为AA

[e]A分别是A中元素的个数设有如下推理规则rIFEANDETHENA={a}(CF={})1: 1 2r:IFEAND(EORE)THENB={b，b2 2 3 4 1 2r:IFATHENH={h3 1 2 3r:IFBTHENH={h4 1 2 3且已知初始证据的确定性分别为：CER(E)=，CRE(E)=，CER(E)=，CER(E)=1 2 3 4假设求。ANDE）=mn{CER(E)，CER(E)}=1 2 1 2m({a})={CER(EANDE)CF}={}1 2Bel(A)=A)=11f(A)=+=10ACER(A)=MD(E'

)f(A)=CER(EAND(EORE))2 3 4=min{CER(E)，max{CER(E)，CER(E)}}2 3 4=min{，}=bb}）=（，1 2Bel（B）=+=B）=1-0=12f(B)=+ =10ACER(B)=MD(E'

)f(B)==m({h})=，，（，，）1 1 2 3m({h}，{h}，{h})=，，（，，）2 1 2 3hhh1 2 3m（1Pl（H）=1310CER（H）≈何谓模糊匹配有哪些计算匹配度的方法模糊概念的匹配是指对22概念的相似程度有称为匹配度，有语义距离和贴近度这两种计算匹配度的方法设U=V={1，2，3，4}且有如下推理规则：IFxis少THENyis多UV=1+2+3=2+3+4已知事实为xis较少“较少”的模糊集为较少=1+2+3请用模糊关系Rm求出模糊结论。解：先用模糊关系Rm求出规则IFxis少THENyis多所包含的模糊关系RmRmRmRmRmRmRmRmRmRmRmRmRmRmRmRmRm即：因此有即，模糊结论为Y’={,,,}设有如下推理规则rIFxisFTHENyisG1:r:IFyisGTHENzisH2r:IFxisFTHENzisH3其中，F,G,H的模糊集分别为F=1/1+2+3+4G=2+3+4H=2+3+4请分别对各种模糊关系验证满足模糊假言三段论的情况按RgFG0000Rg1=00

0.1 0.2 0.40.1 0.2 0.40.1 0.2 0.40.1 0.2 1将GH10 0 Rg2=0 0.2

1 1 1 1 将FH000Rg3=

0.2 0.5 0.80.2 0.5 10 0.2 1 1000000Rg12=00

0.2 1 10.2 0.4 0.40.2 0.4 0.40.2 0.4 0.40.2 1 1将Rg12Rg3按Rm将FG1 1 1 1Rm1= Rm1= 0.8 0.8 0.8 0.8 0.6 0.6 0.6 0.6将GH1 1 1 1Rm2= Rm2= 0.8 0.8 0.8 0.8 0.6 0.6 0.6 0.600.20.50.200.20.50.20.20.50.50.50.50.60.60.6Rm3=

0.80.80.50.60.50.5Rm12=0.6

0.4 0.4 0.40.2 0.2 0.20.5 0.5 0.50.6 0.6 0.6将Rm12Rm3Rc什么是贝叶斯网络它是如何简化全联合概率分布的如何构建贝叶斯网络为什么说条件建立关系是贝叶斯网络能够简化全联合概率计算的基础构造贝叶斯网络在P168页如何使用贝叶斯网络的联合概率分布实现精准推理这种推理方法的局限性是什么解：P170精确推理方法仅适用于规模较小、结构较简单的贝叶斯网络推理。什么是马尔科夫覆盖如何确定一个节点的马尔科夫覆盖解：P168给定一个节点，该节点与其父节点、子节点和子节点的父节点一起构成了一个马尔科夫覆盖。设有如图所示的贝叶斯网络请计算报警铃响了，但实际上并无盗贼入侵，E也未发生地震，而张和李都打来电话的概率。BB盗贼入A-地震发生BEP(A)L报警声响AP(L)李来电话beZ张来电话AP(Z)b∧eb∧ebe（z|a）=××××=×104设有如图所示的贝叶斯网络，若目前观察到已洒水且草地湿了，请问下过雨的概率是多少？CP(S)

C多云S洒水W

P(C)CP(R)RCP(R)下雨当Rr

P（SPsWw，C）cP（C）P(s|C)P（r|C）P（w|s，r）c=[P(c)P(s|c)P(r|c)P(w|s,r)P（c）P(s|c)P(r|c)P(w|s,r)]=当Rr时==1/（+）=1/P(R|s,w)=,=,下雨的概率第6章符号学习参考答案什么是学习什么是机器学习解：学习是人类获取知识的重要途径和自然智能的重要标志，而机器学习则是机器获取知识的重要途径和机器智能的重要标志。什么是学习系统它包括哪几个基本部分解：机器学习系统（简称学习系统）是指能够在一定程度上实现机器学习的系统。如果一个系统能够从某个过程和环境的未知特征中学到有关信息，并且能把学到的信息用于未来的估计、分类、决策和控制，以便改进系统的性能，那么它就是学习系统。机器学习经历了哪几个阶段？按照学习的发展形势，将它分为热烈时期，冷静时期，复兴时期及蓬勃发44记忆学习的基本思想是什么？解：执行元素没解决一个问题，系统就记住这个问题和它的解，当以后再遇到此类问题时，系统就不必重新进行计算，而可以直接找出原来的解去使用。实例学习的归纳方法有哪几种？解：常用的归纳方法有把常量转换为变量，去掉条件，增加选择和曲线拟合等。什么是决策树决策学习是如何利用决策树进行学习的解：决策树是一种由节点和边构成的用来描述分类过程的层次数据结构。根节点表示分类的开始，叶节点表示一个实例的结束，中间节点表示相应实例中的某一属性，而边则代表某一属性可能的属性值。在决策树中，从根节点到叶节点的每一条路径都代表一个具体实例，并且同一路径上的所有属性之间是合取，不同的是析取。决策树的分类过程是从树的根节点开始，按属性值去测试相应的数值，依次下移，直至叶节点。设训练例子集如下表所示：121TT+2TT+3TF-4FF+5FT_6FT_序号属性xx序号属性xx分类解：设根节点为S，尽管它包含了所有的训练例子，但却没有包含任何分类信息，因此具有最大的信息熵。即：H(S)=-(P(+)logP(+)+P(-)logP(-))2 2式中P(+)=3/6，P(-)=3/6分别是决策方案为“+”或“-”时的概率。因此有H(S)=-((3/6)log(3/6)+(3/6)log(3/6))2 2=1按照ID3SSH(S|x)=(|S|/|S|)*H(S)+(|S|/|S|)*H(S)i T T F FFx和Sx=Tx=F、i T F i i|S|S分别为例子集S和ST F T F下面先计算S关于属性x1

的条件熵：在本题中，当x=T1ST当x=F1SF其中，ST

和SSF|S|=|S。T F由STP(+)=2/3STP(-)=1/3ST因此有：H(S)=-(P(+)log

(+)+P(-)log

(-))T ST

2ST

2ST=-((2/3)log(2/3)+(1/3)log(1/3))2 2=再由SF

可知，其决策方案为“+”或“-”的概率分别是：P(+)=1/3SFP(-)=2/3SF则有：H(S)=-(P(+)log

(+)+P(-)log

(-))F SF

2SF

2SF=-((1/3)log(1/3)+(2/3)log(2/3))2 2=将H(SH(ST FH(S|x)=(|S|/|S|)H(S)+(|S|/|S|)H(S)1 T T F F=(3/6)﹡+(3/6)﹡=下面再计算S关于属性x2

的条件熵：在本题中，当x=T2ST当x=F2SF其中，ST

和SSF T|