assignment.cpp

自己作的指派问题 不好意思 主要用于运筹学的指派问题

#include "assignment.h"
//构造函数
Assignment::Assignment(int n, int * eff):
 MAXVALUE(65532), MAXASSIGN(false), MINASSIGN(true),
 ASSIGNED(-1), GETOFFED(-2)
{
 scale = n;
 efficiency = new int[scale*scale];
 
 for(int i=0; i<scale; i++)
  for(int j=0; j<scale; j++)
   efficiency[i*scale+j] = eff[i*scale+j];

 rowTicked = new int[scale];
 colTicked = new int[scale];
 task    = new int[scale];
}
 //析构函数
Assignment::~Assignment()
{ 
 delete [] efficiency;
 delete [] rowTicked; 
 delete [] colTicked; 
 delete [] task; 
}
//判断是否为最小效率函数
int * Assignment::getAssignment(bool isMin)
{
	if (!isMin)
		changeMinToMax();//转变为最大效率函数


    allAssigned = false;

		getRowColZero(efficiency);//第一步
		assignAndGetoff(efficiency);//第二步

		assignCore(efficiency);

		return task;    // Task is set by assignCore()
}
////////////////////////////////////////////////////////////////////////////////
     //将最小效率转换为最大效率
void Assignment::changeMinToMax()
{
 int max = 0,  i,j;
 // Get Max
 //获取每一行的最大值
 for(i=0; i<scale; i++)
  for(j=0; j<scale; j++)
   if (efficiency[i*scale+j] > max)
    max = efficiency[i*scale+j];
 // Change
   //从系数矩阵的每行元素减去该列的最小元素
 for(i=0; i<scale; i++)
  for(j=0; j<scale; j++)
   efficiency[i*scale+j] -= max;
}
//////////////////////////////////////////////////////////////////////////
      /*第一步:使指派问题的系数矩阵经过变换,在各行各列中都出现0元素*/
void Assignment::getRowColZero(int * eff)
{
 int i,j  , min;                           //i是行，J是列
//从系数矩阵的每行元素减去该行的最小元素 
 for(i=0; i<scale; i++)
 {
	min = MAXVALUE;   // Get Min
	for(j=0; j<scale; j++)
  {
	  if (eff[i*scale+j] < min)
		min = eff[i*scale+j];
  }
	if (min==0) continue;
  
	for(j=0; j<scale; j++)
	{
		eff[i*scale+j] -= min;
	}
 }
 //再从所得的系数矩阵的每列元素减去该列的最小元素
 for(j=0; j<scale; j++)
 {
	min = MAXVALUE;   // Get Min
	for(i=0; i<scale; i++)
	{
		if (eff[i*scale+j] < min)                 //主体意思是说只要行或列中有0这个值
		min = eff[i*scale+j];
    }
	if (min ==0) continue;
  
	for(i=0; i<scale; i++)
	eff[i*scale+j] -= min;
 }
}
//////////////////////////////////////////////////////////////////////////////
      /*第二步:进行试指派以寻求最优解*/
void Assignment::assignAndGetoff(int * eff)   
{
 int i,j,k, rowZero, colZero, zeroPos;
 bool isOver = false;
 
 while (!isOver)    
 {
	isOver = true;
  //从只有一个零元素的行开始,给这个0元素加圈,划去圈所在列的其他0元素
	for(i=0; i<scale; i++)
	{
		rowZero = 0;
		for(j=0; j<scale; j++)
			if (eff[i*scale+j] == 0)
				{
					rowZero++;
					zeroPos = j;    //记下列号
				}
   // Only one zero in row
		if (rowZero == 1)
		{
			isOver = false;
			eff[i*scale+zeroPos] = ASSIGNED;
				for(k=0; k<scale; k++)   // Zero in the column maked by GETOFFED 
					if (eff[k*scale+zeroPos]==0)
						eff[k*scale+zeroPos] = GETOFFED;
		}
	}    // End for____Row
  //从只有一个零元素的行开始,给这个0元素加圈,划去圈所在列的其他0元素
	for(j=0; j<scale; j++)
	{
		colZero = 0;
		for(i=0; i<scale; i++)
			if (eff[i*scale+j]==0)
			{
				colZero++;
				zeroPos  = i;   // Write down the row number
			}
			if (colZero==1)
			{
				isOver = true;
				eff[zeroPos*scale+j] = ASSIGNED;
				for(k=0; k<scale; k++)
						if (eff[zeroPos*scale+k]==0)
							eff[zeroPos*scale+k] = GETOFFED;
			}   // End If
	}    // End for____Column
 }     // End while
 return;
}//end int
int Assignment::getLineNum(int * eff)
{
	int i,j,  lineNum=0;
	bool hasMore = true;
 
 // Initiate rowTicked & colTicked
	for(i=0; i<scale; i++)
		rowTicked[i] = colTicked[i] = 0;
	

 // Get rows that has no ASSIGNED
	for(i=0; i<scale; i++)
	{
		rowTicked[i] = 1;
		for(j=0; j<scale; j++)
			if (eff[i*scale+j]==ASSIGNED)
			{
				rowTicked[i] = 0;
				break;
			}
	}

	int time=0;
		while ( (hasMore)&& (time++<scale) )
		{
			hasMore = false;

  // Column  
			for(i=0; i<scale; i++)
				if (rowTicked[i]==1)
					for(j=0; j<scale; j++)
						if ( (eff[i*scale+j]==ASSIGNED) ||(eff[i*scale+j]==GETOFFED)   )
						{
							colTicked[j] = 1;
							hasMore = true;
							break;
						}
  // Row
			for(j=0; j<scale; j++)
				if (colTicked[j])
					for(i=0; i<scale; i++)
						if (eff[i*scale+j]==ASSIGNED)
						{
							rowTicked[i] = 1;
							hasMore = true;
							break;
						}
		}    // End while

		for(i=0; i<scale; i++)
		{
			if (rowTicked[i]==0)
				lineNum++;
			if (colTicked[j]==1)
				lineNum++;
		}

		return lineNum;
	}

