与或树搜索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与或树