文件名称：算法分析 第七讲 分枝-限界法
文件大小：1.4MB
文件格式：PPT
更新时间：2014-06-11 16:43:40
分枝-限界法
在图的检索方法中，BFS和D-检索这两种方法都是对当前E-结点(正在扩展的结点)检测完毕之后，再检测以队或栈结构形式存放在活结点(已经生成但其子结点尚未全部生成的结点)表中的其它结点。将这两种方法一般化后就成为分枝_限界策略。分枝_限界法是在生成当前E-结点的全部子结点后再生成其它活结点的子结点，与此同时用限界函数帮助避免生成不包含答案结点子树的状态空间(根结点到其它结点的所有路径一起构成了状态空间)的一种检索方法。在这个总的原则下，根据对状态空间树中结点检索次序的不同又可将分枝_限界设计策略分为几种不同的检索方法。其中，类似于BFS的状态空间检索称为 FIFO检索(First In First Out)，它的活结点表采用队列加以存储；类似于 D-检索的状态空间检索称为 LIFO检索(Last In Fist Out)，它的活结点表采用堆栈加以存储。