与或树搜索1与或树.ppt

1、6.1 与或树 6.2 与或树搜索 6.3 启发式与或树搜索,6 与或树搜索,6.1 与或树 三阶梵塔,（1,1,1） （3,3,3）,CBA,三元组 (i, j, k) i 代表金盘A所在的杆号；j代表金盘B所在的杆号；k代表金盘C所在的标号。,(ABC) （1,1,1）（1,2,2） （1,2,2）（3,2,2） （3,2,2）（3,3,3）,（1,1,1）,CBA,(1,2,2),（3,3,3）,（3,3,3）,（1,1,1）,（1,2,2）,（3,2,2）,举例(三阶梵塔),与或树表示,(1)把B、C盘从1号杆移到2号杆； (2)把A盘从1号杆移到3号杆； (3)把B、C盘从2号杆移到

2、3号杆；,举例(三阶梵塔),CBA,在三阶梵塔问题中，从左至右的顺序排列，得问题的解： (1,1,1)=(1,1,3) (1,1,3)=(1,2,3) (1,2,3)=(1,2,2) (1,2,2)=(3,2,2) (3,2,2)=(3,2,1) (3,2,1)=(3,3,1) (3,3,1)=(3,3,3),对于复杂的问题，直接求解往往比较困难。 从原问题出发，通过运用某些规则不断进行问题分解，重复进行，直到不能在分解或不需要分解为止。 从原问题出发，通过运用某些规则不断进行问题变换，把原问题变换为若干较容易求的新问题。,复杂问题简化,与或树用来描述一类问题的求解过程：把待解的原问题作为初始

3、节点，把由原问题经一系列分解或变换而得到的可解的简单问题作为目标节点。与或树。 节点：对应问题 子节点：对应子问题（由节点分解或变换）,问题的与或树表示,与或树的节点代表问题，其中既有与关系又有或关系，整个树表示问题空间。,与 分解 问题n为n1 . nk个子问题。 只有解决所有子问题，才能解决其父辈问题的子问题集合。 问题分解过程用图表示： 图中节点代表问题。与关系集合中，各个结点之间用一段小圆弧连接标记。,与节点,或 变换 问题n为n1 . nk个新问题。 只要解决某个问题就可解决其父辈问题的节点集合。,或节点,思考： 问题Q解决方案：？,概念与术语,本原问题：直接可解的简单问题（不能再分

4、解或变换）。 终止结点：本原问题对应的节点。(可解节点) 端节点: 在与或树中无子节点的节点。 与节点： 一个节点的子节点如果是“与”关系，称 或节点： 一个节点的子节点如果是“或”关系，称 思考: 终止节点是端节点吗? 注意： 终止节点一定是端节点，但端节点不一定是终止节点。,可解性判别,一个节点是可解，则节点须满足下列 条件之一： 1 终止节点是可解节点; 2一个与节点可解，当且仅当其子节点全都可解； 3一个或节点可解，只要其子节点至少有一个可解； 一个节点是不可解，则节点须满足下列条件之一： 1 非终止节点的端节点是不可解节点； 2 一个与节点不可解，只要其子节点至少有一个不可解； 3 一个或节点不可解，当且仅当其子节点全都不可解。,问题求解过程就是在一个与或树中寻找一个从初始节点（原始问题）到目标节点（可解的简单问题）的路径问题。,t3,1,3,2,B,5,t1,t4,t2,A,4,1,3,2,B,5,t1,t4,t3,t2,A,4,例1: t 是终止节点,1 可解性？,例2： Q作为初始节点，把子问题Q11，Q12，Q13作为目标节点，则对问题Q的求解就是在与或树中寻找从Q到Q11，Q12，Q1