资源描述：
《人工智能 第二章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章与或图搜索问题目标目标初始节点sabc12.1基本概念与或图是一个超图，节点间通过连接符连接。K-连接符：…...K个2耗散值的计算k(n,N)=Cn+k(n1,N)+…+k(ni,N)其中：N为终节点集Cn为连接符的耗散值…...i个nn1n2ni3目标目标初始节点解图：4能解节点终节点是能解节点若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点才能解。若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。5不能解节点没有后裔的非终节点是不能解节点。若非终节点有
2、“或”子节点，当且仅当所有子节点均不能解时，该非终节点才不能解。若非终节点有“与”子节点时，当至少有一个子节点不能解时，该非终节点才不能解。6普通图搜索的情况f(n)=g(n)+h(n)对n的评价实际是对从s到n这条路径的评价ns7与或图:对局部图的评价目标目标初始节点abc8两个过程图生成过程，即扩展节点从最优的局部途中选择一个节点扩展计算耗散值的过程对当前的局部图从新计算耗散值9AO*算法举例其中：h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2h(n7
3、)=0h(n8)=0设：K连接符的耗散值为K目标目标初始节点n0n1n2n3n4n5n6n7n810目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点n0n1(2)n4(1)n5(1)红色：4黄色：311目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点n0n4(1)n5(1)红色：4黄色：6n1n2(4)n3(4)512目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5黄色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)213目标目
4、标初始节点n0n1n2n3n4n5n6n7n8红色：5黄色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)21142.3博弈树搜索博弈问题双人一人一步双方信息完备零和15分钱币问题（7）（6,1）（5,2）（4,3）（5,1,1）（4,2,1）（3,2,2）（3,3,1）（4,1,1,1）（3,2,1,1）（2,2,2,1）（3,1,1,1,1）（2,2,1,1,1）（2,1,1,1,1,1）对方先走我方必胜16中国象棋一盘棋平均走50步，总状态数约为10的161
5、次方。假设1毫微秒走一步，约需10的145次方年。结论：不可能穷举。171，极小极大过程05-333-3022-30-23541-30689-30-33-3-3-21-36-30316011极大极小ab18-剪枝极大节点的下界为。极小节点的上界为。剪枝的条件：后辈节点的值≤祖先节点的值时，剪枝后辈节点的值≥祖先节点的值时，剪枝简记为：极小≤极大，剪枝极大≥极小，剪枝1986-31453-350-剪枝（续）3-3022-30-2309-300-303305411-31661abcdef
6、ghijkmn20-剪枝的其他应用故障诊断ABCD风险投资21
