构造状态空间树的两个方法 o回溯法 ●当前E结点R,生成一个新的儿子C, 则c就变成一个新的E结点,对子树c 完全检测后,R结点再次成为E结点 分枝限界方法 个E结点一直保持到变成死结点为止 o限界函数 ●以上两种方法都使用限界函数杀死还没 有全部生成其儿子结点的那些活结点
构造状态空间树的两个方法 回溯法 ⚫ 当前E-结点R，生成一个新的儿子C， 则C就变成一个新的E-结点，对子树C 完全检测后，R结点再次成为E-结点 分枝-限界方法 ⚫ 一个E-结点一直保持到变成死结点为止 限界函数 ⚫ 以上两种方法都使用限界函数杀死还没 有全部生成其儿子结点的那些活结点
●·。分枝一限界法 o在生成当前E结点全部儿子之后再生 成其它活结点的儿子 o并且,用限界函数帮助避免生成不包 含答案结点子树的状态空间 oFFO检索:活结点表采用队 oLFO检索:活结点表采用栈 oLc检索:最小成本检索
分枝－限界法 在生成当前E-结点全部儿子之后再生 成其它活结点的儿子 并且，用限界函数帮助避免生成不包 含答案结点子树的状态空间 FIFO检索：活结点表采用队 LIFO检索：活结点表采用栈 LC检索：最小成本检索
FFO分枝一限界法 例91(4皇后问题) 0 B BB 565660): 20 B B 12324 2526 B 272 29 BB B B B B 39 B 答案结点
FIFO分枝－限界法 例9.1（4-皇后问题） 39
4-皇后问题 ●●● 回溯 VS FIFO分枝限界 2 回溯 O; ' u!M B B 3 B
4-皇后问题— 回溯 vs FIFO分枝-限界 回溯 Win！
●·。Lc检索( Least cost o分枝限界失败的原因 对下一个E结点的选择规则过于死板 o如何解决? 排序,让答案结点排在前面! 寻找一种“有智力”的排序函数c(),该函数 能够让答案结点尽早生成 o排序的标准 °下一个E结点应当是生成答案结点花费成本 最小的结点,因此c()又称作结点成本函数 LC: Least cost
LC-检索（Least Cost） 分枝-限界失败的原因 ⚫ 对下一个E-结点的选择规则过于死板 如何解决？ ⚫ 排序，让答案结点排在前面！ ⚫ 寻找一种“有智力”的排序函数C(·)，该函数 能够让答案结点尽早生成 排序的标准 ⚫ 下一个E-结点应当是生成答案结点花费成本 最小的结点，因此C(·)又称作结点成本函数。 ⚫ LC：Least Cost