A4B-人工智能基本原理-作业.doc

图搜索与问题求解第一次作业1.什么是状态空间图、状态（节点）、状态转换规则（边）、状态空间、隐式状态图2.状态图搜索问题求解需要哪些知识?求解过程的本质是什么？3.对以下3个问题，试分别设计该问题的状态、状态转换规则、状态空间，并描述求解过程（1）传教士与野人问题：传教士（M）与野人（C）数目均为五人，渡船（B）最多可乘3人。 （2）翻钱币问题：三枚钱币，能否从下面状态翻动三次后出现全正或全反状态反正反正正正反反反初始状态s目标状态集合0 , 7（3）已知桶、罐和瓶分别能存放水5000ml、3500ml、1500ml，现在桶中有5000ml水，如何只利用这三件容器把水分成两份，每份2500ml（4）N皇后问题就是在N*N的棋盘上放置N个皇后的方法解，满足每行、每列和对角线上只允许出现一个皇后，如以下是8皇后问题的解。试解决4皇后问题 第二次1.什么是启发性信息、完备的搜索、启发函数、加权状态图？2.深度优先搜索和广度优先搜索过程的OPEN表有何不同？3.深度优先搜索和广度优先搜索的优缺点是什么？4.估价函数综合了哪些信息？5.为“倒水”问题设计一个启发函数第三次1.什么是与等价？什么是或等价？试分别用一个例子说明。2.什么是与或图的本原问题？什么是端节点？什么是与节点、或节点？3.与或图搜索的可见性判别条件是什么？4.设有如下图的与/或/树，请分别按和代价法及最大代价法求解树的代价。ABCDt2t3t4t1与/或树56217223E 5. 设有如图所示的博弈树，其中最下面的数字是假设的估值，请对该博弈树作如下工作：(1) 计算各节点的倒推值；(2) 利用-剪枝技术剪去不必要的分枝。博弈树305-336-2354-3068-3369S0ABCDEFGHIJKLNM第四次1、请将下列语句翻译成命题公式（1）如果交通不堵塞，老王将准时到达火车站（2）你去听课，他也去听课（3）如果明天不下雪，我就去登山（4）尽管他参加了考试，但他没有通过考试2、请将下列语句翻译成谓词公式（1）有的人喜欢梅花，有的人喜欢菊花，有的人既喜欢梅花又喜欢菊花。 （2）他每天下午都去打篮球。 （3）西安市的夏天既干燥又炎热。 （4）并不是每一个人都喜欢吃臭豆腐。 （5）喜欢读三国演义的人必读水浒。 （6）欲穷千里目，更上一层楼。第5次1.将下列谓词公式整理为子句集形式（1）$x$y(P(x,y) Q(x,y)（2）x y(P(x,y) Q(x,y)（3）x$y(P(x,y) Q(x,y) R(x,y)（4）x (P(x) $y (P(y) R(x,y)（5）$x(P(x) x(P(y) R(x,y)（6）$x$yz $uv $w(p(x,y,z,u,v,w) (Q(x,y,z,u,v,w) R(x,z,w)第6次1.教材课后题2.寝室有甲、乙、丙三名同学，一天晚自习时，班主任老师巡查寝室发现该寝室有同学滞留寝室，没有参加晚自习；班主任调查得知：如甲在寝室并乙不在寝室时，则丙一定在寝室；如乙在寝室，则丙一定在寝室。班主任得出结论：丙一定在寝室。请试用基于命题公式的归结证明班主任的结论。3.判断以下公式对是否可合一，若可合一，则求出最一般的合一：（1）（2）（3）第7次作业1. 试判断下列子句集中哪些是不可满足的。（1）S=P(y) Q(y), P(f(x) Q(y)（2）S= P(x) Q(x), Q(y) R(y),P(a),R(a) （3）S= P(x) Q(y) L(x,y),P(a), R(z) L(a,z) ,R(b),Q(b)（4）S=P(x) Q(x) R(x), P(y) R(y), Q(a), R(b) （5）S=P(x) Q(x), Q(y) R(y), P(z) Q(z), R(u) 2对下列各题请分别证明，G是否可肯定是F1，F2，的逻辑结论（1）F：x(P(x) Q(x) G：$x(P(x) Q(x)（2）F1：x(P(x)y(Q(y) L(x,y) F2：$x(P(x)y(R(y) L(x,y) G：x(R(x) Q(x)（3）F1：(x)(P(x)(Q(x)R(x)F2：($x) (P(x) S(x)G： ($x)(S(x) R(x)4设已知：(1)凡是清洁的东西就有人喜欢；(2)人们都不喜欢苍蝇；用归结原理证明：苍蝇是不清洁的5张某被盗，公安局派出五个侦探去调查研究案情时，侦察员说赵与钱中至少有一人做案；侦察