void Assignment::changeEfficiency(int * eff)
{
 int i,j,  minValue = MAXVALUE;
 // Get minValue in where lines donot cover
 for(i=0; i<scale; i++)
 {
  if (rowTicked[i]==0) continue;

  for(j=0; j<scale; j++)
  {
   if (colTicked[j]==1) continue;
   if (eff[i*scale+j] < minValue)
    minValue = eff[i*scale+j];
  }
 }

 // To get more zero
 for(i=0; i<scale; i++)
  if (rowTicked[i]==1)
   for(j=0; j<scale; j++)
    eff[i*scale+j] -= minValue;

 for(j=0; j<scale; j++)
  if (colTicked[j]==1)
   for(i=0; i<scale; i++)
    eff[i*scale+j] += minValue;
}

void Assignment::getTaskAssignment(int * eff)
{
 for(int i=0; i<scale; i++)
  for(int j=0; j<scale; j++)
   if (eff[i*scale+j]==ASSIGNED)
   {
    task[i] = j;    // Person i do the task j
    break;
   }
}

bool Assignment::hasZero(int * eff)
{
 for(int i=0; i<scale; i++)
  for(int j=0; j<scale; j++)
   if (eff[i*scale+j]==0) return true;

 return false;
}

bool Assignment::hasAssigned(int * eff)
{
 int i, j;
 for(i=0; i<scale; i++)
 {
  for(j=0; j<scale; j++)
   if (eff[i*scale+j]==ASSIGNED)
    break;
  if (j==scale) return false;
 }

 return true;
}

void Assignment::assignCore(int * eff)
{
 if (hasAssigned(eff))
 {
  getTaskAssignment(eff);
  allAssigned = true;
  return;
 }
 else
 {
  // Zero not Assigned ?
  if (hasZero(eff))
  { 
   // Not All Assigned & has Zero
   for(int i=0; i<scale; i++)
   { 
    if (allAssigned) break;
    for(int j=0; j<scale; j++)
    {
     if (allAssigned) break;  
     // Get the first zero, for getting the best zero is so difficult.
     if (eff[i*scale+j]==0)
     {
      int m;
      int * tempEff = new int [scale*scale];
      // Keep the copy
      for(m=0; m<scale*scale; m++)
       tempEff[m] = eff[m];
      tempEff[i*scale + j] = ASSIGNED; // Marked as Assigned
      for(m=0; m<scale; m++)
      {
       // Marked Zero in the same col As GETOFFED
       if (tempEff[m*scale + j]==0) tempEff[m*scale+j] = GETOFFED;
       // Marked Zero in the same row As GETOFFED
       if (tempEff[i*scale + m]==0) tempEff[i*scale+m] = GETOFFED;
      }      // End for___m

      //if (! allAssigned)
       assignCore(tempEff); // Nested Call

      delete [] tempEff;
     }
    }  // End for___j
   }   // End for___i(To get rid of Dependent Zero
  }    // End if____(hasZero(eff))

  // Not All Assigned & has No Zero
  else
  {
   if (getLineNum(eff)<scale)  // l<n
   {

    changeEfficiency(eff);  // Change Efficiency Matrix
    resetZero(eff);
    getRowColZero(eff);
    assignAndGetoff(eff);
    assignCore(eff);
   }
   else       // l=n
    return;
  }
 }          // End else

 return;
}

void Assignment::resetZero(int * eff)
{
 for(int i=0; i<scale*scale; i++)
  if ((eff[i]==ASSIGNED)||(eff[i]==GETOFFED))
    eff[i]=0;
}