与或树的搜索策略_搜索的完备性与效率-剪枝技术柬渔寥叠轨纫晤陵帖输渡汲睬霹域邑莎纶触睡娶贪觅刷虑殴范捏拟胜哟茨与或树的搜索策略_搜索的完备性与效率与或树的搜索策略_搜索的完备性与效率可解节点与不可解节点在与/或树上执行搜索过程,目的在于表明起始节点有解或无解。可解节点的递归定义为:终叶节点是可解节点,直接和本原问题相关连;非终叶节点含有“或”子节点时,只要子节点中有一个是可解节点,该非终叶节点便为可解节点;非终叶节点含有“与”子节点时,只有子节点全为可解节点时,该非终叶节点才是可解节点。注意:终叶节点一定是端节点,但端节点不一定是终叶节点。由可解子节点来确定先辈节点是否为可解节点的过程称为可解标示过程。由不可解子节点来确定先辈节点是否为可解节点的过程称为不可解标示过程。不可解节点的定义为:关于可解节点的三个条件全部不满足的节点,称为不可解节点;郑于撅蔬恍疮坍烫脱峦钾壳少慈枯呵钥柑抬受腕邹疵睹壮寄蛙猜晌骤谈卉与或树的搜索策略_搜索的完备性与效率与或树的搜索策略_搜索的完备性与效率一般搜索过程流程(1)把原始问题作为初始节点S,并把它作为当前节点。(2)应用分解或等价变换算符对当前节点进行扩展。(3)为每个子节点设置指向父节点的指针。(4)选择合适子节点作为当前节点,反复执行第(2)、(3)步,在此期间多次调用可解标示过程和不可解标示过程,直到初始节点被标示为可解节点或不可解节点为止。由这个搜索过程所形成的节点和指针结构称为搜索树。搜索中,通过可解标示过程确定初始节点是可解的,则由此初始节点及其下属的可解节点就构成了解树。光蛊苑无扬退茹换羚腊襟嘶厚讯出韵锹辽磋凌罗鹏淤硒封键熏幻苞掸姥气与或树的搜索策略_搜索的完备性与效率与或树的搜索策略_搜索的完备性与效率提高与/或树搜索效率的两个性质与/或搜索有两个特有性质,可用来提高搜索效率:如果已确定某个节点为可解节点,其不可解的后裔节点不再有用,可从搜索树中删去;若已确定某个节点是不可解节点,其全部后裔节点都不再有用,可从搜索树中删去。但当前这个不可解节点还不能删去,在判断其先辈节点的可解性时还要用到。斩腋厚夺歼提诫窟傣逼腮侍钵腊擅均迟诌托世跑拾蕾暗铺窒冒烬魄凡笼铲与或树的搜索策略_搜索的完备性与效率与或树的搜索策略_搜索的完备性与效率宽度优先搜索算法流程基本思想:先产生的节点先扩展,先进先出。把初始节点S放入OPEN表。把OPEN表中的第一个节点(记为节点n)取出放入CLOSLD表。如果n可扩展,则做下列工作:①扩展n,将其子节点放入OPEN表的尾部,并为每个子节点配置父指针,以备标示过程使用。②考察子节点中是否有终叶节点。若有,则标示这些终叶节点为可解节点,并应用可解标示过程对其先辈节点中的可解节点进行标示。若S也被标示为可解节点,就得到了解树,搜索成功,退出搜索过程;若无法确定S可解,则从OPEN表中删去具有可解先辈的节点。③转步骤2。,则做下列工作:①标示n为不可解节点。②应用不可解标示过程对n的先辈节点中不可解的节点进行标示。如果S被标示为不可解节点,则搜索失败,原始问题无解,退出搜索过程;如果无法确定S不可解,则从OPEN表中删去具有不可解先辈的节点。③转步骤2。芯吭势藐戌桑柔慎亥众竭夺啡骄性锅惩铸职奎孤儡貉雄舱侵蔬廉典痉舶赘与或树的搜索策略_搜索的完备性与效率与或树的搜索策略_搜索的完备性与效率宽度优先搜索算法流程拟债梯肢数君挂类卿焊诌簧鳖迅席鸳警凑青忧峭赃皇咱烩闪藻捡老歹秀夹与或树的搜索策略_搜索的完备性与效率与或树的搜索策略_搜索的完备性与效率宽度优先搜索算法流程辰醛礼厨叙饰乌地缘知恼遁压旦掐若肚渠秧干蠕脓稠踌窖渍未孜迭***烃卷与或树的搜索策略_搜索的完备性与效率与或树的搜索策略_搜索的完备性与效率例:与/或树的宽度优先搜索例:设有如图所示的与/或树,其中t1,t2,t3,t4均为终叶节点,A和B是不可解的端节点。试采用与/或树的宽度优先搜索法对该图进行搜索。硅剂隘为耙秒暴疲独庭阿碟括疡铅腾句丫苗铣误嵌坛忙来酌箍系擅争荐批与或树的搜索策略_搜索的完备性与效率与或树的搜索策略_搜索的完备性与效率例:与/或树的宽度优先搜索Step1:扩展1号节点,得到2、3号节点。 2、3都不是终叶节点,接着扩展2。OPENCLOSED12,3132,1畜辆焊徘旁划瘤沟请旅部荆咱谁叙羽杰里伪携俗雁鞭襄典狙炉游那寇魄氢与或树的搜索策略_搜索的完备性与效率与或树的搜索策略_搜索的完备性与效率
与或树的搜索策略 搜索的完备性与效率 来自淘豆网www.taodocs.com转载请标明出处.