人工智能习题课(1)44

第1章习题P231-1什么是人工智能？试从学科和能力两方面加以说明。答：定义1.2和定义1.3。定义1.2(人工智能(学科))：人工智能(学科)是计算机科学中涉及研究、设计和应用智能机器的一个分支。其近期的主要目标在于研究用机器来模仿和执行人脑的某些智力功能，并开发相关理论和技术。定义1.3(人工智能(能力))：人工智能(能力)是智能机器所执行的通常与人类智能有关的智能行为，如判断、推理、证明、识别、感知、理解、通信、设计、思考、规划、学习和问题求解等思维活动。1-4现在人工智能有哪些学派？它们的认知观是什么？答：人工智能的学派及其认知观如下：(1)符号主义认为人工智能起源于数理逻辑。(2)连接主义认为人工智能起源于仿生学，特别是对人脑模型的研究。(3)行为主义认为人工智能起源于控制论。第2章习题P542-2设有3个传教士和3个野人来到河边，打算乘一只船从右岸渡到左岸去。该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡过河去？解：第一步：定义问题状态的描述形式：设Sk=(M,C,B)表示传教士和野人在河右岸的状态。其中：M表示传教士在右岸的人数。C表示野人在右岸的人数。B用来表示船是不是在右岸。(B=1表示在右岸，B=0表示在左岸)。初始状态集：S={(3,3,1)}目标状态集：G={(0,0,0)}第二步：定义算符。算符R(i,j)表示划船将i个传教士和j个野人送到左岸的操作。算符L(i,j)表示划船从左岸将i个传教士和j个野人带回右岸的操作。由于过河的船每次最多载两个人，所以i+j≤2。这样定义的算符集F中只可能有如下10个算符。F：R(1,0),R(2,0),R(1,1),R(0,1),R(0,2)L(1,0),L(2,0),L(1,1),L(0,1),L(0,2)第三步：求解过程。3,3,12,2,03,1,03,2,0R(0,1)R(1,1)L(1,1)L(0,1)R(0,2)L(0,2)3,1,11,1,00,2,03,2,1R(0,2)R(2,0)L(2,0)L(0,2)R(0,1)L(0,1)L(1,0)R(1,0)R(0,1)L(0,1)3,0,02,2,1R(1,1)L(1,1)R(2,0)L(2,0)0,1,00,2,11,1,10,3,1L(0,2)L(0,1)R(0,1)R(0,2)L(1,0)R(1,0)0,0,0L(0,1)R(0,1)R(0,2)L(0,2)L(1,1)R(1,1)L(0,1)R(0,1)0,1,1由上述状态空间图，可见从初始状态(3,3,1)到目标状态(0,0,0)的任何一条通路都是问题的一个解。其中：{R(1,1),L(1,0),R(0,2),L(0,1),R(2,0),L(1,1),R(2,0),L(0,1),R(0,2),L(1,0),R(1,1)}是算符最少的解之一。2-5试用四元数列结构表示四圆盘梵塔问题，并画出求解该问题的与或图。123ABCD1123ABCD用问题归约法来求解此问题：将原始问题归约为一个较简单的问题的集合：(1)移动圆盘A、B和C到柱子2的三圆盘难题。(2)移动圆盘D到柱子3的单圆盘难题。(3)移动圆盘A、B和C到柱子3的三圆盘难题。其子问题由一个包含两个四元数列的表列来描述，问题描述[(1111)=(2221)]就意味着“把ABC盘从柱子1移到柱子2”。则将上述四圆盘梵塔问题用四元数列结构表示为：(1111)=(3333)(1111)=(2221)(2221)=(2223)(2223)=(3333)(1111)=(3311)(3311)=(3321)(3321)=(2221)(2223)=(1123)(1123)=(1133)(1133)=(3333)(1111)=(2111)(2111)=(2311)(2311)=(3311)(3321)=(1321)(1221)=(2221)(1321)=(1221)(2223)=(3223)(3223)=(3123)(3123)=(1123)(1133)=(2133)(2333)=(3333)(2133)=(2333)2-6用谓词演算公式表示下列英文句子(多用而不是省用不同谓词和项。例如不要用单一的谓词字母来表示每个句子)。(x)(y)((C(x)∧P(human,y)∧P(x,y)∧Q(y))→I(x))Acomputersystemisintelligentifitcanperformataskwhich,ifperformedbyahuman,requiresintelligence.解：谓词定义：P(x,y):xperformsytask.(x完成y任务)Q(y):yrequiresintelligence.(y需要智能)C(x):xisacomputersystem.(x是一计算机系统)I(x):xisintelligent.(x是智能的)2-7、把下列语句表示成语义网络描述：(1)Allmanaremortal.ManMan-1mortalISAISGGSISA2-7、把下列语句表示成语义网络描述：(2)Everycloudhasasilverlining.CloudCloud-1Lining-1ISAHasGGSISASilverLining-1ColorISA2-7、把下列语句表示成语义网络描述：(3)AllbranchmanagersofDECparticipateinaprofit-sharingplan.ManagerBranchmanagerProfitsharingplan-1ISAParticipateGGSISADECplanbelongsISA2-9、试构造一个描述你的寝室或办公室的框架系统。答：以办公室框架为例：办公室：名称：教务办电话：[phone]工作人员：工作人员-1、工作人员-2设备：电脑2台、复印机2台工作人员-1姓名：张三出生年月：1965年9月岗位：办公室主任职称：副教授工作人员-2姓名：李四出生年月：1980年9月岗位：普通办公员职称：助教第3章习题3-7、用有界深度优先搜索方法求解图3.34所示八数码难题。28163754S0Sg定义操作符集：F={f1,f2,f3,f4}，其中：f1表示空格右移；f2表示空格上移；f3表示空格左移；f4表示空格下移。搜索时，节点的扩展顺序规定为按右、左、上、下方向移动空格。并设置深度界限为8。28163754S0Sg28163754S02816375428316754f4f32831675428316475f3f428316475f32831476528316475f3f22831476523184765f3f22318476523184765f3f112384765f4Sg1238476512378465f4f3由上述有界深度优先搜索树中可见，当d=8时，八数码难题的一个解为：f4,f4,f3,f2,f2,f3,f4,f33-17、把下列句子变换成子句形式：(1)(x){P(x)→P(x)}解：(x){P(x)→P(x)}消去蕴含符号得：(x){～P(x)∨P(x)}消去存在量词得：～P(x)∨P(x)于是得到子句：～P(x)∨P(x)3-17、把下列句子变换成子句形式：(4)～{(x){P(x)→{(y)[p(y)→p(f(x,y))]∧(y)[Q(x,y)→P(y)]}}}1)～{(x){～P(x)∨{(y)[～p(y)∨p(f(x,y))]∧(y)[～Q(x,y)∨P(y)]}}}2)(x){P(x)∧{(y)[p(y)∧～p(f(x,y))]∨(y)[Q(x,y)∧～P(y)]}}3)(x){P(x)∧{(y)[p(y)∧～p(f(x,y))]∨(z)[Q(x,z)∧～P(z)]}}3)(x){P(x)∧{(y)[p(y)∧～p(f(x,y))]∨(z)[Q(x,z)∧～P(z)]}}4)令Skolem函数：x=A，y=B，z=C，则P(A)∧{[p(B)∧～p(f(A,B))]∨[Q(A,C)∧～P(C)]}}5)P(A)∧[p(B)∨Q(A,C)]∧[p(B)∨～P(C)]∧[～p(f(A,B))∨Q(A,C)]∧[～p(f(A,B))∨～P(C)]}}6)子句集：{P(A)，p(B)∨Q(A,C)，p(B)∨～P(C)，～p(f(A,B))∨Q(A,C)，～p(f(A,B))∨～P(C)}补充题：例1：张某被盗，公安局派出五个侦察员去调查。研究案情时，侦察员A说“赵与钱中至少有一人作案”；侦察员B说“钱与孙中至少有一人作案”；侦察员C说“孙与李中至少有一人作案”；侦察员D说“赵与孙中至少有一人与此案无关”；侦察员E说“钱与李中至少有一人与此案无关”。如果这五个侦察员的话都是可信的，试问谁是盗窃犯。解：定义谓词：P(x):x作案。由于五个侦察员的话为真，则将五个侦察员的话表示成谓词公式，有：A:P(zhao)∨P(qian)B:P(qian)∨P(sun)C:P(sun)∨P(li)D:～P(zhao)∨～P(sun)E:～P(qian)∨～P(li)易见以上每个侦察员的话都是一个子句。解：待求解问题的表示P(y)将其否定并与ANSWER(y)构成析取式：～P(y)∨ANSWER(y)易见以上表达式是一个子句。现将子句列表如下：(1)P(zhao)∨P(qian)(2)P(qian)∨P(sun)(3)P(sun)∨P(li)(4)～P(zhao)∨～P(sun)(5)～P(qian)∨～P(li)(6)～P(y)∨ANSWER(y)应用归结原理进行推理：(7)P(qian)∨～P(sun)(1)(4)归结(8)P(zhao)∨～P(li)(1)(5)归结(9)P(qian)∨～P(zhao)(2)(4)归结(10)P(sun)∨～P(li)(2)(5)归结(11)P(li)∨～P(zhao)(3)(4)归结(12)P(sun)∨～P(qian)(3)(5)归结(13)P(qian)(2)(7)归结(14)P(sun)(3)(10)归结(15)～P(zhao)(9)(13)归结(16)～P(li)(10)(14)归结(17)ANSWER(qian)(6)(13)归结，={qian/y}(18)ANSWER(sun)(6)(14)归结，={sun/y}所以，钱和孙是盗窃犯。例2：(分油问题)有A、B、C三个不带刻度的瓶子，分别能装8kg,5kg和3kg油。如果A瓶装满油，B和C是空瓶，怎样操作三个瓶，使A中的油平分两份？(假设分油过程中不耗油)解：第一步：定义问题状态的描述形式：设Sk=(b,c)表示B瓶和C瓶中的油量的状态。其中：b表示B瓶中的油量。c表示C瓶中的油量。初始状态集：S={(0,0)}目标状态集：G={(4,0)}第二步：定义操作符：操作：把瓶子倒满油，或把瓶子的油倒空。f1：从A瓶往B瓶倒油，把B瓶倒满。f2：从C瓶往B瓶倒油，把B瓶倒满。f3：从A瓶往C瓶倒油，把C瓶倒满。f4：从B瓶往C瓶倒油，把C瓶倒满。f5：从B瓶往A瓶倒油，把B瓶倒空。f6：从B瓶往C瓶倒油，把B瓶倒空。f7：从C瓶往A瓶倒油，把C瓶倒空。f8：从C瓶往B瓶倒油，把C瓶倒空。第三步：求解过程：0,00,35,31,31,00,15,13,33,04,04,35,25,30,00,20,32,02,35,0f1f3f4f7f8f6f5f3f1f1f1f4f7f5f3f2f8f3f8f3f2f5f8f3f8f7f7f6f1f4f7f4f5f1f7f1f1f1f7f5f5f7f5f6f7f5f1f3f3由上述状态空间图，可见从初始状态(0,1)到目标状态(4,0)的任何一条通路都是问题的一个解。其中：{f1,f4,f7,f6,f1,f4,f7}是算符最少的解之一。例3：设有下列语句，请用相应的谓词公式把它们表示出来。(1)