matchz.h.h

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

#ifndef __MatchZ_H__
#define	__MatchZ_H__

#pragma warning(disable : 4800 4805 4244)

#include<blitz\array.h>
using namespace blitz;

class matrix
{
public:
	double cost[101][101];
    int zeroelem[101][101];
	double costforout[101][101];
	int matrixsize;
	int personnumber;		
	int jobnumber;
};

class Matchz
{
public:
	Array<int,1>	work(const Array<double,2>& weight, bool m = false);

	void			twozero();
	void			judge();
	void			refresh();
	void			circlezero();
	void			zeroout();

private:
	matrix			sb;
	int				result[501][2];
};

Array<int,1> Matchz::work(const Array<double,2>& weight, bool m)
{
	result[0][0]=0;
	int pnumber = weight.rows();
	int jnumber = weight.cols();
	int i,j;
	double k;

	for(i=1;i<=pnumber;i++)
		for(j=1;j<=jnumber;j++)
		{
			sb.cost[i][j] = weight(i-1, j-1);
			sb.costforout[i][j]=sb.cost[i][j];
		}

		if(jnumber>pnumber)
			for(i=pnumber+1;i<=jnumber;i++)
				for(j=1;j<=jnumber;j++)
				{
					sb.cost[i][j]=0;
					sb.costforout[i][j]=0;
				}
		else
		{
			if(pnumber>jnumber)
				for(i=1;i<=pnumber;i++)
					for(j=jnumber+1;j<=pnumber;j++)
					{
						sb.cost[i][j]=0;
						sb.costforout[i][j]=0;
					}

		}
		sb.matrixsize=pnumber;
		if(pnumber<jnumber)
			sb.matrixsize=jnumber;
		sb.personnumber=pnumber;
		sb.jobnumber=jnumber;
		if(m==1)
		{
			k=0;
			for(i=1;i<=sb.matrixsize;i++)
				for(j=1;j<=sb.matrixsize;j++)
					if(sb.cost[i][j]>k)
						k=sb.cost[i][j];
			for(i=1;i<=sb.matrixsize;i++)
				for(j=1;j<=sb.matrixsize;j++)
					sb.cost[i][j]=k-sb.cost[i][j];
		}

	zeroout();
	circlezero();

	Array<int,1> res(weight.rows());
	for(int i = 1; i <= weight.rows(); i++)
	{
		if(result[i][0]<=pnumber&&result[i][1]<=jnumber&&result[i][0]>0&&result[i][1]>0)
			res(result[i][0]-1) = result[i][1]-1;
	}
	return res;
}//input

void Matchz::circlezero()
{
	int i,j;
	double k;
	int p;
	for(i=0;i<=sb.matrixsize;i++)
		sb.cost[i][0]=0;
	for(j=1;j<=sb.matrixsize;j++)
		sb.cost[0][j]=0;
	for(i=1;i<=sb.matrixsize;i++)
		for(j=1;j<=sb.matrixsize;j++)
			if(sb.cost[i][j]==0)
			{
				sb.cost[i][0]++;
				sb.cost[0][j]++;
				sb.cost[0][0]++;
			}
	for(i=0;i<=sb.matrixsize;i++)
		for(j=0;j<=sb.matrixsize;j++)
			sb.zeroelem[i][j]=0;
	  
	k=sb.cost[0][0]+1;
	while(sb.cost[0][0]<k)
	{
		k=sb.cost[0][0];
		for(i=1;i<=sb.matrixsize;i++)
		{
			if(sb.cost[i][0]==1)
			{
				for(j=1;j<=sb.matrixsize;j++)
					if(sb.cost[i][j]==0&&sb.zeroelem[i][j]==0)
						break;
				sb.zeroelem[i][j]=1;
				sb.cost[i][0]--;
				sb.cost[0][j]--;
				sb.cost[0][0]--;
				if(sb.cost[0][j]>0)
					for(p=1;p<=sb.matrixsize;p++)
						if(sb.cost[p][j]==0&&sb.zeroelem[p][j]==0)
						{
							sb.zeroelem[p][j]=2;
							sb.cost[p][0]--;
							sb.cost[0][j]--;
							sb.cost[0][0]--;
						}
			}
		}
		for(j=1;j<=sb.matrixsize;j++)
		{
			if(sb.cost[0][j]==1)
			{
				for(i=1;i<=sb.matrixsize;i++)
					if(sb.cost[i][j]==0&&sb.zeroelem[i][j]==0)
						break;
				sb.zeroelem[i][j]=1;
				sb.cost[i][0]--;
				sb.cost[0][j]--;
				sb.cost[0][0]--;
				if(sb.cost[i][0]>0)
					for(p=1;p<=sb.matrixsize;p++)
						if(sb.cost[i][p]==0&&sb.zeroelem[i][p]==0)
						{
							sb.zeroelem[i][p]=2;
							sb.cost[i][0]--;
							sb.cost[0][p]--;
							sb.cost[0][0]--;
						}
			}
		}
	}//while
	if(sb.cost[0][0]>0)
		twozero();
	else
		judge();
}//circlezero


