秋季学期书面作业讲解

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,考试安排,：,时间,：,2013,年,12,月,31,日周二下午,1:30-3:30,地点,：,J2-501,20,13,年秋季学期书面作业讲解,状态空间法书面作业题：,1,5,2,4,3,6,7,8,初始状态,1,2,3,4,5,6,7,8,目标状态,利用宽度优先、深度优先（深度限制为,4,）、有序搜索算法（启发函数定义为数码不在位的个数）找出上述八数码问题从初始状态到目标状态的操作符序列？,1,5,2,4,3,6,7,8,1,2,3,4,1,5,2,4,3,6,7,8,1,2,4,5,3,6,7,8,1,5,2,4,3,6,7,8,1,5,2,4,7,3,6,8,5,2,1,4,3,6,7,8,1,5,2,6,4,3,7,8,1,2,4,5,3,6,7,8,1,2,4,5,3,6,7,8,1,5,4,3,2,6,7,8,1,5,2,4,3,8,6,7,1,5,2,4,7,3,6,8,1,5,2,4,7,3,6,8,5,2,1,4,3,6,7,8,1,5,2,6,4,3,7,8,4,1,2,5,3,6,7,8,1,2,3,4,5,6,7,8,1,5,4,3,2,6,7,8,1,5,2,4,3,8,6,7,1,5,2,7,3,4,6,8,1,5,2,4,7,6,8,3,5,2,1,4,3,6,7,8,5,4,2,1,3,6,7,8,1,5,2,6,3,7,4,8,1,5,2,6,4,3,7,8,4,1,2,5,3,6,7,8,4,1,2,6,5,3,7,8,1,2,3,4,5,6,7,8,1,2,3,4,5,8,6,7,宽度优先,1,5,2,4,3,6,7,8,1,2,3,4,1,5,2,4,3,6,7,8,1,2,4,5,3,6,7,8,1,5,2,4,3,6,7,8,1,5,2,4,7,3,6,8,1,2,4,5,3,6,7,8,1,2,4,5,3,6,7,8,1,5,4,3,2,6,7,8,1,5,2,4,3,8,6,7,1,5,2,4,7,3,6,8,1,5,2,4,7,3,6,8,1,2,3,4,5,6,7,8,1,5,4,3,2,6,7,8,1,5,2,4,3,8,6,7,1,5,2,7,3,4,6,8,1,5,2,4,7,6,8,3,1,2,3,4,5,6,7,8,1,2,3,4,5,8,6,7,深度优先,1,5,4,7,2,6,8,3,1,5,2,4,7,6,8,3,5,2,1,7,3,4,6,8,1,5,2,7,3,4,6,8,1,5,2,4,3,8,6,7,1,5,2,4,8,6,3,7,1,5,4,3,2,6,7,8,1,3,5,4,2,6,7,8,右边后产生,1,5,2,4,3,6,7,8,1,2,3,4,1,5,2,4,3,6,7,8,1,2,4,5,3,6,7,8,1,5,2,4,3,6,7,8,1,5,2,4,7,3,6,8,1,2,4,5,3,6,7,8,1,2,4,5,3,6,7,8,1,5,4,3,2,6,7,8,1,5,2,4,3,8,6,7,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,1,2,3,4,5,8,6,7,有序搜索,0+3,1+4,1+3,1+3,1+4,2+4,2+2,2+3,2+4,3+1,4+0,4+2,存在的问题：,(1),在宽度、深度搜索中，找到目标节点时，少画节点。我们现在规则是对一个节点使用所有可能的操作符。,(2),有序搜索中，没有计算深度值，,h(n),计算有误。,(3),没有标出操作符,书面作业,：假设当前的棋局为,O,X,请用极大极小过程为,MAX,找出一个好棋？,O,X,X,O,X,O,X,X,O,X,X,X,O,X,X,O,O,X,X,O,O,X,X,O,X,O,X,O,X,O,X,O,X,O,1,1,1,2,2,1,O,O,X,X,O,X,X,O,O,X,X,O,O,X,X,O,O,X,X,O,0,0,0,0,1,O,O,X,X,1,0,O,O,X,X,O,O,X,X,O,O,X,X,1,1,2,1,O,X,O,X,X,O,X,O,X,O,O,X,0,0,0,0,1,X,O,X,O,1,X,O,X,O,X,O,X,O,X,O,X,O,0,0,1,存在的问题：,中间层的值不是倒推计算出来的,某些棋局的值计算有误,消解原理部分的书面作业,1、求公式集,W=P(,f,(x),y),P(,f,(y),a),的最一般的合一者（一致置换）,第一步,：,k,=0,公式集,F,0,=W,置换,0,=,（空）,分歧集,D,0,=x,y,置换为,y/x,1,=,0,y/x=y/x,F,1,=F,0,y/x=P(,f,(y),y),P(,f,(y),a),k=k+1=1,解,：,P(,f,(x),y),P(,f,(y),a),第二步,：,F,1,中含有两个表达式，继续,分歧集,D,1,=a,y，,置换为,a/y,2,=,1,a/y=a/x,a/y,F,2,=F,1,a/y=P(f(a),a),k=2,P(,f,(y),y),P(,f,(y),a),第三步,：,F,2,中只有一个表达式，结束,所求的最一般的一致置换或最一般的合一者为：,2,=a/x,a/y,主要问题：,合成运算有误，,错误答案,：,y/x,a/y,还是两个公式,2、求谓词公式,(,x),P(x),(y)P(y)P(f(x,y),(y)Q(x,y)P(y),的子句集,注：所有,粗箭头,仅表示配对的括号或者操作的符号,分析公式的,配对括号,和,量词的辖域,(,x),P(x),(y)P(y),P(f(x,y),(y)Q(x,y),P(y),（消去蕴涵）,=,(,x),P(x),(,y),P(y),P(f(x,y),(,y),Q(x,y),P(y),（非直接作用到谓词符号）,=(,x),P,(x),(y)P(y)P(f(x,y)(y)Q(x,y)P(y),=(x)P(x),(y)P(y)P(f(x,y),(y)Q(x,y)P(y),=(,x),P(x),(,y)P(y),P(f(x,y),(,y)Q(x,y),P(y),（改名）,=(,x)P(x),(y)P(y)P(f(x,y)(,z,)Q(x,z,)P(,z,),（消去存在量词）,=,P(,a,)P(,b,)P(f(,a,b,)Q(,a,c,)P(,c,),用常量,a,b,c,代替变量,x,y,z,（利用分配律）,P(QR)=(PQ)(PR),=,P(a),P(b),P(f(a,b),Q(a,c),P(b),P(f(a,b),P(c),=,P(a),P(b)Q(a,c)P(f(a,b)Q(a,c),P(b)P(c)P(f(a,b)P(c),再用一次分配律,=P(a)P(b)P(f(a,b)Q(a,c)P(c),（结合律）,P(a),P(b)Q(a,c),P(f(a,b)Q(a,c),P(b)P(c),P(f(a,b)P(c),子句集：,P(a),P(b)Q(a,c),P(f(a,b)Q(a,c),P(b)P(c),P(f(a,b),P(c),这里,a,b,c,都是常量，不需要改名,主要错误：,没有按照步骤,常量改名,3、设子句集为：,S=P(x)Q(x),P(f(a),Q(f(z),请求出它的一个反演,解法1,：,P(x)Q(x),P(f(a),Q(f(z),可以消解的子集,c,1,=,c,1,=Q(x);c,2,=,c,2,=,用合一算法求,P(x),P(f(a),的,mug，,得,=f(a)/x,归结式或消解式为,c=(c,1,c,2,)=Q(f(a),P(x)Q(x),P(f(a),错误写法：,x/f(a),c,1,=,c,1,=,;c,2,=,c,2,=,用合一算法求,Q(f(z),Q(f(a),的,mgu，,得,=a/z,归结式或消解式为,c=,Q(f(z),Q(f(a),P(x)Q(x),P(f(a),Q(f(z),Q(f(a),mgu=,f(a)/x,mgu=,a/z,解法,2,：,c,1,=,c,1,=,P(x),；,c,2,=,c,2,=,合一算法得,mgu:=f(z)/x,消解式为,P(f(z),c,1,=,c,1,=,c,2,=,c,2,=,合一算法得,mgu:=a/z,归结式或消解式为,c=,P(x)Q(x),Q(f(z),P(f(a),P(f(z),P(x)Q(x),P(f(a),Q(f(z),P(f(z),mgu=,f(z)/x,mgu=,a/z,4、设前提条件为,F,1,:(x)P(x)(y)Q(y)L(x,y),F,2,:(x)P(x)(y)R(y)L(x,y),试用消解原理证明下列结论成立：,G:(,x)R(x),Q(x),证明,：,F,1,的前束合取范式与子句集：,(,x)P(x)(y)Q(y)L(x,y),(x)P(x)(y)Q(y)L(x,y),(x)(y)P(x)Q(y)L(x,y),子句集：,P(x),Q(y),L(x,y),错误：取“非”。,F,2,的前束合取范式与子句集：,(,x)P(x)(y)R(y)L(x,y),(x)P(x)(y)R(y)L(x,y),P(a)(y)R(y)L(a,y),(y)P(a)R(y)L(a,y),子句集：,P(a),R(y),L(a,y),错误：取非,结论取非的前束合取范式与子句集：,G(x)R(x)Q(x),(x)R(x)Q(x),(x)R(x)Q(x),R(b)Q(b),子句集为：,R(b),Q(b),错误：与前面相同的常量符号,完整的子句集为：,P(x)Q(y)L(x,y),P(a),R(,z,)L(a,z,)（,改名,）,R(b),Q(b),反演过程：,(1),P(x)Q(y)L(x,y),(2)P(a),(3)R(z)L(a,z),(4)R(b),(5),Q(b),(6)Q(y)L(a,y)(1)(2)mgu=a/x,(7)L(a,b)(5)(6)mgu=b/y,(8)L(a,b)(3)(4)mgu=b/z,(9),(7)(8)mgu=,5、编写,Prolog,程序，并上机调试通过：,已知三个前提,F1:：,王(,Wang),先生是小李(,Li),的老师,F2：,小李与小张(,Zhang),是同班同学,F3：,如果,x,与,y,是同班同学，则,x,的老师就是,y,的老师。,问题：小张的老师是谁？,domains,predicates,teacher(symbol,symbol),classmate(symbol,symbol),clauses,classmate(li,zhang).,teacher(wang,li).,teacher(Z,Y):-classmate(X,Y),teacher(Z,X).,goal,teacher(U,zhang).,解：,判断一个整数是否偶数。,predicates,is(integer,integer),clauses,is(0,2):-!,is(1,1):-!,is(X,Z):-Z1=Z-2,is(X1,Z1),X=X1.,goal,is(Z,101).,is(Z,100).,超低级错误：,symbol,