安徽理工大学：《算法设计与分析 Algorithm Design and Analysis》课程教学资源（PPT课件讲稿）第8章 计算机算法基础（分支限界法）

计算机算法基础 分枝一限界法

计算机算法基础 分枝－限界法

0 预备知识 。问题状态 。状态空间树 。解状态 。活结点 。状态空间 oE-结点 。答案状态 。死结点 0 等等.… 。本节主要目的 通过对-皇后问题的分析，学习以上概念， 并且了解▣溯法

0 预备知识  问题状态  解状态  状态空间  答案状态  状态空间树  活结点  E-结点  死结点  等等……  本节主要目的 通过对n-皇后问题的分析，学习以上概念， 并且了解回溯法

解空间树结构的术语 树中每个结点确定求解问题的一个问题状态 (problem state) 由根结点到其它结点的所有路径确定了这个 问题的状态空间(state space) 解状态solution states)是这样一些问题状 态S,对于这些问题状态，由根到S的那条路 径确定了这解空间中的一个元组（满足显式 约束) 答案状态(solution states)是这样，一些解状 态S,由根到S的路径确定了问题的一个解 (满足隐式约束) 解空间的树结构为状态空间树(state space tree)

解空间树结构的术语  树中每个结点确定求解问题的一个问题状态 (problem state)  由根结点到其它结点的所有路径确定了这个 问题的状态空间(state space)  解状态(solution states)是这样一些问题状 态S，对于这些问题状态，由根到S的那条路 径确定了这解空间中的一个元组（满足显式 约束）  答案状态(solution states)是这样一些解状 态S，由根到S的路径确定了问题的一个解 （满足隐式约束）  解空间的树结构为状态空间树(state space tree)

利用状态空间树解题 。1设想状态空间树 。2生成问题状态 。3确定问题状态中哪些是解状态 。4哪些解状态是答案状态 生成问题状态→构造状态空间树

利用状态空间树解题  1 设想状态空间树  2 生成问题状态  3 确定问题状态中哪些是解状态  4 哪些解状态是答案状态 生成问题状态 → 构造状态空间树

状态空间树术语 。活结点：自己已经生成而其所有的儿子 结点还没有全部生成的结点。 。E-结点（正在扩展的结点）：当前正在 生成其儿子结点的活结点。 0 死结点：不再进一步扩展或者其儿子结 点己全部生成的生成结点。 静态树(static trees):树结构与所要解 决的问题的实例无关。 动态树(dynamic trees):根据不同的 实例而使用不同的树结构

状态空间树术语 ⚫ 活结点：自己已经生成而其所有的儿子 结点还没有全部生成的结点。 ⚫ E-结点（正在扩展的结点）：当前正在 生成其儿子结点的活结点。 ⚫ 死结点：不再进一步扩展或者其儿子结 点已全部生成的生成结点。 静态树(static trees)：树结构与所要解 决的问题的实例无关。 动态树(dynamic trees)：根据不同的 实例而使用不同的树结构

构造状态空间树的两个方法 。回溯法 当前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