分支限界法介绍

相比回溯法搜索，分支限界法是一种启发式搜索策略。 分支与限界法不再单纯的像回溯法那样盲目的往前搜索，也不是遇到死胡同才往回走，而是依据节点表中不断更新的信息（此处的信息可根据具体情况具体选择），不断的调整自己的搜索方向，有选择，有目的地往前搜索；回溯也不是单纯地沿着父亲节点，一层一层地向上回溯，而是依据节点表中的信息进行回溯。

以具体例子学习-----作业分配问题

实现要求：

n个操作员以n种不同时间完成n项不同的作业，要求分配每位操作员完成一项作业，使完成n项作业的时间总和最小。

本次实验以4个操作员4份工作为例，数据如下所示，第2行第2列的12表示第2个操作员完成第二项工作需要时间12。

38412912135879312768

 

 

令Tik表示在深度k下，把作业分配给操作员i时的时间下界，那么如图所示，k=0时有：（计算下界的方式为当前值+后续值的最小值且不考虑每个员工只做一项工作的约束，所以只是个下界，并且确定值）

T00 = 3+7+6+3=19 

T10 = 9+7+4+3=23

T20 = 8+7+4+5=24

T30 = 12+7+4+3=26

下界值小于bound（9999），根据下界值从小打到插入优先队列。队首元素T00。【bound值仅在某一结点达到叶节点时更新】

从优先队列弹出队首元素，并且生成相应的孩子节点，如图为6，7，8，对应于把1号作业分配给剩余操作员的情况，计算下界。

T11=3+12+6+3=24

T21=3+7+6+5=21

T31=3+7+9+3=22

同样按照下界大小插入到优先队列，例如T21即7号节点下界为21，比当前节点和先前节点都小，所以它才是队首元素。

循环这个过程，直到某个节点到达队首并且满足为叶节点时，返回，此节点就是所要求的最优值。

分支限界法解作业分配问题过程可以描述如下：

(1) 建立根节点X，令根节点的深度X.k=0，未分配作业操作员编号集合X.S={0,1...n-1},已分配作业操作员编号的X.m=fai，把当前问题最优下界bound置999999.

(2) 令i=0

(3) 若i位于X.S，建立儿子节点Yi，把节点X的数据复制到节点Yi,否则转步骤 (7)

(4) 令Yi.m=Yi.m并{ i }，Yi.S=Yi.S - { i }, Yi.xi=Yi=k, Yi.k = Yi.k+1(多一个值，意味着深度加1，每个操作员都分配就到了叶节点深度)，如上所示计算深度Yi.t。

(5) 如果Yi.t<bound,转步骤(6);否则剪去节点Yi,转步骤(7)

(6) 把节点Yi按t从小打到插入优先队列，如果Yi时叶子节点，说明它是问题的一个可行解，用Yi.t更新当前的可行解最优时间下界bound。

(7) i = i+1,若i<n,转步骤(3)，否则转步骤(8)

(8) 取下队列首元素作为子树的根节点X，若X.k=n,则该节点是叶子节点，表明它是问题的最优解，算法结束，向量X.x便是最优方案；否则转步骤(2)

具体代码实现如下：

