人工智能交大题目及答案.docx
- 文档编号:16381458
- 上传时间:2023-07-13
- 格式:DOCX
- 页数:10
- 大小:148.36KB
人工智能交大题目及答案.docx
《人工智能交大题目及答案.docx》由会员分享,可在线阅读,更多相关《人工智能交大题目及答案.docx(10页珍藏版)》请在冰点文库上搜索。
人工智能交大题目及答案
7、某问题的状态空间图如下图所示,其中括号内标明的是各节点的h值,弧线边的数字是该弧线的耗散值,试用A算法求解从初始节点S到目标节点T的路径。
要求给出搜索图,标明各节点的f值,及各节点的扩展次序,并给出求得的解路径。
三、问答题答案
第1题
答:
得解图:
第3题
答:
综合数据库:
(m1,m5,m9,b)设从河的左岸到右岸,其中m1,m5,m9分别表示过河时间需要1分钟,5分钟和9分钟的人,在河左岸的人数。
b=1表示船在左岸,b=0表示船在右岸。
规则集:
初始状态:
(2,1,1,1)
结束状态
(0,0,0,0)
h函数:
h(n)=m-b,其中m为在左岸的人数,b为船是否在左岸。
对于任意两个节点ni和nj,其中nj是ni的子节点。
当ni中b=1时,则nj中b=0,因此:
max(h(ni)-h(j))=(m-1)-(m-1)=0,而C(ni,nj)最小为1,因此h(ni)-h(nj) 当ni中b=0时,则nj中b=1,因此: max(h(ni)-h(j))=m-m=0,而C(ni,nj)最小为1,因此h(ni)-h(nj) 而对于目标节点t,h(t)=0。 因此该h函数满足单调性条件。 所以h满足A*条件。 第4题 答: 对事实和规则进行skolem化: (1)( s) ~P(a) (2)( s)(P(g(s))) P(g(s)) (3)( x)( s)( y)((P(s)∧Q(b,x,s))→H(y) (P(s)∧Q(b,c,s))→H(f(s)) (4)( x)( s)(Q(b,x,s)→Q(b,x,g(s))) Q(b,x,s)→Q(b,x,g(s)) (5)( x)( s)( y)(~P(s)→Q(b,x,y)) ~P(s)→Q(b,x,h(x,s)) 经变量换名后,有事实和规则如下: ~P(a) P(g(s1)) r1: (P(s2)∧Q(b,c,s2))→H(f(s2)) r2: Q(b,x3,s3)→Q(b,x3,g(s3)) r3: ~P(s4)→Q(b,x4,h(x4,s4)) 用对偶形式对目标skolem化: ( x)H(x) H(x) 演绎图如下图(这里只给出了一个一致解图)。 由置换集构造U1和U2: U1=(x,s2,x3,s2,x4,s3,s4) U2=(f(s2),g(s1),c,g(s3),c,h(x4,s4),a) 由于U1和U2是可合一的,因此该解图是一致解图。 合一复合为: {f(g(h(c,a)))/x,g(h(c,a))/s2,c/x3,h(c,a)/s3,c/x4,h(c,a)/s1,a/s4}}将该合一复合带入目标中,得到解答: x=f(g(h(c,a))) 第5题 答: 1、由于修正的A*算法对与OPEN表中f值小于fm的节点按照g值的大小排序,优先扩展g值小的节点。 对于这部分节点来说,相当于h=0。 而h=0满足单调条件,因此至少对于这部分节点来说,减少了重复扩展节点的可能性。 因此修正的A*算法有可能减少重复节点的扩展。 2、由于A*扩展的节点,其f值总是小于等于f*(s),而fm是到目标为止扩展过的节点的最大f值,因此必有fm小于等于f*(s)。 又由于OPEN表中f值小于f*(s)的节点,总是被A*扩展的,因此从OPEN表中选择那些f值小于fm的节点(这些节点的f值也必然小于f*(s)),按照g值的大小优先扩展,只是改变了部分节点的扩展次序,不会多扩展节点 第6题 答: 如下的知识可以帮助求解该问题: (1)序列中,偶数在偶数位置,奇数在奇数位置; (2)第五个数为5。 综合数据库: 用一个1到9的序列表示: N={x},其中x为1到9的数字之一。 规则集: r1: IFlen(N)=4THEN{x}∪{5} r2: IFlen(N)为偶数andn=In(1,3,7,9)THEN{x}∪{n} r3: IFlen(N)为奇数andn=In(2,4,6,8)THEN{x}∪{n} 其中len(N)为求序列的长度,In(a,b,c,d)为取a、b、c、d之一。 初始状态: {} 结束条件: 得到的序列N前i个数组成的整数能被i整除。 第7题 答: 搜索图如图所示,其中括号内标出的是节点的f值,圆圈内的数字是扩展的次序。 F(16) 得到的解路径为: S-B-F-J-T
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 交大 题目 答案