人工智能：第三章 与或图的搜索策略.pdf

: .
第三章 与/，当其子节点中至少有一个为可解节点时，则该或节点
就是可解节点。
③对“与”节点，只有当其子节点全部为可解节点时，该与节点才是可
解节点。
同样，可用类似的方法定义不可解节点：
①不为终止节点的端节点是不可解节点。
②对“或”节点，若其全部子节点都为不可解节点，则该或节点是不可解
节点。
③对“与”节点，只要其子节点中有一个为不可解节点，则该与节点是不
可解节点。解图
由可解节点构成，并且由这些可解节点可以推出初始节点（它对应
着原始问题）为可解节点的子树为解图。在解图中一定包含初始节点。
例如，图给出的与或树中，用红线表示的子树是一个解树。在该图
中，节点P为原始问题节点，用t标出的节点是终止节点。根据可解节
点的定义，很容易推出原始问题P为可解节点。
问题归约求解过程就实际上就是生成解树，即证明原始节点是可解
节点的过程。这一过程涉及到搜索的问题，对于与/或树的搜索将在后
面详细讨论。 P 1可解节点
2 3
B端节点（不可扩展节点）
4 t1 5
t2 t3
终止节点
A t4 : .
第三章 与/或图的搜索策略
与或图表示法
与或图的一般搜索

与或图的有序搜索

－剪支技术 : .
第三章 与/或图的搜索策略
与或图表示法
与或图的一般搜索

与或图的有序搜索

－剪支技术 : .
与/或图的表示法
 问题归约
 与或图表示问题特点
 与或图的表示法
 举例 : .
第三章 与/或图的搜索策略
与或图表示法
与或图的一般搜索

与或图的有序搜索