【分支限界法】任务分配问题 (nxn)

大家好，欢迎来到IT知识分享网。

1.问题引入：

任务分配问题要求把n项任务分配给n个人，每个人完成每项任务的成本不同，要求分配总成本最小的最优分配方案。

设当前已对人员1～i分配了任务，并且花费了成本cur_cost，则限界函数可以定义：

lb=每个人对应的最小任务成本之和；

则最优解为：

bestcost=cur_cost）+lb；

任务和人员的编号均为1～n，解空间每一层对应一个人员的分配。

根结点对应人员0（虚结点），依次为人员1、2、…、n分配任务。

叶子结点对应人员n。

解向量为x：x[i]表示人员i分配任务编号。初始时所有元素值为0，表示没有分配。

临时标识数组work：work[i]=1表示任务i已经分配。初始时所有元素值为0，表示没有分配。

用best[Max]存放最优分配方案， bestcost（初始值为1e5）存放最优成本。

 2.代码：

#include<bits/stdc++.h> using namespace std; #define Max 2000 int n; int cost[Max][Max]; int best[Max]; int bestcost=1e5; struct node{ int num; //已分配人数 int cur_cost; //已计算成本 int lb; //当前下界 int x[Max]; //第几个人分配第几个任务 int work[Max]; //任务是否分配 0为未分配； bool operator<(const node& s) const{//定义排序规则 return lb>s.lb; } }; void bound(node&x){//计算下界函数 int Min=0; for(int i=x.num+1;i<=n;i++){ int mini=Max; for(int j=1;j<=n;j++){ if(x.work[j]==0&&cost[i][j]<mini){ mini=cost[i][j]; } } Min+=mini; } x.lb=x.cur_cost+Min; } //注意：这里每一次计算完bound(y),并不能保证其最终取的cur_cost为lb,所以每一个扩展节点计算lb后就算它是最小的，也必须计算完所有的节点才能打印输出。 //(第一个达到叶子结点的并非全局最优解)与上题作业调度问题的区别是没有贪心计算下界，约束条件少一点。 void BFS(){ priority_queue<node> Q;//创建优先队列； node x,y; //初始化根节点 x.num=0; x.cur_cost=0; memset(x.x,0,sizeof(x.x)); memset(x.work,0,sizeof(x.work)); bound(x); Q.push(x); while(!Q.empty()){ node z=Q.top(); Q.pop(); //到达叶子结点，及时更新最优成本bestcost值 if(z.num==n){ if(z.cur_cost<bestcost){ bestcost=z.cur_cost; for(int j=1;j<=n;j++){ best[j]=z.x[j]; } } } //计算新节点的各个值 y.num=z.num+1; for(int i=1;i<=n;i++){ if(z.work[i]) continue; //计算y的x[]值 for(int j=1;j<=n;j++){ y.x[j]=z.x[j]; } y.x[y.num]=i; //计算y的work[]值 for(int k=1;k<=n;k++){ y.work[k]=z.work[k]; } y.work[i]=1; //计算y的cur_cost和lb值； y.cur_cost=z.cur_cost+cost[y.num][i]; bound(y); //判断并入队； if(y.lb<=bestcost){ Q.push(y); } } } } int main(){ cout<<"输入人员数/任务数大小: n"<<endl; cin>>n; printf("输入人员-任务值(%d x %d矩阵)\n",n,n); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>cost[i][j]; } } BFS(); cout<<"最佳方案为:"<<endl; for(int i=1;i<=n;i++){ printf("第%d个人分配%d个任务\n",i,best[i]); } cout<<"总成本为="<<bestcost<<endl; return 0; }

3.运行截图：

菜鸟进化中…….

欢迎大家一起学习交流