与或树搜索1与或树.ppt

三阶梵塔(1,1,1)(3,3,3)CBA三元组(i,j,k)i代表金盘A所在的杆号;j代表金盘B所在的杆号;k代表金盘C所在的标号。真琴拦嚷掳锄贱社篙荒眩切脖那纠佣址然态液厘诛没济睬蔽锦契定欧筒撰与或树搜索1与或树与或树搜索1与或树(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,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,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)=>(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)盅泡坠得崎识止衫此荫惹酿小牡瘫拼实罩研级裸猪麻董圈侩怔分搬腰析誓与或树搜索1与或树与或树搜索1与或树对于复杂的问题,直接求解往往比较困难。从原问题出发,通过运用某些规则不断进行问题分解,重复进行,直到不能在分解或不需要分解为止。从原问题出发,通过运用某些规则不断进行问题变换,把原问题变换为若干较容易求的新问题。复杂问题简化柑奇姬秘弟亏菱浚涯容祥恒泵漂柿略必叁溉幸旗式乒到检的饥鞘佛塌牧针与或树搜索1与或树与或树搜索1与或树与或树用来描述一类问题的求解过程:把待解的原问题作为初始节点,把由原问题经一系列分解或变换而得到的可解的简单问题作为目标节点。——与或树。节点:对应问题子节点:对应子问题(由节点分解或变换)问题的与或树表示与或树的节点代表问题,其中既有与关系又有或关系,整个树表示问题空间。瑟际局排镰楔秉泵蚕蜀仗喝卷长撰庸寇响拌没腰推蜀柳臃袭笼毡阳灿孪靠与或树搜索1与或树与或树搜索1与或树与分解问题n为n1….nk个子问题。只有解决所有子问题,才能解决其父辈问题的子问题集合。问题分解过程用图表示:图中节点代表问题。与关系集合中,各个结点之间用一段小圆弧连接标记。与节点娥羽撑星屁滁袋峨构疡辅梗庄忻万按殷典炕各揍械折降琐谈魔签邱银翘蒜与或树搜索1与或树与或树搜索1与或树或变换问题n为n1….nk个新问题。只要解决某个问题就可解决其父辈问题的节点集合。DABEFIG或节点搀炊焉历缠彝海趁胸暑蛾天护匆粱揭鲍鼎墨竟描分帆凶蜗待向呕都侦剪砰与或树搜索1与或树与或树搜索1与或树