使用C++和python解决分支界限解决分配问题

#include<iostream> using namespace std; #define MAX_FLOAT_NUM 10000.0 #define N 4 struct ass_node{ int x[N]; //分配给操作员的作业 int k; //搜索深度 float t; //当前搜索深度下，已分配的作业所需时间 float b; //本结点所需的时间下界 struct ass_node *next; }; typedef struct ass_node ASS_NODE; float c[N][N]; //n个操作员分别完成n项作业所需的时间 float bound; //当前已搜索到的可行解的最优时间 ASS_NODE *qbase; //优先队列的首指针 void Q_insert(ASS_NODE *qbase,ASS_NODE *xnode){ ASS_NODE *p; if(qbase->next==NULL){ qbase->next=xnode; xnode->next=NULL; } else if(xnode->b < qbase->next->b){ xnode->next=qbase->next; qbase->next=xnode; } else{ p=qbase->next; while(p->next){ if((xnode->b > p->b)&&(xnode->b < p->next->b)){ xnode->next=p->next; p->next=xnode; break; } p=p->next; } if(p->next==NULL){ p->next=xnode; xnode->next=NULL; } } } ASS_NODE *Q_delete(ASS_NODE *qbase){ ASS_NODE *p; p=qbase->next; qbase->next=p->next; return p; } float job_assigned(float c[][N],int n,int job[]) { int i,j,m; ASS_NODE *xnode,*ynode,*qbase; qbase=new ASS_NODE; qbase->next=NULL; float min,bound=MAX_FLOAT_NUM; xnode=new ASS_NODE; for(i=0;i<n;i++) //初始化xnode所指向的根结点 xnode->x[i]=-1; xnode->t=xnode->b=0; xnode->k=0; while(xnode->k!=n){ //非叶子结点，继续向下搜索 for(i=0;i<n;i++){ //对n 个操作员分别判断处理 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++; //该结点下一次的搜索深度 for(j=ynode->k;j<n;j++){ //未分配作业最小时间估计 min=MAX_FLOAT_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中返回 job[i]=xnode->x[i]; while(qbase->next){ //释放结点缓冲区 xnode=Q_delete(qbase); delete xnode; } return min; } int main() { int i,j; int job[N]; cout<<"请输入各操作员完成各项作业所需要的时间:"<<endl; for(i=0;i<N;i++) for(j=0;j<N;j++) cin>>c[i][j]; cout<<"完成任务的最优时间为:\n"; cout<<job_assigned(c,4,job)<<endl; cout<<"作业分配方案为："<<endl; cout<<"作业号:\t0\t1\t2\t3\t"<<endl; cout<<"操作员:\t"<<job[0]<<"\t"<<job[1]<<"\t"<<job[2]<<"\t"<<job[3]<<"\t"<<endl; cout<<"耗 时:\t"<<c[0][job[0]]<<"\t"<<c[1][job[1]]<<"\t"<<c[2][job[2]]<<"\t"<<c[3][job[3]]<<"\t"<<endl; }