第八章分支与限界.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便是该问题的下界。该问题的最小费用不会少于48。
8.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)函数返回所指向结点的费用矩阵中第行的最小值，次小值回送于引用变量。

1. Type row_min(NODE *node,int row,Type &second)
2. {
3. Type temp;
4. int i;
5. if (node->c[row][0]c[row][1]) {
6. temp = node->c[row][0]; second = node->c[row][1];
7. }
8. else {
9. temp = node->c[row][1]; second = node->c[row][0];
10. }
11. for (i=2;ik;i++) {
12. if (node->c[row][i] = temp; temp = node->c[row][i];
14. }
15. else if (node->c[row][i]c[row][i];
17. }
18. return temp;
19. }

运行时间：。
工作单元个数：。
2、Type col_min(NODE * node ,int col,Type &second)返回所指向的结点的费用矩阵中第列的最小值，次小值回送于引用变量。
3、Type array_red(NODE *node)归约所指向的结点的费用矩阵，返回值为归约常数

1. Type array_red(NODE *node)
2. {
3. int i,j;
4. Type temp,temp1,sum = 0;
5. for (i=0;ik;i++) { /* 行归约 */
6. temp = row_min(node,i,temp1); /* 行归约常数 */
7. for (j=0;jk;j++)
8. node->c[i][j] temp;
9. sum += temp; /* 行归约常数累计 */
10. }
11. for (j=0;jk;j++) { /* 列归约 */
12. temp = col_min(node,j,temp1); /* 列归约常数 */
13. for (i=0;ik;i++)
14. node->c[i][j] -= temp;
15. sum += temp; /* 列归约常数累计 */
16. }
17. return sum; /* 返回归约常数*/
18. }

运行时间：时间。
工作单元个数：。
4、函数edge_sel计算，选择搜索分支的边。返回的值，出边顶点序号和入边顶点序号。

1. Type edge_sel(NODE * node,int &vk,int &vl)
2. {
3. int i,j;
4. Type temp,d = 0;
5. Type *row_value = new Type[node->k];
6. Type *col_value = new Type[node->k];
7. for (i=0;ik;i++) /* 每一行的次小值 */
8. row_min(node,i,row_value[i]);
9. for (i=0;ik;i++) /* 每一列的次小值 */
10. col_min(node,i,col_value[i]);
11. for (i=0;ik,i++) { /* 对费用矩阵所有值为0的元素*/
12. for (j=0;jk;j++) { /* 计算相应的temp值 */
13. if (node->c[i][j]==0) {
14. temp = row_value[i] + col_value[j];
15. if (temp>d) { /* 求最大的temp值于d */
16. d = temp; vk = i; vl = j;
17. } /* 保存相应的行、列号 */
18. }
19. }
20. }
21. delete row_value;
22. delete col_value;
23. return d;
24. }

运行时间：时间。
工作单元： 。
5、函数del_rowcol删除费用矩阵当前第行、第列的所有元素

1. void del_rowcol(NODE *node,int vk,int vl)
2. {
3. int i,j,vk1,vl1;
4. for (i=vk;ik-1;i++) /* 元素上移 */
5. for (j=0;jc[i][j] = node->c[i+1][j];
7. for (j=vl;jk-1;j++) /* 元素左移 */
8. for (i=0;ic[i][j] = node->c[i][j+1];
10. for (i=vk;ik-1;i++) /* 元素上移及左移 */
11. for (j=vl;jk-1;j++)
12. node->c[i][j] = node->c[i+1][j+1];
13. vk1 = node->row_init[vk]; /* 当前行vk转换为原始行vk1*/
14. node->row_cur[vk1] = -1; /* 原始行vk1置删除标志 */
15. for (i= vk1+1;irow_cur--;
17. vl1 = node->col_init[vl]; /* 当前列vl转换为原始列vl1*/
18. node->col_cur[vl1] = -1; /* 原始列vk1置删除标志 */
19. for (i=vl1+1;icol-cur--;
21. for (i=vk;ik-1;i++) /* 修改vk及其后的当前行的对应原始行号*/
22. node->row_init[i] = node->row_init[i+1];
23. for (i=vl;ik-1;i++)/* 修改vl及其后的当前列的对应原始列号 */
24. node->col_init[i] = node->col_init[i+1];
25. node->k--; /* 当前矩阵的阶数减1 */
26. }

图8.5 矩阵降阶时元素的移动过程
运行时间：时间。
工作单元个数：。
6、函数edge_byp把行、列所表示的边，登记到回路顶点邻接表，旁路矩阵中有关的边：

1. void edge_byp(NODE *node,int vk,int vl)
2. {
3. int i,j,k,l;
4. vk = rowinit[vk]; /* 当前行号转换为原始行号 */
5. vl = col_init[vl]; /* 当前列号转换为原始列号 */
6. node->ad[vk] = vl; /* 登记回路顶点邻接表*/
7. for (i=0;iad[j]!=-1) /* 检查从顶点i开始的通路 */
10. j = node->ad[j];
11. if i!=j) { /* 存在一条起点为i终点为j的通路 */
12. l = node->row_cur[j]; /* j转换为当前行号l */
13. k = node->col_cur[i]; /* i转换为当前列号k */
14. if ((k>0)&&(l>0)) /* 当前行、列号均处于当前矩阵中 */
15. node->c[l][k] = MAX_VALUE_OF_TYPE;
16. } /* 相应元素置为无限大,旁路相应的边*/
17. }
18. }

运行时间：时间。
工作单元个数：。
初始化函数NODE * initial(Type c[ ][ ],int n)叙述如下：

1. NODE *initial(Type c[][],int n)
2. {
3. int i,j;
4. NODE *node = new NODE; /* 分配结点缓冲区 */
5. for (i=0;i node->c[i][j] = c[i][j];
8. for (i=0;irow_init[i] = i; /* 初始行、列号的初始对应关系 */
10. node->col_init[i] = i;
11. node->row_cur[i] = i;
12. node->col_cur[i] = i;
13. }
14. for (i=0;i
15. node->ad[i] = -1;
16. node->k = n;
16. return node; /* 返回结点指针 */
17. }

执行时间：。
不把结点缓冲区所需存储空间包括在内，工作单元个数是。
8.2.5 货郎担问题分支限界算法的实现
算法8.1 货郎担问题的分支限界算法
输入：城市顶点的邻接矩阵c[][],顶点个数n
输出：最短路线费用w及回路的邻接顶点表ad[]
1. template
2. Type traveling_salesman(Type c[][],int n,int ad[])
3. {
4. int i,j,vk,vl,n_heap = 0;
5. Type d,w;
6. NODE *xnode,*ynode,*znode;
7. HEAP *heap = new HEAP[n*n]; /* 分配堆的缓冲区 */
8. HEAP x,y,z; /* x,y,z结点的堆元素 */
9. xnode = initial(c,n); /* 初始化父亲结点—-x结点 */
10. xnode->w = array_red(xnode); /* 归约费用矩阵 */
11. while (xnode->k!=0) {
12. d = edge_sel(xnode,vk,vl); /* 选择分支方向并计算 */
13. znode = new NODE; /* 建立分支结点—-z结点(右儿子结点) */
14. *znode = *xnode; /* x结点数据拷贝到z结点 */
15. znode->c[vk][vl] = MAX_VALUE_OF_TYPE; /* 旁路z结点的边 */
16. array_red(znode); /* 归约z结点费用矩阵 */
17. znode->w = xnode->w + d; /* 计算z结点的下界 */
18. z.w = znode->w; /* 构造z结点的堆元素 */
19. z.p = znode;
20. insert(heap,n_heap,z); /* z结点插入堆中 */
21. ynode = new NODE; /* 建立分支结点—-y结点(左儿子结点) */
22. *ynode = *xnode; /* x结点数据拷贝到y结点 /
23. edge_byp(ynode,vk,vl); /* 登记回路邻接表,旁路有关的边 */
24. del_rowcol(ynode,vk,vl); /* 删除y结点费用矩阵当前vk行vl列*/
25. ynode->w = array_red(xnode); /* 归约y结点费用矩阵 */
26. ynode->w += xnode->w; /* 计算y结点的下界 */
27. y.w = ynode->w; /* 构造y结点的堆元素 */
28. y.p = ynode;
29. if (ynode->k==2) { /* 费用矩阵只剩2阶 */
30. if (ynode->c[0][0]==0) { /* 登记最后的两条边 */
31. ynode->ad[ynode->row_init[0]] = ynode->col_init[0];
32. ynode->ad[ynode->row_init[1]] = ynode->col_init[1];
33. }
34. else {
35. ynode->ad[ynode->row_init[0]] = ynode->col_init[1];
36. ynode->ad[ynode->row_init[1]] = ynode->col_init[0];
37. }
38. ynode->k = 0;
39. }
40. insert(heap,n_heap,y); /* y结点插入堆中 */
41. delete xnode; / 释放没用的x结点缓冲区 */
42. x = delete_min(heap,n_heap); /* 取下堆顶元素作为x结点*/
43. xnode = x.p;
44. }
45. w = xnode->w /* 保存最短路线费用 */
46. for (i=0;iad[i];
48. delete xnode; /* 释放x结点缓冲区*/
49. for (i=1i<=n_heap;i++) /* 释放堆的缓冲区*/
50. delete heap[i].p;
51. delete heap;
52. return w; /* 回送最短路线费用 */
53. }

算法的时间花费估计如下：
第9行初始化父亲结点，第10行归约父亲结点费用矩阵，都需时间。
第11行开始的while循环，在最坏情况下，循环体执行次。
在while循环内部：
12行选择分支方向，需时间。
14行把结点数据拷贝到结点， 16行归约结点费用矩阵，都需时间。
20行把结点插入堆中，在最坏情况下，有个结点，需时间。
22行把结点数据拷贝到结点，需时间。
23行登记回路邻接表，旁路有关的边， 24行删除结点费用矩阵当前行列，
25行归约结点费用矩阵，这些操作都需时间。
40行把结点插入堆中， 42行删除堆顶元素，都需时间。
其余花费为时间。
整个while循环，在最坏情况下需。
第46行的for循环保存路线的顶点邻接表于数组需时间。
第49行释放堆的缓冲区，在最坏情况下，需时间。
算法的运行时间：。
算法所需要的空间：
每个结点需要空间存放费用矩阵，共有个结点，需空间。
8.3 0/1背包问题
8.3.1 分支限界法解0/1背包问题的思想方法和求解过程
个物体重量分别为，价值分别为，背包载重量为
物体按价值重量比递减的顺序，排序后物体序号的集合为。
：选择装入背包的物体集合，
：不选择装入背包的物体集合，
：尚待选择的物体集合。
、、：搜索深度为时的三个集合中的物体。开始时，

一、分支的选择及处理
：比值最大的物体序号，。
把物体装入背包的分支结点，不把物体装入背包的分支结点。
就是集合中的第一个元素。
搜索深度为时，物体的序号就是集合中的元素。
物体装入背包的分支结点作如下处理：

不把物体装入背包的分支结点则做如下处理：

二、上界的确定
：搜索深度为时，分支结点的背包中物体的价值上界
。若
令 （8.3.1）
若：

令：
（8.3.2）
三、求解步骤
1. 把物体按价值重量比递减顺序排序；
2. 建立根结点，令，，，，；
3. 若，算法结束，即为装入背包中的物体，即为装入背包中物体的最大价值；否则，转4；
4. 建立结点， ，，，；按（8.3.1）、（8.3.2）式计算；把结点按插入堆中；
5. 建立结点， ，，，；按（8.3.1）、（8.3.2）式计算；把结点插入堆中；
6. 取下堆顶元素于结点，转3；
例8.2 有5个物体，重量分别为8,16,21,17,12，价值分别为8,14,16,11,7，背包载重量为37，求装入背包的物体及其价值。
假定，物体序号分别为0,1,2,3,4。最后得到的解是，最大价值是30。

图8.6 0/1背包问题分支限界法的求解过程
8.3.2 0/1背包问题分支限界算法的实现
数据结构：

typedef struct {
float w; /* 物体重量 */
float p; /* 物体价值 */
float v; /* 物体的价值重量比 */
int num; /* 物体排序前的初始序号 */
} OBJECT;
OBJECT ob[n];
float M; /* 背包载重量 */
BOOL x[n] /* 最优装入背包的物体 */

typedef struct {
BOOL s1[n]; /* 当前集合S1中的物体 */
int k; /* 当前结点的搜索深度 */
float b; /* 当前结点的价值上界 */
float w; /* 当前集合S1中的物体重量 */
float p; /* 当前集合S1中的物体价值 */
} KNAPNODE；

typedef struct {
KNAPNODE *p; /* 指向结点的数据 */
float b; /* 所指向结点的上界,堆元素的关键字 */
} HEAP

使用bound函数来计算分支结点的上界。bound函数叙述如下：

1. void bound(KNAPNODE *node,float M,OBJECT ob[],int n)
2. {
3. int i = node->k;
4. float w = node->w;
5. float p = node->p;
6. if (node->w>M) /* 物体重量超过背包载重量 */
7. node->b = 0; /* 上界置为0 */
8. else { /* 否则,确定背包的剩余载重量 */
9. while (w+ob[i].w<=M)&&(ib = p + (M – w) * ob[i].p / ob[i].w;
15. else
16. node->b = p;
17. }
18. }

这个函数的执行时间，在最好的情况下是时间，在最坏的情况下是时间。这样，0/1背包问题分支限界算法，可叙述如下：

算法8.2 用分支限界方法实现0/1背包问题
输入：包含n个物体的重量和价值的数组ob[],背包载重量M
输出：最优装入背包的物体obx[],装入背包的物体最优价值v
1. float knapsack_bound(OBJECT ob[],float M,int n,int obx[])
2. {
3. int i,j,k = 0; /* 堆中元素个数的计数器初始化为0 */
4. float v;
5. K