void Matchz::twozero()
{
	int i,j;
	int p,q;
	int m,n;
	double k;
    matrix st;
	for(i=1;i<=sb.matrixsize;i++)
		if(sb.cost[i][0]>0)
			break;
	if(i<=sb.matrixsize)
	{
		for(j=1;j<=sb.matrixsize;j++)
		{
			st=sb;//pay attention
			if(sb.cost[i][j]==0&&sb.zeroelem[i][j]==0)
			{
				sb.zeroelem[i][j]=1;
				sb.cost[i][0]--;
				sb.cost[0][j]--;
				sb.cost[0][0]--;
				for(q=1;q<=sb.matrixsize;q++)
					if(sb.cost[i][q]==0&&sb.zeroelem[i][q]==0)
					{
						sb.zeroelem[i][q]=2;
						sb.cost[i][0]--;
						sb.cost[0][q]--;
						sb.cost[0][0]--;
					}
				for(p=1;p<=sb.matrixsize;p++)
					if(sb.cost[p][j]==0&&sb.zeroelem[p][j]==0)
					{
						sb.zeroelem[p][j]=2;
						sb.cost[p][0]--;
						sb.cost[0][j]--;
						sb.cost[0][0]--;
					}

				k=sb.cost[0][0]+1;
				while(sb.cost[0][0]<k)
				{
					k=sb.cost[0][0];
					for(p=i+1;p<=sb.matrixsize;p++)
					{
						if(sb.cost[p][0]==1)
						{
							for(q=1;q<=sb.matrixsize;q++)
								if(sb.cost[p][q]==0&&sb.zeroelem[p][q]==0)
									break;
							sb.zeroelem[p][q]=1;
							sb.cost[p][0]--;
							sb.cost[0][q]--;
							sb.cost[0][0]--;
							for(m=1;m<=sb.matrixsize;m++)
								if(sb.cost[m][q]=0&&sb.zeroelem[m][q]==0)
								{
									sb.zeroelem[m][q]=2;
									sb.cost[m][0]--;
									sb.cost[0][q]--;
									sb.cost[0][0]--;
								}
						}//if
					}//for
					for(q=1;q<=sb.matrixsize;q++)
					{
						if(sb.cost[0][q]==1)
						{
							for(p=1;p<=sb.matrixsize;p++)
								if(sb.cost[p][q]==0&&sb.zeroelem[p][q]==0)
									break;
							sb.zeroelem[p][q]=1;
							sb.cost[p][q]--;
							sb.cost[0][q]--;
							sb.cost[0][0]--;
							for(n=1;n<=sb.matrixsize;n++)
								if(sb.cost[p][n]==0&&sb.zeroelem[p][n]==0)
								{
									sb.zeroelem[p][n]=2;
									sb.cost[p][0]--;
									sb.cost[0][n]--;
									sb.cost[0][0]--;
								}
						}//if
					}//for
				}//while
				if(sb.cost[0][0]>0)
					twozero();
				else 
					judge();
			}//if->p5	          
			sb=st;
		}//for->p5
	}//if->p5
}//twozero


