秋季学期书面作业讲解ppt课件

1、人人 工工 智智 能能Artificial Artificial Intelligence (AI)Intelligence (AI)许建华许建华南京师范大学计算机学院南京师范大学计算机学院2021年秋季年秋季考试安排：考试安排：时间：时间：2021 年年 12 月月 31 日周二下午日周二下午1:30-3:30 地点：地点：J2-5012021年秋季学期书面作业讲解年秋季学期书面作业讲解形状空间法书面作业题：形状空间法书面作业题：15243678初始形状初始形状12345678目的形状目的形状利用宽度优先、深度优先深度限制为利用宽度优先、深度优先深度限制为4

2、、有序搜索算、有序搜索算法启发函数定义为数码不在位的个数找出上述八数法启发函数定义为数码不在位的个数找出上述八数码问题从初始形状到目的形状的操作符序列？码问题从初始形状到目的形状的操作符序列？152436781234152436781245367815243678152473685214367815264378124536781245367815432678152438671524736815247368521436781526437841253678123456781543267815243867152734681524768352143678542136781526374815264378

3、41253678412653781234567812345867宽度优先宽度优先1524367812341524367812453678152436781524736812453678124536781543267815243867152473681524736812345678154326781524386715273468152476831234567812345867深度优先深度优先1547268315247683521734681527346815243867152486371543267813542678右边后右边后产生产生152436781234152436781245367815

4、2436781524736812453678124536781543267815243867123456781234567812345867有序搜索有序搜索0+31+41+31+31+42+42+22+32+43+14+04+2存在的问题：存在的问题：(1)在宽度、深度搜索中，找到目的节点时，在宽度、深度搜索中，找到目的节点时，少画节点。我们如今规那么是对一个节点运用少画节点。我们如今规那么是对一个节点运用一切能够的操作符。一切能够的操作符。(2)有序搜索中，没有计算深度值，有序搜索中，没有计算深度值，h(n)计算有计算有误。误。(3)没有标出操作符没有标出操作符书面作业：假设当前的棋局为书面

5、作业：假设当前的棋局为OX请用极大极小过程为请用极大极小过程为MAX找出一个好棋？找出一个好棋？OXXOXOXXOXXXOXXOOXXOOXXOXOXOXOXOXO111221OOXXOXXOOXXOOXXOOXXO00001OOXX10OOXXOOXXOOXX1121OXOXXOXOXOOX00001XOXO1XOXOXOXOXOXO001存在的问题：存在的问题：中间层的值不是倒推计算出来的中间层的值不是倒推计算出来的某些棋局的值计算有误某些棋局的值计算有误消解原理部分的书面作业消解原理部分的书面作业1、求公式集、求公式集W=P(f(x),y), P(f(y),a)的最普通的合一者一致置换的

6、最普通的合一者一致置换第一步：第一步：k=0, 公式集公式集F0=W, 置换置换0=空空, 分歧分歧集集D0=x , y置换为置换为 y / x1=0y / x=y / x F1=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 / y 2=1a / y= a/x , a/y F2=F1 a/y=P(f(a),a) k=2P(f(y),y), P(f(y),a)第三步：第三步：F2中只需一个表达式，终了中只需一个表

7、达式，终了所求的最普通的一致置换或最普通的合一者为：所求的最普通的一致置换或最普通的合一者为： 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

8、)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

9、)=(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都是常量，不需求改名都是常量，不需求改名主要

10、错误：主要错误：没有按照步骤没有按照步骤常量改名常量改名3、设子句集为：、设子句集为：S= P(x)Q(x) , P(f(a) , Q(f(z) 恳求出它的一个反演恳求出它的一个反演 解法解法1 1：P(x)Q(x)P(x)Q(x)P(f(a)P(f(a)Q(f(z) Q(f(z) 可以消解可以消解的子集的子集 c1= c1=, c, c1=Q(x); c2=1=Q(x); c2=, c, c2= 2= 用合一算法求用合一算法求 P(x), P(f(a) P(x), P(f(a)的的mugmug，得得=f(a)/x=f(a)/x 归结式或消解式为归结式或消解式为c=(cc=(c1c1c2)=Q

11、(f(a) 2)=Q(f(a) P(x)Q(x)P(f(a)错误写法：错误写法：x/f(a)c1=c1=, c, c1=; c2=1=; c2=, c, c2=2= 用合一算法求用合一算法求Q(f(z),Q(f(a)Q(f(z),Q(f(a)的的mgumgu，得得= a/z= a/z 归结式或消解式为归结式或消解式为c= c= Q(f(z)Q(f(z) Q(f(a) Q(f(a)P(x)Q(x)P(f(a)Q(f(z) Q(f(a) mgu= f(a)/x mgu= a/z 解法解法2 2：c1=c1=, c1, c1= =P(x)P(x)；c2=c2=, c, c2= 2= 合一算法得合一算

12、法得mgu: =f(z)/xmgu: =f(z)/x 消解式为消解式为 P(f(z) P(f(z)c1=c1=, c, c1=,c2=1=,c2=, c, c2=2= 合一算法得合一算法得mgu: = a/zmgu: = a/z 归结式或消解式为归结式或消解式为c=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、设前提条件为、设前提条件为F1: (x)P(x)(y)Q(y)L(x,y)F2: (x)P(x)(y)R(y)L(x,y)试用消解原理证明以下结论成立：试用消解原理证

13、明以下结论成立：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) 错误：取非错误：取非结论取非的前束合

14、取范式与子句集：结论取非的前束合取范式与子句集：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

15、/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的教师。的教师。问题：小张的教师是谁？问题：小张的教师是谁？ domainspredicates teacher(symbol,symbol) classmate(symbol,symbol)clauses classmate(li, zhang). teacher(wang, li). tea