第八章分支与限界.doc

第八章 分支与限界8.1 分支与限界法的基本思想一、基本思想：1、在结点估算沿着它的各儿子结点搜索时，目标函数可能取得的“界”，2、把儿子结点和目标函数可能取得的“界”，保存在优先队列或堆中，3、从队列或堆中选取“界”最大或最小的结点向下搜索，直到叶子结点，4、若叶子结点的目标函数的值，是结点表中的最大值或最小值，则沿叶子结点到根结点的路径所确定的解，就是问题的最优解，由该叶子结点所确定的目标函数的值，就是解这个问题所得到的最大值或最小值二、目标函数“界”的特性：是部分解，是相应的界1、对最小值问题，称为下界，意思是向下搜索所可能取得的值最小不会小于这些下界若是所得到的部分解，满足： （8.1.1）2、对最大值问题，称为上界，意思是向下搜索所可能取得的值最大不会大于这些上界若是所得到的部分解，满足：三、两种分支方法：设解向量， 的取值范围为有穷集，，1、每棵子树都有个分支：最坏情况下，结点表的空间为，若状态空间树是完全叉树， ，结点表的空间为2、每棵子树只有两个分支，取特定值的分支、及不取特定值的分支： 状态空间树是完全二叉树，最坏情况下结点表的空间为8.2 货郎担问题有向赋权图，顶点集。

为图的邻接矩阵，表示顶点到顶点的关联边的长度，又把称为费用矩阵8.2.1 费用矩阵的特性及归约：图的最短哈密尔顿回路，：回路的费用因为中的元素表示顶点到顶点的关联边的费用，一、哈密尔顿回路与费用矩阵的关系：引理8.1 令是一个有向赋权图，是图的一条哈密尔顿回路，是图的费用矩阵，则回路上的边对应于费用矩阵中每行每列各一个元素证明 图有个顶点，费用矩阵第行元素：顶点到其它顶点的出边费用；费用矩阵第列元素：其它顶点到顶点的入边费用是图的一条哈密尔顿回路，是回路中的任意一个顶点，，在回路中只有一条出边，对应于费用矩阵中第行的一个元素；在回路中只出现一次，费用矩阵的第行有且只有一个元素与其对应在回路中只有一条入边，费用矩阵中第列也有且只有一个元素与其对应回路中有个不同顶点，费用矩阵的每行每列都有且只有一个元素与回路中的顶点的出边与入边一一对应例：，图8.1(a)中5城市的货郎担问题的费用矩阵，令是哈密尔顿回路，回路上的边对应于费用矩阵中的元素图8.1 5城市货郎担问题的费用矩阵及其归约二、费用矩阵的归约 1、行归约和列归约定义8.1 费用矩阵的第行（或第列）中的每个元素减去一个正常数(或)，得到一个新的费用矩阵，使得中第行（或第列）中的最小元素为0，称为费用矩阵的行归约(或列归约)。

称为行归约常数，称为列归约常数例：把图8.1(a)中归约常数，，，，列归约常数，所得结果如图8.1(c)所示2、归约矩阵定义8.2 对费用矩阵的每一行和每一列都进行行归约和列归约，得到一个新的费用矩阵，使得中每一行和每一列至少都有一个元素为0，称为费用矩阵的归约矩阵称为费用矩阵的归约矩阵称常数 （8.2.1）为矩阵的归约常数例：对图8.1(a)中的费用矩阵进行归约，得到图8.1(c)所示归约矩阵归约常数为3、归约矩阵与哈密尔顿回路的关系定理8.1 有向赋权图，的哈密尔顿回路，的费用矩阵，是以计算的回路费用是的归约矩阵，归约常数为，是以计算的回路费用，有： （8.2.2）证明 和分别是和的第行第列元素， ， 是以计算的哈密尔顿回路的费用，令是计算的同一条哈密尔顿回路的费用，令由引理8.1，回路上的边对应于中每行每列各一个元素有定理证毕定理8.2 有向赋权图，是的最短哈密尔顿回路，是的费用矩阵，是的归约矩阵，令是图的邻接矩阵，则也是的最短的哈密尔顿回路证明 用反证法证明若不是图的最短的哈密尔顿回路，则中必存在另一条回路，是中最短的哈密尔顿回路，同时，它也是中的一条回路。

和分别是以计算的和的费用，有： 其中，是正整数是的一条回路，令和是分别以计算的回路和的费用由定理8.1，有 其中，是费用矩阵的归约常数因此是中比更短的哈密尔顿回路，与定理的前提相矛盾所以，也是的最短的哈密尔顿回路8.2.2 界限的确定和分支的选择先求图费用矩阵的归约矩阵，得到归约常数再转换为求取与相对应的图的最短哈密尔顿回路问题和分别是和的最短哈密尔顿回路的费用，有的最短哈密尔顿回路的费用，最少不会少于是货郎担问题状态空间树中根结点的下界例：图8.1(a)中归约常数48便是该问题的下界该问题的最小费用不会少于488.2.2.1 界限的确定1、搜索策略选取沿某一边出发的路径，作为分支结点；不沿该边出发的其它所有路径集合，作为另一个分支结点2、选取沿方向的路径时，结点下界的确定 的哈密尔顿回路，费用矩阵，以计算的回路费用是的归约矩阵，归约常数为，以计算的回路费用， 1），处理不可能经过的边2）矩阵降阶，删去第行第列所所有元素，得到降阶后的矩阵3）归约，得归约常数，有 例：图8.1(a)及图8.1(c)的5城市货郎担问题的费用矩阵、及其归约矩阵选取从顶点出发，沿着的边前进，则该回路的边包含费用矩阵中的。

