任务分配问题基于深度优先遍历的C++实现算法_c++工作分配问题

 

1 课程设计题目与要求

1.1设计题目：任务分配问题

1.2设计要求：

 问题描述：

//有N个任务需要分配给n个人执行，一个任务对应一个人（意思是说，每个任务只分配给一个人，每个人只分配一个任务）

//对于每一对i，j=1，2，3......n来说，将j个任务分配给第i个人的成本是C[I,J];找出总成本最小的分配方案      

2 总体设计

3 详细设计

3.1数据结构设计（或类设计）

本程序定义了一个主函数，用户可根据界面提示自行操作。由于要实现界面的回复，所以用了大量的函数调用，在控制用户的循环操作时采用了大量的for循环、do while语句、if  else语句、return语句、switch语句等，其中涉及到多个递归函数表达式。

数据成员主要有成本矩阵，贪心成本，最低成本等内容，用户只需要在首页填写矩阵的大小，每个人员分配任务的成本即可。

Arr[][];                                                                  成本矩阵

mincost；                                               每行最小值矩阵

greedcost[];                                                          贪心矩阵

temp[];                                      每种组合方法的成本之和

k;                                            temp数组中第k种成本

cost=0;                                                      当前成本之和

y[];                                              记录纵坐标前驱的数组

CreateArr();                                            初始化成本矩阵

StarMin();                                        初始化mincost[]数组

SetMin();                                            填充mincost[]数组

SumMin();                                            mincost[]数组求和

StarTemp();                                            temp[]数组初始化

StarGreed();                                           初始化贪心矩阵

SumOfGreed();   贪心法求Arr[][]数组的近似最低成本

Recursion();                                                   递归调用函数

Back();                                                                 回溯函数

3.2模块设计

3.2.1初始化成本矩阵函数，在整个程序开始运行之前，先构建一个二维数组，然后由用户输入具体的任务成本，等到整个循环结束，即可退出

3.2.2 初始化mincost[]矩阵函数，对于全局变量mincost[]函数，将Arr[]每一行先存入mincost[]数组中去，有利于后面的比较，并且找出最小值。

3.2.3 填充mincost[]数组函数，从Arr的每一行的第二个值开始比较，如果上一个的值比mincost[]对应的值小的话，就将mincost[]的值改为较小的数值。这样等到循环结束以后，mincost[]数组里面每一个对应的都是Arr每一行对应的最小值。即整个数组填充完毕。

3.2.4 mincost[]数组求和函数，就可以得出对应的成本下界。

3.2.5 temp[]数组初始化，temp数组是用于记录每一种可行的成本，即大于下界，且小于上界的人员分配方案。从而得到的结果存于temp数组中。第一个记录贪心矩阵所得的结果，即上界。

3.2.6初始化贪心矩阵函数，给贪心矩阵一个初始值。

3.2.7贪心法求Arr[][]数组的近似最低成本函数，在每一行选择出最合适的矩阵，作为放入贪心矩阵中，最后将贪心矩阵中的值相加，就可以得到贪心成本。

3.2.8递归调用函数，将Arr每一行的行数，人员数目，每一行所选的纵坐标作为参数传递进去，以是否全部寻找过全部元素作为出口，如果全部搜索了一遍，就可以到达出口。

3.2.9回溯函数，当递归函数的每一次往下搜寻失败的时候，利用回溯函数返回最近一个可执行行上去，继续进行搜寻。 

 

4、运行结果

1、首先给出用户操作界面

2、用户根据提示选择相应功能

例如输入的人员为为4个人的话，则输入每个人员的任务成本，如图所示：

 

运行过后，我们可以得知整个成本矩阵的上界，下界，以及最优成本如下图所示：

 

5.详细代码：

#include<iostream>
#include<cstdlib>
using namespace std;
#define  Max  9999
#define  NUM  10000
//有N个任务需要分配给n个人执行，一个任务对应一个人（意思是说，每个任务只分配给一个人，每个人只分配一个任务）
//对于每一对i，j=1，2，3......n来说，将j个任务分配给第i个人的成本是C[I,J];找出总成本最小的分配方案
 
int Arr[1000][1000];		//成本矩阵
int mincost[1000];			//成本矩阵中每一行最小的成本
int greedcost[1000];		//贪心矩阵
int temp[NUM];				//每种组合方法的成本之和
int k=0;					//temp数组中第k种成本
int cost=0;					//当前成本之和
int y[1000];				//记录纵坐标前驱的数组,y[i]
 
void CreateArr(int number);				//初始化成本矩阵
 
void StarMin(int number);				//初始化mincost[]数组
 
void SetMin(int number);				//填充mincost[]数组
 
int SumMin(int number);					//mincost[]数组求和
 
void StarTemp(int number);				//temp[]数组初始化
 
void StarGreed(int number);						//初始化贪心矩阵
 
int SumOfGreed(int number);		//贪心法求Arr[][]数组的近似最低成本
 
void Recursion(int i1,int j0,int j1,int number);		//递归调用函数
 
int Back(int i,int j,int number);						//回溯函数，清除本层痕迹，返回到上面最近的可执行的一行
 
