《计算机算法基础》课程教学资源（PPT课件讲稿）分枝－限界法

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

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

●·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