#include<iostream> using namespace std; #define MAX_NUM 99999 const int n = 4; float c[n][n];//n个操作员分别完成n项作业所需时间 float bound = MAX_NUM;//当前已搜索可行解的最优时间 struct ass_node { int x[n];//分配给操作员的作业 int k;//搜索深度 float t;//当前搜索深度下，已分配作业所需时间 float b;//本节点所需的时间下界 struct ass_node* next;//优先队列链指针 }; typedef struct ass_node* ASS_NODE; //把xnode所指向的节点按所需时间下界插入优先队列qbase中，下界越小，优先性越高 void Q_insert(ASS_NODE qbase, ASS_NODE xnode) { ASS_NODE temp = qbase->next; ASS_NODE temp2 = qbase; while (temp != NULL) { if (xnode->b < temp->b) { break; } temp2 = temp; temp = temp->next; } xnode->next = temp2->next; temp2->next = xnode; } //取下并返回优先队列qbase的首元素 ASS_NODE Q_delete(ASS_NODE qbase) { //ASS_NODE temp = qbase; ASS_NODE rt = new ass_node;//只是一个node if (qbase->next != NULL) *rt = *qbase->next; else rt = NULL; qbase->next = qbase->next->next; return rt; } //分支限界法实现 float job_assigned(float (*c)[n], int n, int* job) { int i, j, m; ASS_NODE xnode,ynode=NULL; ASS_NODE qbase = new ass_node; qbase->next = NULL; qbase->b = 0;//空头节点 float min, bound = MAX_NUM; xnode = new ass_node; for (i = 0;i < n;i++) xnode->x[i] = -1;//-1表示尚未分配 xnode->t = xnode->b = 0; xnode->k = 0; //非叶子节点，继续向下搜索 while (xnode->k != n) { //对n个操作员分别判断处理 for (i = 0;i < n;i++) { if (xnode->x[i] == -1) {//i操作员未分配工作 ynode = new ass_node;//为i操作员建立一个节点 *ynode = *xnode;//把父节点数据复制给它 ynode->x[i] = ynode->k;//作业k分配给操作员i ynode->t += c[i][ynode->k];//已分配作业累计时间 ynode->b = ynode->t; ynode->k++;//该节点下一次搜索深度 ynode->next = NULL; for (j = ynode->k;j < n;j++) {//未分配作业最小时间估计 min = MAX_NUM; for (m = 0;m < n;m++) { if ((ynode->x[m] == -1) && c[m][j] < min) min = c[m][j]; } ynode->b += min;//本节点所需时间下界 } if (ynode->b < bound) { Q_insert(qbase, ynode);//把节点插入优先队列 if (ynode->k == n)//得到一个可行解 bound = ynode->b;//更新可行解的最优下界 } else delete ynode;//大于可行解最优下界 } } delete xnode;//释放节点xnode的缓冲区 xnode = Q_delete(qbase);//取下队列首元素xnode } min = xnode->b; for (i = 0;i < n;i++)//保存最优方案 job[i] = xnode->x[i]; while (qbase->next) { xnode = Q_delete(qbase); delete xnode; } return min; } int main() { c[0][0] = 3;c[0][1] = 8;c[0][2] = 4;c[0][3] = 12; c[1][0] = 9;c[1][1] = 12;c[1][2] = 13;c[1][3] = 5; c[2][0] = 8;c[2][1] = 7;c[2][2] = 9;c[2][3] = 3; c[3][0] = 12;c[3][1] = 7;c[3][2] = 6;c[3][3] = 8; int* job = new int[n]; for (int i = 0;i < n;i++) job[i] = -1; float result = job_assigned(c, n, job); for (int i = 0;i < n;i++) cout << job[i] << " "; cout << endl; cout << result << endl; system("pause"); return 0; }

 结构体编程需要注意：

结构体指针* P和* Q,如果P=Q赋值，Q变P也变，但是*P = *Q相当于深拷贝，并不会出现类似情况，刚开始在未提前设置链表头节点时出了一大堆bug都是因为赋值产生，需要注意了！！！！ 

最好的建议是提前生成一个空的头指针，这样在插入和删除操作中都会简单很多，不然插入删除考虑生成和删除头节点等不必要的麻烦，很头痛的。

附上当时未分配头节点写的课后6-4零件的指定重量下最小价格的代码，和作业分配代码稍有不同，因为两个零件可以来自同一商家。