void Matchz::judge()
{
	int i,j;
	int m;
	int n;
	int k;
	m=0;
	for(i=1;i<=sb.matrixsize;i++)
		for(j=1;j<=sb.matrixsize;j++)
			if(sb.zeroelem[i][j]==1)
				m++;
	if(m==sb.matrixsize)
	{
		k=1;
		for(n=1;n<=result[0][0];n++)
		{
			for(i=1;i<=sb.matrixsize;i++)
			{
				for(j=1;j<=sb.matrixsize;j++)
					if(sb.zeroelem[i][j]==1)
						break;
				if(i<=sb.personnumber&&j<=sb.jobnumber)
					if(j!=result[k][1])
						break;
				k++;
			}
			if(i==sb.matrixsize+1)
				break;
			else
				k=n*sb.matrixsize+1;
		}
		if(n>result[0][0])
		{
			k=result[0][0]*sb.matrixsize+1;
			for(i=1;i<=sb.matrixsize;i++)
				for(j=1;j<=sb.matrixsize;j++)
					if(sb.zeroelem[i][j]==1)
					{
						result[k][0]=i;
						result[k++][1]=j;
					}
			result[0][0]++;
		}
	}
	else
	{
		refresh();
	}
}//judge


void Matchz::refresh()
{
	int i,j;
	double k;
	int p;
	k=0;

	for(i=1;i<=sb.matrixsize;i++)
	{
		for(j=1;j<=sb.matrixsize;j++)
			if(sb.zeroelem[i][j]==1)
			{
				sb.zeroelem[i][0]=1;         //有独立零元素
				break;
			}
	}
	while(k==0)
	{
		k=1;
		for(i=1;i<=sb.matrixsize;i++)
			if(sb.zeroelem[i][0]==0)
			{
				sb.zeroelem[i][0]=2;
				for(j=1;j<=sb.matrixsize;j++)
					if(sb.zeroelem[i][j]==2)
					{
						sb.zeroelem[0][j]=1;
					}
			}
		for(j=1;j<=sb.matrixsize;j++)
		{
			if(sb.zeroelem[0][j]==1)
			{
				sb.zeroelem[0][j]=2;
				for(i=1;i<=sb.matrixsize;i++)
					if(sb.zeroelem[i][j]==1)
					{
						sb.zeroelem[i][0]=0;
						k=0;
					}
			}
		}
	}                    //为2的行或者列是打"√"的
	p=0;
	k=0;
	for(i=1;i<=sb.matrixsize;i++)
	{
		if(sb.zeroelem[i][0]==2)
		{
			for(j=1;j<=sb.matrixsize;j++)
			{
				if(sb.zeroelem[0][j]!=2)
					if(p==0)
					{
						k=sb.cost[i][j];
						p=1;
					}
					else
					{
						if(sb.cost[i][j]<k)
							k=sb.cost[i][j];
					}
			}
		}
	}
	for(i=1;i<=sb.matrixsize;i++)
	{
		if(sb.zeroelem[i][0]==2)
			for(j=1;j<=sb.matrixsize;j++)
				sb.cost[i][j]=sb.cost[i][j]-k;
	}

	for(j=1;j<=sb.matrixsize;j++)
	{
		if(sb.zeroelem[0][j]==2)
			for(i=1;i<=sb.matrixsize;i++)
				sb.cost[i][j]=sb.cost[i][j]+k;
	}                                 //化简矩阵
	for(i=0;i<=sb.matrixsize;i++)
		for(j=0;j<=sb.matrixsize;j++)
			sb.zeroelem[i][j]=0;              //清0
	circlezero();	
}//refresh


void Matchz::zeroout()
{
	int i,j; 
	double k;
	for(i=1;i<=sb.matrixsize;i++)
	{
		k=sb.cost[i][1];
		for(j=2;j<=sb.matrixsize;j++)
			if(sb.cost[i][j]<k)
				k=sb.cost[i][j];
		for(j=1;j<=sb.matrixsize;j++)
			sb.cost[i][j]=sb.cost[i][j]-k;
	}
	for(j=1;j<=sb.matrixsize;j++)
	{
		k=sb.cost[1][j];
		for(i=2;i<=sb.matrixsize;i++)
			if(sb.cost[i][j]<k)
				k=sb.cost[i][j];
		for(i=1;i<=sb.matrixsize;i++)
			sb.cost[i][j]=sb.cost[i][j]-k;
	}
}//zeroout

//void main()
//{
//	Array<double, 2> weight(4, 4);
//	weight = 0,0,0,1,
//		     1,0,0,0,
//			 0,1,0,0,
//			 0,0,1,0;
//	Match Match;
//	Array<int,1> result = Match.work(weight);
//	cout << weight << endl;
//	cout << result << endl;
//}//main

#endif	//	__MatchZ_H__