main.cpp

任务分配最小耗散路径选择算法

#include <string>
#include <fstream>
#include <iostream>
using namespace std;
#define N 7
#define Max 65536
typedef struct select{
	int i;
	int j;
	int w;
}select;
int n;

void cpy_array(int a[][N],int b[][N])
{
	int i2,j2;
	for(i2=0;i2!=N;i2++)
	{
		for(j2=0;j2!=N;j2++)
		{
			b[i2][j2]=a[i2][j2];
		}
	}
}
int zerolize(int cost[][N])
{
	int i2,j2;
	int mr,mc,m;
	m=0;
	for(i2=0;i2!=N;i2++)
	{
			mc=mr=Max;
			for(j2=0;j2!=N;j2++)
			{				
					if(cost[i2][j2]<mr)
					mr=cost[i2][j2];
					if(cost[j2][i2]<mc)
					mc=cost[j2][i2];
			}
			if(mr!=0&&mr!=Max){	
				for(j2=0;j2!=N;j2++)
				{
					if(cost[i2][j2]==Max)
						continue;
					cost[i2][j2]-=mr;		
				}
				m+=mr;
			}
			if(mc!=0&&mc!=Max){				
				for(j2=0;j2!=N;j2++)
				{
					if(cost[j2][i2]==Max) continue;
					cost[j2][i2]-=mc;				
				}
				m+=mc;
			}
	}
	return m;
}
select sel_item(int cost[N][N])
{
	select item;
	item.i=-1;
	item.j=-1;
	item.w=0;	
	int i,j,i1,j1;
	int mc,mr,m;
	for(i=0;i!=N;i++)
	{
		for(j=0;j!=N;j++)
		{
			if(cost[i][j]==0)
			{
				mc=mr=Max;
				for(i1=0;i1!=N;i1++)
				{
					if(i1==i)
						continue;
					if(cost[i1][j]<mc)
						mc=cost[i1][j];
				}
				for(j1=0;j1!=N;j1++)
				{
					if(j1==j)
						continue;
					if(cost[i][j1]<mr)
						mr=cost[i][j1];
				}
				m=mr+mc;
				if(m>item.w)
				{
					item.w=m;
					item.i=i;
					item.j=j;
				}
				}
		}
	}
	return item;
}
void mdy_left(int cost[][N],select item)
{
	
	cost[item.j][item.i]=Max;
	for(int i2=0;i2!=N;i2++)
	{
		cost[i2][item.j]=Max;
		cost[item.i][i2]=Max;
	}
}
void tree(int rm,int lb,int cost[N][N])
{
	select item;
	lb=lb+zerolize(cost);
	cout<<"代价下界为"<<lb<<"\n";
	if(rm==0)
	{
		cout<<"扩展完了"<<endl;
		return;
	}
	if(lb>126)
	{
		cout<<"代价太大，不扩展了"<<endl;
		return;
	}
	item=sel_item(cost);
	if(item.i==-1||item.j==-1||item.w==0)return;
	cout<<"左子树包括"<<item.i+1<<","<<item.j+1;
	int new_cost_l[N][N];
	cpy_array(cost,new_cost_l);	
	int new_cost_r[N][N];
	cpy_array(cost,new_cost_r);
	mdy_left(new_cost_l,item);
	tree(rm-1,lb,new_cost_l);
	if(rm==1)return;
	cout<<"右子树不包括"<<item.i+1<<","<<item.j+1;
	new_cost_r[item.i][item.j]=Max;
	int tmp=zerolize(new_cost_r);
	if(tmp==0)
	{
		cout<<"不存在"<<endl;
		return;
	}
	lb=lb+tmp;
	tree(rm,lb,new_cost_r);
}
void main()
{
	ifstream s("a.txt");
	int cost[N][N],r,i,j;
	for( i=0;i!=N;i++)
		for( j=0;j!=N;j++)
		{
			s>>r;
			cost[i][j]=r;
		}
	s.close();
	freopen( "out.txt", "w", stdout );
	tree(7,96,cost);
	freopen( "CON", "w", stdout ); 
}
/*void main()
{
	ifstream s("a.txt");
	int cost[N][N],r,m,mr,mc,i,j,i1,j1,i2,j2;
	for( i=0;i!=N;i++)
		for( j=0;j!=N;j++)
		{
			s>>r;
			cost[i][j]=r;
		}
	s.close();
	select item;
	int wi=117;
	for(int x=0;x<N;x++)
	{
		item.i=-1;
		item.j=-1;
		item.w=0;		
		for(i=0;i<N;i++)
		{
			for(j=0;j<N;j++)
			{
				if(cost[i][j]==0)
				{
					mc=mr=Max;
					for(i1=0;i1<N;i1++)
					{
						if(i1==i)
							continue;
						if(cost[i1][j]<mc)
							mc=cost[i1][j];
					}
					for(j1=0;j1<N;j1++)
					{
						if(j1==j)
							continue;
						if(cost[i][j1]<mr)
							mr=cost[i][j1];
					}
					m=mr+mc;
					if(m>item.w)
					{
						item.w=m;
						item.i=i;
						item.j=j;
					}

				}
			}
		}
		//right sub_tree
		cout<<"右子树，不包含("<<item.i+1<<","<<item.j+1<<")代价下界为"<<item.w+wi<<endl;
		cost[item.j][item.i]=Max;
		item.w=0;
		for(i2=0;i2<N;i2++)
		{
			cost[i2][item.j]=Max;
			cost[item.i][i2]=Max;
		}
		for(i2=0;i2<N;i2++)
		{
			mc=mr=Max;
			for(j2=0;j2<N;j2++)
			{				
					if(cost[i2][j2]<mr)
					mr=cost[i2][j2];
					if(cost[j2][i2]<mc)
					mc=cost[j2][i2];
			}
			if(mr!=0&&mr!=Max){	
				for(j2=0;j2<N;j2++)
				{
					if(cost[i2][j2]==Max)
						continue;
					cost[i2][j2]-=mr;		
				}
				item.w+=mr;
			}
			if(mc!=0&&mc!=Max){				
				for(j2=0;j2<N;j2++)
				{
					if(cost[j2][i2]==Max) continue;
					cost[j2][i2]-=mc;				
				}
				item.w+=mc;
			}
		}
		cout<<"左子树包含("<<item.i+1<<","<<item.j+1<<")"<<"代价下界为"<<item.w+wi<<endl;
		for(i=0;i<N;i++)
		{
			for (j=0;j<N;j++)
			{
				cout<<cost[i][j]<<" ";
			}
			cout<<endl;
		}
		wi+=item.w;
	}
}*/