文档介绍：与或树
与或树搜索
启发式与或树搜索
6 与或树搜索
与或树
三阶梵塔
(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)
3,2,2
(1,2,2)
(3,2,2)
举例(三阶梵塔)
(1,1,1)=>(3,3,3)
(1,1,1)=>(1,2,2)
(1,2,2)=>(3,2,2)
(3,2,2)=>(3,3,3)
(1,2,3)=>(1,2,2)
(3,2,2)=>(3,2,1)
(3,2,1)=>(3,3,1)
(3,3,1)=>(3,3,3)
(1,1,1)=>(1,1,3)
(1,1,3)=>(1,2,3)
与或树表示
(1)把B、C盘从1号杆移到2号杆;
(2)把A盘从1号杆移到3号杆;
(3)把B、C盘从2号杆移到3号杆;
举例(三阶梵塔)
(1,1,1)=>(3,3,3)
(1,1,1)=>(1,2,2)
(1,2,3)=>(1,2,2)
(1,1,1)=>(1,1,3)
(1,1,3)=>(1,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)
对于复杂的问题,直接求解往往比较困难。
从原问题出发,通过运用某些规则不断进行问题分解,重复进行,直到不能在分解或不需要分解为止。
从原问题出发,通过运用某些规则不断进行问题变换,把原问题变换为若干较容易求的新问题。
复杂问题简化
与或树用来描述一类问题的求解过程:把待解的原问题作为初始节点,把由原问题经一系列分解或变换而得到的可解的简单问题作为目标节点。——与或树。
节点:对应问题
子节点:对应子问题(由节点分解或变换)
问题的与或树表示
与或树的节点代表问题,其中既有与关系又有或关系,整个树表示问题空间。
与
分解问题n为n1 …. nk个子问题。
只有解决所有子问题,才能解决其父辈问题的子问题集合。
问题分解过程用图表示:
图中节点代表问题。与关系集合中,各个结点之间用一段小圆弧连接标记。
与节点
或
变换问题n为n1 …. nk个新问题。
只要解决某个问题就可解决其父辈问题的节点集合。
D
A
B
E
F
I
G
或节点