hungarymatch.h

用匈牙利算法解决二部图的最优匹配问题,可用于多任务的指派问题的解决.

#ifndef __HUNGARYMATCH_H__
#define	__HUNGARYMATCH_H__

//矩阵类
#define MAX 20

class MyMatrix
{
public:
	double Cost[MAX][MAX];
	double TempCost[MAX][MAX];
	int	   Size;
	bool   Mark[MAX][MAX];
};

class HungaryMatch
{
public:
	HungaryMatch(int m, int n, double maxcost = 50000, bool IsMaxMatch = FALSE);	

	void			judge();
	void			circlezero();
	void			zeroout();
	void			match();
	void			InitM();

	int RNumber;
	int CNumber;
	bool MaxOrMin;
	MyMatrix sb;
	int Result[MAX];
	double MaxCost;
	bool Crc;
	int count;
};
HungaryMatch::HungaryMatch(int m, int n, double maxcost /* = 5000 */, bool IsMaxMatch /* = FALSE */)
{   
count = 0;

	Crc = false; 
	RNumber = m; 
	CNumber = n; 
	MaxOrMin = IsMaxMatch;
	MaxCost = maxcost;

	int maxsize = RNumber>CNumber?RNumber:CNumber;

	sb.Size = maxsize;

	int i = 0;
	

	//Init Result
	for(i = 1; i <= maxsize; i++)
	{
		Result[i] = -1;
	}

	
	
}
void HungaryMatch::InitM()
{	
	//Init m~n
	int i, j;
	double SaveValue[MAX][MAX];
	if(RNumber > CNumber)
	{
		for(i = 1; i <= RNumber; i++)
		{
			for(j = CNumber+1; j <= RNumber; j++)
			{
				sb.Cost[i][j] = MaxCost;
			}
		}
		for(i = 1; i <= RNumber; i++)
		{
			for(j = 1; j <= RNumber; j++)
			{
				SaveValue[i][j] = sb.Cost[j][i];
				Crc = true;
			}
		}
		for(i = 1; i <= RNumber; i++)
		{
			for(j = 1; j <= RNumber; j++)
			{
				sb.Cost[i][j] = SaveValue[i][j] ;
			}
		}

	}
	else if(RNumber < CNumber)
	{
		for(i = RNumber+1; i <= CNumber; i++)
		{
			for(j = 1; j <= CNumber; j++)
			{
				sb.Cost[i][j] = MaxCost;
			}
		}
	}

	/************************************************************************/
	/*                       得到最大匹配的等价矩阵                         */
	/************************************************************************/
	double k;
	if(MaxOrMin)
	{
		k=0;
		for(i = 1;i <= sb.Size; i++)
		{
			for(j = 1;j <= sb.Size; j++)
			{
				if(sb.Cost[i][j] > k)
				{
					k = sb.Cost[i][j];
				}
			}
		}
		for(i = 1;i <= sb.Size; i++)
		{
			for(j = 1;j <= sb.Size; j++)
			{
				sb.Cost[i][j] = k - sb.Cost[i][j];
			}
		}
	}
}
void HungaryMatch::zeroout()
{
	int i,j; 
	double k;
	for(i = 1;i <= sb.Size; i++)
	{
		k = sb.Cost[i][1];
		for(j=2;j <= sb.Size; j++)
		{
			if(sb.Cost[i][j] < k)
			{
				k = sb.Cost[i][j];
			}
		}
		for(j = 1;j <= sb.Size; j++)
		{
			sb.Cost[i][j] = sb.Cost[i][j] - k;
		}
	}
	for(j = 1;j <= sb.Size; j++)
	{
		k=sb.Cost[1][j];
		for(i = 2;i <= sb.Size; i++)
		{
			if(sb.Cost[i][j] < k)
			{
				k = sb.Cost[i][j];
			}
		}
		for(i = 1;i <= sb.Size; i++)
		{
			sb.Cost[i][j] = sb.Cost[i][j] - k;
		}
	}
}//zeroout

