构造状态空间树的两个方法 。回溯法 当前E-结点R,生成一个新的儿子C, 则C就变成一个新的E-结点，对子树C 完全检测后，R结点再次成为E结点 。分枝-限界方法 。一个E结点一直保持到变成死结点为止 o限界函数 以上两种方法都使用限界函数杀死还没 有全部生成其儿子结点的那些活结点
构造状态空间树的两个方法 回溯法 ⚫ 当前E-结点R，生成一个新的儿子C， 则C就变成一个新的E-结点，对子树C 完全检测后，R结点再次成为E-结点 分枝-限界方法 ⚫ 一个E-结点一直保持到变成死结点为止 限界函数 ⚫ 以上两种方法都使用限界函数杀死还没 有全部生成其儿子结点的那些活结点
分枝一限界法 。在生成当前E-结点全部儿子之后再生 成其它活结点的儿子 。并且，用限界函数帮助避免生成不包 含答案结点子树的状态空间 o FIFO检索：活结点表采用队 o LIFO检索：活结点表采用栈 oLC检索：最小成本检索
分枝－限界法 在生成当前E-结点全部儿子之后再生 成其它活结点的儿子 并且，用限界函数帮助避免生成不包 含答案结点子树的状态空间 FIFO检索：活结点表采用队 LIFO检索：活结点表采用栈 LC检索：最小成本检索
FIFO分枝一限界法 例9.1(4-皇后问题 ■■■■■■■■■■■■■■■■■■■■■■■ 8 34 4 ◆ 19 )0 40 45 B 8影 B 20 B B 11 2 8 6 B 38 B 52 B B 30 B B B 3」 39 B 答案结点
FIFO分枝－限界法 例9.1（4-皇后问题） 39
4-皇后问题 回溯vs FIFO分枝-限界 ■■■■■■■■■■■■■■■■■■■■■ 12 18 2 回溯 23 2 19 B B B Win 1G ···· B B B B
4-皇后问题— 回溯 vs FIFO分枝-限界 回溯 Win！
LC-检索(Least Cost) 。分枝-限界失败的原因 。对下一个E-结点的选择规则过于死板 。如何解决？ 。排序，让答案结点排在前面！ 寻找一种“有智力”的排序函数C(),该函数 能够让答案结点尽早生成 。排序的标准 下一个E-结点应当是生成答案结点花费成本 最小的结点，因此C)又称作结点成本函数。 LC:Least Cost
LC-检索（Least Cost） 分枝-限界失败的原因 ⚫ 对下一个E-结点的选择规则过于死板 如何解决？ ⚫ 排序，让答案结点排在前面！ ⚫ 寻找一种“有智力”的排序函数C(·)，该函数 能够让答案结点尽早生成 排序的标准 ⚫ 下一个E-结点应当是生成答案结点花费成本 最小的结点，因此C(·)又称作结点成本函数。 ⚫ LC：Least Cost