《华工人工智能老师上课课件第二章》由会员分享,可在线阅读,更多相关《华工人工智能老师上课课件第二章(21页珍藏版)》请在金锄头文库上搜索。
1、1,第二章 与或图搜索问题,2,2.1 基本概念,与或图是一个超图,节点间通过连接符连接。 K-连接符:,3,耗散值的计算,k(n, N) = Cn+k(n1, N)+k(ni, N) 其中:N为终节点集 Cn为连接符的耗散值,4,目标,目标,初始节点,解图:,5,能解节点,终节点是能解节点 若非终节点有“或”子节点时,当且仅当其子节点至少有一能解时,该非终节点才能解。 若非终节点有“与”子节点时,当且仅当其子节点均能解时,该非终节点才能解。,6,不能解节点,没有后裔的非终节点是不能解节点。 若非终节点有“或”子节点,当且仅当所有子节点均不能解时,该非终节点才不能解。 若非终节点有“与”子节点
2、时,当至少有一个子节点不能解时,该非终节点才不能解。,7,普通图搜索的情况,f(n) = g(n) + h(n) 对n的评价实际是对从s到n这条路径的评价,n,s,8,与或图: 对局部图的评价,目标,目标,初始节点,a,b,c,9,两个过程,图生成过程,即扩展节点 从最优的局部途中选择一个节点扩展 计算耗散值的过程 对当前的局部图从新计算耗散值,10,AO*算法举例,其中: h(n0)=3 h(n1)=2 h(n2)=4 h(n3)=4 h(n4)=1 h(n5)=1 h(n6)=2 h(n7)=0 h(n8)=0 设:K连接符 的耗散值为K,11,初始节点,n0,n1(2),n4(1),n5
3、(1),红色:4 黄色:3,12,目标,目标,初始节点,n0,n1,n2,n3,n4,n5,n6,n7,n8,红色:4 黄色:6,n1,n2(4),n3(4),5,13,目标,目标,初始节点,n0,n1,n2,n3,n4,n5,n6,n7,n8,红色:5 黄色:6,2,14,目标,目标,初始节点,n0,n1,n2,n3,n4,n5,n6,n7,n8,红色:5 黄色:6,2,1,15,2.3 博弈树搜索,博弈问题 双人 一人一步 双方信息完备 零和,16,分钱币问题,(7),(6,1),(5,2),(4,3),(5,1,1),(4,2,1),(3,2,2),(3,3,1),(4,1,1,1),(
4、3,2,1,1),(2,2,2,1),(3,1,1,1,1),(2,2,1,1,1),(2,1,1,1,1,1),对方先走,我方必胜,17,中国象棋,一盘棋平均走50步,总状态数约为10的161次方。 假设1毫微秒走一步,约需10的145次方年。 结论:不可能穷举。,18,1,极小极大过程,0,-3,3,-3,-3,-2,1,-3,6,-3,0,3,1,6,0,1,1,极大,极小,a,b,19,-剪枝,极大节点的下界为。 极小节点的上界为。 剪枝的条件: 后辈节点的值祖先节点的值时, 剪枝 后辈节点的 值祖先节点的值时, 剪枝 简记为: 极小极大,剪枝 极大极小,剪枝,20,8,6,-3,1,4,5,3,-3,5,0,-剪枝(续),3,-3,0,2,2,-3,0,-2,3,0,9,-3,0,0,-3,0,3,3,0,5,4,1,1,-3,1,6,6,1,a,b,c,d,e,f,g,h,i,j,k,m,n,21,-剪枝的其他应用,故障诊断 A B C D 风险投资,