#include<iostream> #include<fstream> using namespace std; #define MAX_NUM 99999 int bound = MAX_NUM; ifstream fi("input.txt"); ofstream fo("output.txt"); struct ass_node { int x[10]; int k;//搜索深度 int t;//当前搜索深度下，已分配作业所需价格 int w;//当前搜索深度下，已分配作业所需重量 int b;//本节点所需的价格下界 struct ass_node* next;//优先队列链指针 }; typedef struct ass_node* ASS_NODE; //把xnode所指向的节点按所需时间下界插入优先队列qbase中，下界越小，优先性越高 void Q_insert(ASS_NODE qbase, ASS_NODE xnode) { if (xnode->b < qbase->b) { ass_node* temp = new ass_node; *temp = *qbase; *qbase = *xnode; *xnode = *temp; qbase->next = xnode; return; } ASS_NODE temp = qbase; ASS_NODE temp2 = qbase; while (temp != NULL) { if (xnode->b < temp->b) { break; } temp2 = temp; temp = temp->next; } xnode->next = temp2->next; temp2->next = xnode; } //取下并返回优先队列qbase的首元素 ASS_NODE Q_delete(ASS_NODE qbase,int n) { //ASS_NODE temp = qbase; ASS_NODE rt = new ass_node;//只是一个node rt->b = qbase->b; rt->w = qbase->w; rt->k = qbase->k; rt->next = NULL; rt->t = qbase->t; for (int i = 0;i < n;i++) rt->x[i] = qbase->x[i]; *qbase = *qbase->next; return rt; } //优先队列分支限界法 int job_assigned(int** c, int** w, int n,int m, int d, int* job) { int i, j, k; ASS_NODE xnode, ynode, qbase = NULL; int min, bound = MAX_NUM; xnode = new ass_node; for (i = 0;i < n;i++) xnode->x[i] = -1;//-1表示尚未分配 xnode->t = xnode->w = xnode->b = 0; xnode->k = 0; while (xnode->k != n) { //对n个部件分别判断处理 for (i = 0;i < n;i++) {//每个深度代表一个零件，每个零件有多种分配方式 ynode = new ass_node; *ynode = *xnode; ynode->x[ynode->k] = i; ynode->t += c[ynode->k][i]; ynode->w += w[ynode->k][i]; //计算价格下界 ynode->b = ynode->t; ynode->k++;//该节点下一次搜索深度 ynode->next = NULL; for (j = ynode->k;j < n;j++) {//未分配零件的最小价格估计 min = MAX_NUM; for (k = 0;k < n;k++) { if ((ynode->x[k] == -1) && c[k][j] < min) min = c[k][j]; } ynode->b += min;//本节点所需价格下界 } //更新bound if (ynode->b < bound && ynode->w <= d) { if (qbase == NULL) {//深拷贝,Make一个头节点 qbase = new ass_node; *qbase = *ynode;//没有*就是简单浅拷贝！！！一变全变！！！！！ } else Q_insert(qbase, ynode);//把节点插入优先队列 if (ynode->k == n)//得到一个可行解 bound = ynode->b;//更新可行解的最优下界 } else delete ynode;//不满足最优解 } delete xnode;//释放节点xnode的缓冲区 //出队 xnode = Q_delete(qbase, n);//取下队列首元素xnode } //输出 min = xnode->b; for (i = 0;i < n;i++)//保存最优方案 job[i] = xnode->x[i]; while (qbase) { if (qbase->next != NULL) { xnode = Q_delete(qbase, n); delete xnode; } else {//最后一个节点 qbase = NULL; } } return min; } int main() { int n, m, d;//n个部件 m个供应商 d：最大重量 int i, j; fi >> n;fi >> m;fi >> d; int** c = new int *[n]; for (i = 0;i < n;i++) { c[i] = new int[m]; for (j = 0;j < m;j++) fi >> c[i][j]; } int** w = new int *[n]; for (i = 0;i < n;i++) { w[i] = new int[m]; for (j = 0;j < m;j++) fi >> w[i][j]; } int* fenpei = new int[n]; for (int i = 0;i < n;i++) fenpei[i] = -1;//-1表示第i个部件未分配商家 int result = job_assigned(c, w, n,m, d, fenpei); for (int i = 0;i < n;i++) /*fo << fenpei[i]<<" ";*/ cout << fenpei[i] << " "; cout << endl; fo << endl; fo << result; cout << result << endl; system("pause"); return 1; }