与或树搜索1与或树.ppt

6.1与或树
6.2与或树搜索
6.3启发式与或树搜索6.1与或树
三阶梵塔(ABC)
（1,1,1）（1,2,2）
（1,2,2）（3,2,2）
（3,2,2）（3,3,3）举例(三阶梵塔)举例(三阶梵塔)在三阶梵塔问题中，从左至右的顺序排列，得问题的解：

(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)

对于复杂的问题，直接求解往往比较困难。

从原问题出发，通过运用某些规则不断进行问题分解，重复进行，直到不能在分解或不需要分解为止。

从原问题出发，通过运用某些规则不断进行问题变换，把原问题变换为若干较容易求的新问题。
与或树用来描述一类问题的求解过程：把待解的原问题作为初始节点，把由原问题经一系列分解或变换而得到的可解的简单问题作为目标节点。——与或树。
节点：对应问题
子节点：对应子问题（由节点分解或变换）与
分解问题n为n1….nk个子问题。

只有解决所有子问题，才能解决其父辈问题的子问题集合。

问题分解过程用图表示：

图中节点代表问题。与关系集合中，各个结点之间用一段小圆弧连接标记。或
变换问题n为n1….nk个新问题。

只要解决某个问题就可解决其父辈问题的节点集合。
Q13可解性判别t3例2：
Q作为初始节点，把子问题Q11，Q12，Q13······作为目标节点，则对问题Q的求解就是在与或树中寻找从Q到Q11，Q12，Q13······的路径问题。与或树中解的路径称为解树。

解树是由可解节点形成的一个子树，这个子树的根为初始节点，叶为终止节点。

解树是与树。