算法分析与设计[分枝限界法].pptVIP

第七章 分枝-限界法 上章知识回顾 问题状态 解状态 状态空间 答案状态 状态空间树 活结点 E-结点 死结点 n-皇后问题描述 将n个皇后放置在一个n×n的棋盘上，要求没有两个皇后可以互相攻击。 攻击的定义：两个皇后出现在同一行、或同一列、或者同一条斜线上都视为出现了攻击。 8-皇后问题的一个解 n-皇后问题 用n-元组(x1,x2,…,xn)表示棋盘上皇后的位置状态 下标表示皇后i (i=1,2,…,n) xi表示放置皇后i所在的列号 显式约束条件：每个xi只从集合Si={1,2,…,n}取值 满足显式约束的所有元组确定一个可能的解空间 ? 解空间由nn个n-元组组成 隐式约束条件 没有两个xi可以相同，而且没有两个皇后可以在同一条斜线上 ? 由前者得，所有解都是n-元组(1,2,…,n)的置换，因此，解空间缩小为 n！个元组 4-皇后问题解空间的树结构 结点按深度优先检索编号 叶子结点有4！＝ 24个 解空间树结构的术语 树中每个结点确定求解问题的一个问题状态(problem state) 由根结点到其它结点的所有路径确定了这个问题的状态空间(state space) 解状态(solution states)是这样一些问题状态S，对于这些问题状态，由根到S的那条路径确定了这解空间中的一个元组（满足显式约束） 答案状态(solution states)是这样一些解状态S，由根到S的路径确定了问题的一个解（满足隐式约束） 解空间的树结构为状态空间树(state space tree) 利用状态空间树解题 1 设想状态空间树 2 生成问题状态 3 确定问题状态中哪些是解状态 4 哪些解状态是答案状态 生成问题状态 ? 构造状态空间树 状态空间树术语 活结点：自己已经生成而其所有的儿子结点还没有全部生成的结点。 E-结点（正在扩展的结点）：当前正在生成其儿子结点的活结点。 死结点：不再进一步扩展或者其儿子结点已全部生成的生成结点。 构造状态空间树的两个方法 回溯法 当前E-结点R，生成一个新的儿子C，则C就变成一个新的E-结点，对子树C完全检测后，R结点再次成为E-结点。 分枝-限界方法 一个E-结点一直保持到变成死结点为止。 限界函数 以上两种方法都使用限界函数杀死还没有全部生成其儿子结点的那些活结点。 4-皇后问题的限界函数 如果(x1, x2, …, xi)是到当前E-结点的路径，那么具有父-子标记xi+1的所有儿子结点是一些这样的结点，它们使得(x1, x2, …, xi+1)表示没有两个皇后正在互相攻击的一种棋盘格局。 4-皇后问题回溯法vs状态空间树 结点按深度优先检索编号 叶子结点有4！＝ 24个 4-皇后问题—回溯期间的生成树 分枝－限界法 在生成当前E-结点全部儿子之后再生成其它活结点的儿子，并且，用限界函数帮助避免生成不包含答案结点子树的状态空间 FIFO检索：活结点表采用队 LIFO检索：活结点表采用栈 FIFO分枝－限界法例7.1（4-皇后问题） 4-皇后问题—回溯 vs FIFO分枝-限界 LC-检索（Least Cost） 分枝-限界失败的原因 对下一个E-结点的选择规则过于死板。 如何解决？ 排序，让答案结点排在前面！ 寻找一种“有智力”的排序函数C(·)，该函数能够让答案结点尽早生成。 排序的标准 下一个E-结点应当是生成答案结点花费成本最小的结点，因此C(·)又称作结点成本函数。 LC：Least Cost 分枝-限界策略的种类 根据对状态空间树中结点检索次序的不同，可将分枝-限界的设计策略分为： FIFO检索，活结点采用一张先进先出表 LIFO检索，活结点采用一张先进后出表 LC分枝-限界检索，活结点采用一张易于操作的线性表。 LC-检索（结点成本的两个标准） 一、在生成一个答案结点之前，子树X需要生成的结点数。 二、在子树X中离X最近的那个答案结点到X的路径长度。以图7.1为例 节点1、18和34、29和35、30和38的代价分别是4，3，2，1 其他2，3，4级上的点代价应分别大于3，2，1 生成结点（1→2 18 34 50→19 24 29→30 32→31） LC-检索（结点成本函数） C(·)定义 如果X是答案结点，则C(X)是由状态空间树的根结点到X的成本（即花费的代价，可以是级数、计算复杂度等）。 如果X不是答案结点且子树X不包含任何答案结点，则C(X)＝∞。 如果X不是答案结点但子树X包含答案结点，则C(X)等于子树X中具有最小成本的答案结点的成本。 LC-检索（成本估计函数） 从前面的两个成本度量标准看， 计算C(·)的工作量与原问题的解具有相同复杂度。这是因为计算一个结点的代价通常要检索包含一个答案结点的子树才能确定，而这正是解决此问题所要作