第二章与或图搜索问题要点解析.pdf

第二章 与或图搜索 2.1 基本概念 与或图是一个超图，节点间通过连接符连接。 k-连接符：k1为“与”节点，k=1为“或”节点 …... k个 与或图 n0 n1 n2 n4 n0有2个外向连接符， n3 n5 分别为1-连接符（n1), 2-连接符（n4,n5);n8 是n4的或子节点，同时 又是n5的与子节点 n6 n8 n7 2 与或图搜索问题 初始节点n0 n1 n2 n4 搜索的目的:考察n0到目标 n3 n5 （终节点）集合N={n7,n8} 是否有解并找到解图 n6 目标n8 目标n7 能解节点 终止（目标）节点可解 若非终节点有“或”子节点时，当且仅当其 子节点至少有一能解时，该非终节点才能解。 若非终节点有“与”子节点时，当且仅当其 子节点均能解时，该非终节点才能解。 端节点：无子节点的节点 不能解节点 没有后裔的非终节点（端节点）是不能解节点。 若非终节点有“或”子节点，当且仅当所有子 节点均不能解时，该非终节点才不能解。 若非终节点有“与”子节点时，当至少有一个 子节点不能解时，该非终节点才不能解。 节点耗散值的递推计算 k(n, N) = C +k(n , N)+…+k(n , N) n 1 i 其中：N为终节点集, C 为连接符的耗散值 n n …... n1 n2 ni i个 解图（对于无环与或图而言） 递归定义： 一个与或图G中，从节点n到节点集N的解图记为G’ ，G’是G的子图 1. 如果n是N的一个元素，则G’由单一节点n 组成； 2. 如果n有一个外向连接符k指向节点{n , n ,…, 1 2 n }使得从每一个n 到N有一个解图，则G’由n、连 k