int main()
{
	int number,i=0,j=0,SumLow=0,SumUp=0;					//任务（人）数量
 
	cout << "请输入任务\\人员数量（n<=1000）：" << endl;
	cin >> number;
 
	CreateArr(number);						//创建二维成本矩阵
 
	StarMin(number);						//初始化mincost[]数组
	
	SetMin(number);							//填充mincost[]数组
 
	SumLow=SumMin(number);					//mincost[]数组求和,成本的下界
 
	StarGreed(number);						//初始化greedcost[]数组
 
	SumUp=SumOfGreed(number);				//贪心法求Arr[][]数组的近似最低成本，即成本的上界
 
	for(int xy=0;xy<number;xy++)			//给纵坐标初始化,贪心矩阵归0
	{
		y[xy]=0;
		greedcost[xy]=Max;
	}
 
	cost=Arr[0][0];
	greedcost[0]=Arr[0][0];
	Recursion(i,y[i],j,number);				//递归调用函数
 
	int SuitCost=temp[0];
	for(int L=1;L<NUM;L++)
	{
		if(temp[L]==0) break;
		if(temp[L]<SuitCost)
		{
			SuitCost=temp[L];
		}
	}
	
	cout<<"成本上界是:"<<SumUp<<endl;
	cout<<"成本下界是:"<<SumLow<<endl;
	cout<<"最小成本是:"<<SuitCost<<endl;
 
	system("pause");
	return 0;
}
 
 
 
void CreateArr(int number)			//构建二维成本矩阵
{
	for(int i=0;i<number;i++)			//生成number*number的二维数组,确定每个人的任务完成成本
	{
		for(int j=0;j<number;j++)
		{
			cout<<"Arr["<<i<<"]["<<j<<"]"<<"=";
			cin>>Arr[i][j];
		}
	}
}
 
void StarMin(int number)			//初始化mincost[]数组
{
	for(int n0=0;n0<number;n0++)	//将mincost[]数组初始化
	{
		mincost[n0]=Arr[n0][0];
	}
}
 
void SetMin(int number)				//填充mincost[]数组
{
	for(int n1=0;n1<number;n1++)	//将成本矩阵中每一行最小的数字存入mincost[]数组中
	{
		for(int n2=0;n2<number-1;n2++)
		{
			if(Arr[n1][n2+1]<mincost[n1])
			{
				mincost[n1]=Arr[n1][n2+1];
			}
		}
	}
}
 
int SumMin(int number)		//mincost[]数组求和
{
	int SumLow=0;
	for(int i0=0;i0<number;i0++)			//SumLow为mincost数组里面的所有数之和，及成本矩阵中最小的数
	{
		SumLow=SumLow+mincost[i0];
	}
	return SumLow;
}
 
void StarTemp(int number)									//temp数组初始化
{
	for(int ii=0;ii<NUM;ii++)
	{
		temp[ii]=0;
	}
}
 
void StarGreed(int number)							//初始化贪心矩阵，里面的每个值都归0
{
	for(int igreed=0;igreed<number;igreed++)
	{
		greedcost[igreed]=0;
	}
}
 
int SumOfGreed(int number)							//贪心法求Arr[][]数组的近似最低成本,即上界
{
	StarTemp(number);								//temp数组初始化
	int minsuit=Max,j1;								//j1记录每一次每一行得到的最合适的值得纵坐标
	for(int i=0;i<number;i++)
	{	
		minsuit=Max;								//每次换行的时候将minsuit初始化成最大值
		for(int j=0;j<number;j++)
		{
			if(greedcost[j]!=0)
			{
				continue;
			}
			if(Arr[i][j]<minsuit)
			{
				minsuit=Arr[i][j];
				j1=j;
			}
		}
		greedcost[j1]=minsuit;
		temp[0]=temp[0]+greedcost[j1];
	}
	return temp[0];
}
void Recursion(int i,int j0,int j,int number)			//递归调用函数,(0,0,0,4)
{
	if(i==0 && y[i]==number) return ;
if(cost<=temp[0])
	{
		if(i>=number-1)
		{
			k++;
			temp[k]=cost;
			
			i=Back(i,j,number);
			j=y[i];
		}
		else{
			i++;
			j=0;
			while(greedcost[j]!=Max)
			{
				j++;
			}
			cost=cost+Arr[i][j];
			y[i]=j;
			greedcost[y[i]]=Arr[i][j];
			
		}
	}
	else{
		if(y[i]>=number-1)
			{	
				i=Back(i,j,number);
				j=y[i];
			}
		else{
					i=Back(i,j,number);
					j=y[i];
			}
	}
	Recursion(i,y[i],j,number);
}
int Back(int i,int j,int number)						//回溯函数，清除本层痕迹，返回到上面最近的可执行的一行
{
	if(i==0)
	{							//如果该行为第一行
		if(y[i]==number-1)
		{						//如果该元素是最后一个
			y[i]++;
			return i;
		}
		else{					//如果该元素不是最后一个
			cost=cost-Arr[i][y[i]];
			greedcost[y[i]]=Max;
			y[i]++;
			greedcost[y[i]]=Arr[i][y[i]];
			cost=cost+Arr[i][y[i]];
			return i;
		}
	}
	else{						//如果不是第一行
			y[i]=j;
			while(greedcost[j]!=Max)
			{
				j++;
				if(j>=number) break;
			}
			if(j<number)
			{							//如果有空闲的位置，清除当行信息，往后挪动
				cost=cost-Arr[i][y[i]];
				greedcost[y[i]]=Max;
				y[i]=j;
				greedcost[y[i]]=Arr[i][y[i]];
				cost=cost+Arr[i][y[i]];
				return i;
			}else{
										//如果没有空位，清除当前痕迹；
					cost=cost-Arr[i][y[i]];
					greedcost[y[i]]=Max;
					y[i]=0;
					
					i--;					//返回上一层；
					j=y[i];
					i=Back(i,j,number);
					return i;
			}
	}	
		
}