删去中的第1行和第0列的所有元素， 素置为∞图8.1(c)中5×5的归约矩阵，降阶为图8.2(b)所示的4×4的矩阵进一步进行归约，得到图8.2(c)所示的归约矩阵，其归约常数为5表明沿出发，经边的回路，其费用至少不会小于 48＋5 = 53图8.2 Y结点对费用矩阵的降阶处理4）处理不可能经过的边： (1) 不和其它已经选择的边相连接，把置为∞，如图8.3(a)所示；(2) 和以前选择的边连接成，把置为∞，如图8.3(b)所示；(3) 和以前选择的边连接成，把置为∞，如图8.3(c)所示；(4) 和以前选择的边连接成，把置为∞，如图8.3(d)所示；图8.3 选择有向边时的几种可能情况5） 父亲结点，下界，降阶后的归约常数为，结点的下界为 （8.2.3）3、不沿方向的结点下界的确定1）回路不包含边， 置为∞不降阶）2） （8.2.4）3）结点的下界为： （8.2.5）例：在图8.1(a)中，根结点作为父亲结点，则选择边向下搜索作为结点为，结点为的下界为：结点的下界为：8.2.2.2 分支的选择选择分支的思想方法：1. 沿的方向选择，使所选择的路线尽可能短；2. 沿最大的方向选择，使尽可能大；令是的元素集合，是中使达最大的元素，即： （8.2.6）边就是所选择的分支方向。

例：图8.1(a)中的费用矩阵归约为8.1(c)中矩阵，根结点的下界有，搜索方向的选择如下： 所选择的方向为边，据此建立结点和此时， （8.2.7）8.2.3 货郎担问题的求解过程结点数据结构： typedef struct node_data {Type c[n][n]; /* 费用矩阵 */int row_init[n]; /* 费用矩阵的当前行映射为原始行 */int col_init[n]; /* 费用矩阵的当前列映射为原始列 */int row_cur[n]; /* 费用矩阵的原始行映射为当前行 */int col_cur[n]; /* 费用矩阵的原始列映射为当前列 */int ad[n]; /* 回路顶点邻接表 */int k； /* 当前费用矩阵的阶 */Type w; /* 结点的下界 */} NODE;分支限界法求解货郎担问题的求解过程：1. 分配堆缓冲区，初始化为空堆；2. 建立结点， 拷贝到， 初始化为；归约，计算归约常数，下界；初始化回路的顶点邻接表；3. 按(8.2.4)式，由中所有的元素，计算；4. 按(8.2.6)式，选取使达最大的元素作为，选择边作为分支方向；5. 建立儿子结点，拷贝到，拷贝到，拷贝到；把中的置为∞，归约；计算结点的下界；把结点按插入最小堆中； 6. 建立儿子结点， 拷贝到， 拷贝到，拷贝到； 的有关元素置为∞；7. 降阶, 减1，归约降阶后的，按(8.2.3)式计算结点的下界； 8. 若，直接判断最短回路的两条边，并登记于路线邻接表，使；9. 把结点按插入最小堆中；10. 取下堆顶元素作为结点，若，算法结束；否则，转3；例8.1 求解图8.1(a)所示的5城市货郎担问题。

该问题的求解过程如图8.4所示，过程如下：图8.4 用分支限界法解5城市货郎担问题的过程8.2.4 几个辅助函数的实现数据结构： typedef struct node_data {Type c[n][n]; /* 费用矩阵 */int row_init[n]; /* 费用矩阵的当前行(下标)映射为原始行(内容) */int col_init[n]; /* 费用矩阵的当前列(下标)映射为原始列(内容)*/int row_cur[n]; /* 费用矩阵的原始行(下标)映射为当前行(内容) */int col_cur[n]; /* 费用矩阵的原始列(下标)映射为当前列(内容) */int ad[n]; /* 回路顶点邻接表 */int k； /* 当前费用矩阵的阶 */Type w; /* 结点的下界 */} NODE;NODE *xnode; /* 父亲结点指针 */NODE *ynode; /* 儿子结点指针 */NODE *znode; /* 儿子结点指针 */int n_heap; /* 堆元素个数 */typedef struct { /* 堆结构数据 */NODE *p; /* 指向结点元素的指针*/Type w; /* 所指向结点的下界,堆元素的关键字 */} HEAP; ：与顶点（出）相邻接的顶点（入）序号。

例：的回路由边、、、、组成，数组中的登记情况：图8.5 回路顶点邻接表的登记情况算法中使用下面的几个函数：Type row_min(NODE * node ,int row,Type &second )； 计算费用矩阵行的最小值Type col_min(NODE * node ,int col,Type &second)； 计算费用矩阵列的最小值Type array_red(NODE * node)； 归约所指向结点的费用矩阵Type edge_sel(NODE * node,int &vk,int &vl)； 计算，选择搜索分支的边void del_rowcol(NODE * node,int vk,int vl)； 删除费用矩阵第行、列void edge_byp(NODE * node,int vk,int vl)； 登记回路顶点邻接表，旁路有关的边NODE * initial(Type c[ ][ ],int n)； 初始化1、row_min(NODE * node ,int row,Type &second)函数返回所指向结点的费用矩阵中第行的最小值，次小值回送于引用变量。