秋季学期书面作业讲解.ppt
人人 工工 智智 能能ArtificialIntelligence(AI)许建华许建华南京师范大学计算机学院南京师范大学计算机学院2013年秋季年秋季考试安排考试安排：时间时间：2013年年12月月31日周二下午日周二下午1:30-3:30地点地点：J2-5012013年秋季学期书面作业讲解年秋季学期书面作业讲解状态空间法书面作业题：状态空间法书面作业题：15243678初始状态初始状态12345678目标状态目标状态利用宽度优先、深度优先（深度限制为利用宽度优先、深度优先（深度限制为4）、有序搜索算）、有序搜索算法（启发函数定义为数码不在位的个数）找出上述八数法（启发函数定义为数码不在位的个数）找出上述八数码问题从初始状态到目标状态的操作符序列？码问题从初始状态到目标状态的操作符序列？15243678123415243678124536781524367815247368521436781526437812453678124536781543267815243867152473681524736852143678152643784125367812345678154326781524386715273468152476835214367854213678152637481526437841253678412653781234567812345867宽度优先宽度优先1524367812341524367812453678152436781524736812453678124536781543267815243867152473681524736812345678154326781524386715273468152476831234567812345867深度优先深度优先1547268315247683521734681527346815243867152486371543267813542678右边后右边后产生产生1524367812341524367812453678152436781524736812453678124536781543267815243867123456781234567812345867有序搜索有序搜索0+31+41+31+31+42+42+22+32+43+14+04+2存在的问题：存在的问题：(1)在宽度、深度搜索中，找到目标节点时，在宽度、深度搜索中，找到目标节点时，少画节点。我们现在规则是对一个节点使用所少画节点。我们现在规则是对一个节点使用所有可能的操作符。有可能的操作符。(2)有序搜索中，没有计算深度值，有序搜索中，没有计算深度值，h(n)计算有计算有误。误。(3)没有标出操作符没有标出操作符书面作业书面作业：假设当前的棋局为：假设当前的棋局为OX请用极大极小过程为请用极大极小过程为MAX找出一个好棋？找出一个好棋？OXXOXOXXOXXXOXXOOXXOOXXOXOXOXOXOXO111221OOXXOXXOOXXOOXXOOXXO00001OOXX10OOXXOOXXOOXX1121OXOXXOXOXOOX00001XOXO1XOXOXOXOXOXO001存在的问题：存在的问题：中间层的值不是倒推计算出来的中间层的值不是倒推计算出来的某些棋局的值计算有误某些棋局的值计算有误消解原理部分的书面作业消解原理部分的书面作业1、求公式集、求公式集W=P(f(x),y),P(f(y),a)的最一般的合一者（一致置换）的最一般的合一者（一致置换）第第一一步步：k=0,公公式式集集F0=W,置置换换0=（空空）,分分歧歧集集D0=x,y置换为置换为y/x1=0y/x=y/xF1=F0y/x=P(f(y),y),P(f(y),a)k=k+1=1解解：P(f(x),y),P(f(y),a)第二步第二步：F1中含有两个表达式，继续中含有两个表达式，继续分歧集分歧集D1=a,y，置换为置换为a/y2=1a/y=a/x,a/yF2=F1a/y=P(f(a),a)k=2P(f(y),y),P(f(y),a)第三步第三步：F2中只有一个表达式，结束中只有一个表达式，结束所求的最一般的一致置换或最一般的合一者为：所求的最一般的一致置换或最一般的合一者为：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 1：P(x)Q(x)P(f(a)Q(f(z)可以消解可以消解的子集的子集 c1=,c1=Q(x);c2=,c2=用合一算法求用合一算法求P(x),P(f(a)的的mug，得得=f(a)/x归结式或消解式为归结式或消解式为c=(c1c2)=Q(f(a)P(x)Q(x)P(f(a)错误写法：错误写法：x/f(a)c1=,c1=;c2=,c2=用合一算法求用合一算法求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：c1=,c1=P(x)；c2=,c2=合一算法得合一算法得mgu:=f(z)/x消解式为消解式为P(f(z)c1=,c1=,c2=,c2=合一算法得合一算法得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/z4、设前提条件为、设前提条件为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)证明证明：F1的前束合取范式与子句集：的前束合取范式与子句集：(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)错误：取错误：取“非非”。F2的前束合取范式与子句集：的前束合取范式与子句集：(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:F1:：王王(Wang)Wang)先生是小李先生是小李(Li)Li)的老师的老师F2F2：小李与小张小李与小张(Zhang)Zhang)是同班同学是同班同学F3F3：如如果果x x与与y y是是同同班班同同学学，则则x x的的老老师师就就是是y y的的老师。老师。问题：小张的老师是谁？问题：小张的老师是谁？domainspredicatesteacher(symbol,symbol)classmate(symbol,symbol)clausesclassmate(li,zhang).teacher(wang,li).teacher(Z,Y):-classmate(X,Y),teacher(Z,X).goalteacher(U,zhang).解：解：判断一个整数是否偶数。判断一个整数是否偶数。predicatesis(integer,integer)clausesis(0,2):-!is(1,1):-!is(X,Z):-Z1=Z-2,is(X1,Z1),X=X1.goalis(Z,101).is(Z,100).超低级错误：超低级错误：symbol
