任意规模指派问题的C++类实现

一．指派问题

在生活中经常遇见这样的问题，有n项任务要求n个人完成，这n个人完成各项任务的效率（或所需时间）不同，于是产生指派哪个人去完成哪项任务的问题，这类问题称为指派问题或分派问题。

1．指派问题的数学模型

引入变量Xij，其取值只能是1或0，并令Xij=1表示指派第i人完成第j项任务  Xij=0表示不指派第i人完成第j项任务；当问题要求极小化时，数学模型是：                                                                                                     Min z=         ①    

 

 ② ③

  ④

约束条件②说明第j项任务只能由1人完成；约束条件③说明第i人只能完成1项任务。满足约束条件②--④的解，可以用矩阵来表示，此矩阵称为解矩阵。

当问题要求极大化时，可令bij=M-Cij把问题转换成极小化模型。

二．指派问题的解法

指派问题是0-1规划的特例，也是运输问题的特例，可以用整数规划、0-1规划、运输问题的解法去求解，但因忽略指派问题的特殊性，因而不能达到好的解题效率。

指派问题的最优解具有这样的性质，若从系数矩阵（bij）的一行（列）各元素中分别减去该行（列）的最小元素，得到新矩阵（bij’），那么以（bij’）为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。

库恩于1955年提出了指派问题的解法，其中引用了康尼格一个关于矩阵中0元素的定理：系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。

三．程序实现

依照上述方法，编制Assignment类，以实现对任意规模的指派问题的解决。

class Assignment

{

public:

    Assignment(int n, int * eff);

    ~Assignment();

    int * getAssignment(bool isMin=true);

 

private:

    bool hasAssigned(int * eff);

    bool hasZero(int * eff);

    void changeMinToMax();

    void getRowColZero(int * eff);

    void assignAndGetoff(int * eff);

    void changeEfficiency(int * eff);

    void getTaskAssignment(int * eff);

    void assignCore(int * eff);

    void resetZero (int * eff);

    int  getLineNum(int *eff);

   

private:

    bool   allAssigned;

    int *  task;

    int *  efficiency;

    int    scale;

    int *   rowTicked;

    int *  colTicked;

 

public:           // 定义的几个常数

    const int  MAXVALUE ;

    const bool MAXASSIGN;

    const bool MINASSIGN;

    const int  ASSIGNED ;

    const int  GETOFFED ;

};

 

Assignment类说明

1.Assignment类实现任务指派；

2.使用示例

       Assignment assignment = Assignment(n, eff);

       int * Task = assignment.getTaskAssignment(isMin);

       其中，n表示指派任务个数；

       eff   效率系数，以一维数组传递；

       isMin      是否取最小代价指派；isMin=true时，表示为最小代价指派，缺省情况下，isMin=true；

       Task       指派结果，若Task[i]=j, 表示第i个人完成第j项任务(以0为第一序数)；

3.应用举例：

int main()

{

       int scale, *eff,  * task;

       int i, j;

 

       // Get Scale

       cout<<"\nThe Scale Of Problem: ";

       cin>>scale;

       // Construct eff

       eff = new int[scale*scale];

       // Get Efficiency

       for(i=0; i<scale; i++)

              for(j=0; j<scale; j++)

              {

                     cout<<"\nThe Efficiency Of The "<<i+1<<"th Person Doing The "

                            <<j+1<<"th Task Is (Natural Number): ";

                     cin>>eff[i*scale+j];

              }

       // Get minormax

       bool isMin= true;

       char isY;

       cout<<"\nIs a min cost assignment ?(Y for yes, & others for no): ";

       cin>>isY;

       isMin= (isY=='Y' || isY=='y');

 

       // List the Efficiency

       cout<<"\n" <<"The Effienciency:";

       for(i=0; i<scale; i++)

       {

              cout<<"\nThe " <<i+1 <<"th person: ";

              for(j=0; j<scale; j++)

                     cout<<eff[i*scale+j] <<" ";

       }

       // Assignment Type

       if (isMin)

              cout<<"\n\nMin Cost Assignment.\n";

       else

              cout<<"\n\nMax Effect Assignment.\n";

 

       Assignment assignment = Assignment(scale, (int *)eff);

       task = assignment.getAssignment(isMin);

 

       // Output the result

       for(i=0; i<scale; i++)

              cout<<"\nThe " <<i+1 <<"th person do the " <<task[i]+1 <<"th task;" ;

       cout<<"\n";

 

       return 0;

}

按照提示输入问题规模、相应的效率矩阵、求解方式（最大效率或最小代价）后程序就可以输出结果。

以下是assignment.cpp的内容,assignment.h的内容即类的定义部分.

#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;
}

void Assignment::getRowColZero(int * eff)
{
 int i,j  , min;
 // Zero in Row
 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;
 }
 
 // Zero in Col
 for(j=0; j<scale; j++)
 {
  min = MAXVALUE;   // Get Min
  for(i=0; i<scale; i++)
   if (eff[i*scale+j] < min)
    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;
  
  // From row which has only one zero
  for(i=0; i<scale; i++)
  {
   rowZero = 0;
   for(j=0; j<scale; j++)
    if (eff[i*scale+j] == 0)
    {
     rowZero++;
     zeroPos = j;    // Write down the col number
    }
   // 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
  
  // Column process
  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;
}

/*void Assignment::assignWithStart(int * eff, int row, int col)
{
 int i,j;

 if (allAssigned)
  return;
  
 if (hasZero(eff))
 {
  for(i=0; i<scale; i++)
  {
   if (allAssigned) 
    return;
   for(j=0; j<scale; j++)
   {
    if (allAssigned)
     return;
    if (eff[i*scale+j]==0)
    {
     int * tempEff = new int[scale*scale];
     int k,m;
     for(k=0; k<scale; k++)
      for(m=0; m<scale; m++)
       tempEff[k*scale+m] = eff[k*scale+m];
       
     tempEff[row*scale+col] = ASSIGNED;
     for(k=0; k<scale; k++)   
      if (tempEff[k*scale+col]==0)
       tempEff[k*scale+col] = GETOFFED;
     for(k=0; k<scale; k++)
      if (tempEff[row*scale+k]==0)
       tempEff[row*scale+k] = GETOFFED;

     // Get new row, col Start
     for(k=0; k<scale; k++)
      for(m=0; m<scale; m++)
       if (tempEff[k*scale+m]==0)
        assignWithStart(tempEff, k, m);
     
     delete [] tempEff;
    }    // End if
   }
  }
 }
 else      // No zero
 {
  while (getLineNum(eff) < scale)
  {
   changeEfficiency(eff);
   if (hasAssigned(eff)) break;
  }
  if (hasAssigned(eff))
  {
   allAssigned = true;
   getTaskAssignment(eff);
   return;
  }
 }       // End else
}*/

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;
}

本文地址：http://com.8s8s.com/it/it1420.htm