●●。计算机算法基础 分枝一限界法
计算机算法基础 分枝－限界法
●·0预备知识 o问题状态 o状态空间树 o解状态 o活结点 o状态空间 oE结点 o答案状态 o死结点 o等等 o本节主要目的 通过对n-皇后问题的分析,学习以上概念, 并且了解回溯法
0 预备知识 问题状态 解状态 状态空间 答案状态 状态空间树 活结点 E-结点 死结点 等等…… 本节主要目的 通过对n-皇后问题的分析，学习以上概念， 并且了解回溯法
●·。解空间树结构的术语 o树中每个结点确定求解问题的一个问题状态 (problem state) o由根结点到其它结点的所有路径确定了这个 间题的状态空间( state space) 解状态( solution states) 是这样一些问题状 态S,对于这些问题状态,由根到S的那条路 續定了这解空间中的一个元组(满足显式 o答案状态(so! ution states )是这样,些解状 态S,由根到S的路径确定了问题的一个解 (满足隐式约束) o解空间的树结构为状态空间树( state space tree)
解空间树结构的术语 树中每个结点确定求解问题的一个问题状态 (problem state) 由根结点到其它结点的所有路径确定了这个 问题的状态空间(state space) 解状态(solution states)是这样一些问题状 态S，对于这些问题状态，由根到S的那条路 径确定了这解空间中的一个元组（满足显式 约束） 答案状态(solution states)是这样一些解状 态S，由根到S的路径确定了问题的一个解 （满足隐式约束） 解空间的树结构为状态空间树(state space tree)
●·。利用状态空间树解题 o1设想状态空间树 o2生成问题状态 o3确定问题状态中哪些是解状态 o4哪些解状态是答案状态 生成问题状态→构造状态空间树
利用状态空间树解题 1 设想状态空间树 2 生成问题状态 3 确定问题状态中哪些是解状态 4 哪些解状态是答案状态 生成问题状态 → 构造状态空间树
状态空间树术语 ●活结点:自己已经生成而其所有的儿子 结点还没有全部生成的结点。 E结点(正在扩展的结点):当前正在 生成其儿子结点的活结点 死结点:不再进一步扩展或者其儿子结 点已全部生成的生成结点。 静态树( static trees):树结构与所要解 决的问题的实例无关。 动态树( dynamic trees):根据不同的 实例而使用不同的树结构
状态空间树术语 ⚫ 活结点：自己已经生成而其所有的儿子 结点还没有全部生成的结点。 ⚫ E-结点（正在扩展的结点）：当前正在 生成其儿子结点的活结点。 ⚫ 死结点：不再进一步扩展或者其儿子结 点已全部生成的生成结点。 静态树(static trees)：树结构与所要解 决的问题的实例无关。 动态树(dynamic trees)：根据不同的 实例而使用不同的树结构
构造状态空间树的两个方法 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
