文档介绍：第七章 分枝-限界法
*
上章知识回顾
问题状态
解状态
状态空间
答案状态
状态空间树
活结点
E-结点
死结点
通过对n-皇后问题的分析，复习以上概念和回溯法
*
n-皇后问题描述
将n个皇后放置在一个n×n的棋盘上，要求没有两个皇后可以互相攻击。
攻击的定义：两个皇后出现在同一行、或同一列、或者同一条斜线上都视为出现了攻击。
*
8-皇后问题的一个解
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
该解的8元组表示:
(4,6,8,2,7,1,3,5)
*
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-结点一直保持到变成死结点为止。
限界函数
以上两种方法都使用限界函数杀死还没有全部生成其儿子结点的那些活结点。