void HungaryMatch::circlezero()
{
	int i,j;
	double k;
	double step = sb.Size;
	bool isCircle = true;

	////////////////////////////////////////////////////////标记初始化
	for(i = 0;i <= sb.Size; i++)
	{
		for(j = 0;j <= sb.Size; j++)
		{
			sb.Mark[i][j] = false;
			sb.TempCost[i][j] = sb.Cost[i][j];
		}
	}


	double zeroMin;
	int tag = -1 ;
	bool rowOrcol = true;//行（row）为1

	sb.Cost[0][0] = 0;

	for(i = 1;i <= sb.Size; i++)
	{
		for(j = 1;j <= sb.Size; j++)
		{
			if(sb.Cost[i][j]==0)
			{
				sb.Cost[0][0]++;
			}
		}
	}
	k = sb.Cost[0][0];


	
	while((k-sb.Cost[0][0]) < sb.Size && step > 0 )
	{
		for(i = 0;i <= sb.Size; i++)	sb.TempCost[i][0]=0;
		for(j = 1;j <= sb.Size; j++)	sb.TempCost[0][j]=0;

		for(i = 1; i <= sb.Size; i++)
		{
			for(j=1; j <= sb.Size; j++)
			{
				if(sb.TempCost[i][j]==0)
				{
					sb.TempCost[i][0]++;
					sb.TempCost[0][j]++;
				}
			}
		}

		isCircle = false;
		zeroMin  = MaxCost + 1;
//////////////////////////////////////////先找每行中零最少的
		for(i=1;i<=sb.Size;i++)
		{
			if(sb.TempCost[i][0] < zeroMin && !sb.Mark[i][0] && sb.TempCost[i][0] != 0)
			{
				zeroMin = sb.TempCost[i][0];
				rowOrcol = true;
				tag = i;
			}
		}

		//////////////////////////////////////////先找每列中零最少的
		for(j = 1; j <= sb.Size; j++)
		{
			if(sb.TempCost[0][j]  < zeroMin && !sb.Mark[0][j] && sb.TempCost[0][j] != 0 )
			{
				zeroMin = sb.TempCost[0][j];
				tag = j;
				rowOrcol = false;
			}
		}

		//////////////////////////////////////////将找到的这一行或列画线并作标记
		if(tag < 0)
		{
			for(i = 1;i <= sb.Size; i++)
			{
				for(j = 1;j <= sb.Size; j++)
				{
					sb.Cost[i][j] = 0;
					sb.TempCost[i][j] = 0;
				}
			}
		}
		else
		{
			int testttt = 0;
			if(rowOrcol)
			{
				for(j = 1; j <= sb.Size; j++)
				{
					if(sb.TempCost[tag][j] == 0 /*&& !sb.mark[tag][0] && !sb.mark[0][j] && sb.costzhb[0][j] != 0*/ )
					{
						Result[tag] = j;
						sb.Mark[tag][j] = true;	//标记行中最小零数的零点；
						sb.Mark[0][j] = true;	//对该点所在的列进行画线
						sb.Cost[0][0]--;       //零元素减一


						for(int c = 1; c <= sb.Size; c++)
						{
							if(sb.TempCost[tag][c] == 0)
							{
								sb.TempCost[tag][c]++;
							}
						}                    //同时将该行中其他为零的元素也加一以排除参加下次圈零
						for(int r = 1; r <= sb.Size; r++)
						{
							if(sb.TempCost[r][j] == 0)
							{
								sb.TempCost[r][j]++;
							}
						}                      //将该列中其他元素为零的也加一
						break;
					}
				}
			}
			else
			{
				for(i = 1; i <= sb.Size; i++)
				{
					if(sb.TempCost[i][tag] == 0 /*&& sb.mark[i][0] && !sb.mark[0][tag] && sb.costzhb[i][0] != 0*/)
					{
						Result[i] = tag;
						sb.Mark[i][tag] = true;	//标记列中最小零数的零点
						sb.Mark[i][0] = true;	//对该点所在的行进行画线
						sb.Cost[0][0]--;

						for(int c = 1; c <= sb.Size; c++)
						{
							if(sb.TempCost[i][c] == 0)
								sb.TempCost[i][c]++;
						}
						for(int r = 1; r <= sb.Size; r++)
						{
							if(sb.TempCost[r][tag] == 0)
								sb.TempCost[r][tag]++;
						}
						break;
					}
				}
			}
			for(i = 1;i <= sb.Size; i++)
			{
				for(j=1;j<= sb.Size; j++)
				{
					if(!sb.Mark[i][0] && !sb.Mark[0][j] && sb.Cost[i][j] == 0)
					{
						isCircle = true;
						break;
					}
				}
				if(isCircle) break;
			}

		}
		step--;
	}
	if((k - sb.Cost[0][0]) < sb.Size )
	{
		if(!isCircle)
		{
			judge();
		}
		else
		{
			for(i = 1;i <= sb.Size; i++)
			{
				for(j = 1;j <= sb.Size; j++)
				{
					if(!sb.Mark[i][0] && !sb.Mark[0][j] && sb.Cost[i][j] == 0)
						sb.Cost[i][j]+= 0.01;
				}
			}
			judge();
		}
	}
}

void HungaryMatch::judge()
{
count++;

	int i,j;
	double numMin = MaxCost + 1;

	for(i = 1; i <= sb.Size; i++)
	{
		for(j = 1;j <= sb.Size; j++)
		{
			if(!sb.Mark[i][0] && !sb.Mark[0][j] && sb.Cost[i][j] < numMin)
			{
				numMin = sb.Cost[i][j];
			}
		}
	}
	for(i = 1; i <= sb.Size; i++)
	{
		for(j = 1;j <= sb.Size;j++)
		{
			if(!sb.Mark[i][0] && !sb.Mark[0][j])
			{
				sb.Cost[i][j] = sb.Cost[i][j] - numMin;
			}
		}
	}

	for(i = 1; i <= sb.Size; i++)
	{
		for(j = 1;j <= sb.Size;j++)
		{
			if(sb.Mark[i][0] && sb.Mark[0][j])
			{
				sb.Cost[i][j] = sb.Cost[i][j] + numMin ;
			}
		}
	}

	zeroout();
	circlezero();
}
void HungaryMatch::match()
{   int temp[MAX];
	int i, j;
	InitM();
	zeroout();
	circlezero();
	if(Crc)
	{
		for(i = 1; i <= sb.Size; i++)
		{
			for(j = 1; j <=sb.Size; j++)
				if(j == Result[i])
				{
					temp[j] = i;
				}
		}
		for(i = 1; i <= sb.Size; i++)
		{
			Result[i] = temp[i];
		}
	}

}

#endif