fenzhi.cpp

这是一个利用分治法求最短回路的算法

#include <stdio.h>
#include <iostream.h>
#include <time.h>
#include <malloc.h>
#include <stdlib.h>
#include <math.h> 


#define JIEDIAN 40
#define MAX 100000

//int Result[JIEDIAN/4];
double roadmin;
int temp[JIEDIAN/4];
int temp1[JIEDIAN/4];


typedef struct
{
	double g[JIEDIAN/4][JIEDIAN/4];
}Juzhen;


typedef struct
{
	int x,y;
}Point;

typedef struct
{
	Point g[JIEDIAN];
	int advx,adv_y1,adv_y2;
}Graph;

typedef struct
{
	int PartI[JIEDIAN/4];
	int PartII[JIEDIAN/4];
	int PartIII[JIEDIAN/4];
	int PartIV[JIEDIAN/4];
	
	int RpartI[JIEDIAN/4];
	int RpartII[JIEDIAN/4];
	int RpartIII[JIEDIAN/4];
	int RpartIV[JIEDIAN/4];
}Part;

int random(int low,int high,int seed=0)

{
	srand(seed+(unsigned)time(NULL));                        
    int i=rand()%high+low;
	return i;
}


int Getadvx(Graph *gra)
{
	int count;
	for(int i=0;i<JIEDIAN;i++)
	{
		count=0;
		for(int j=0;j<JIEDIAN;j++)
			if(gra->g[i].x<gra->g[j].x)count++;
		//	cout<<count<<",";
			if(count==JIEDIAN/2)
			{
			//	cout<<"x="<<count<<endl;
				return gra->g[i].x;
			}
	
	}
	return 0;
}

int Getadv_y1(Graph *gra,int advx)
{
	int count;
	for(int i=0;i<JIEDIAN;i++)
	{
		if(gra->g[i].x<=advx)
		{
			count=0;
			for(int j=0;j<JIEDIAN;j++)
				if(gra->g[j].x<=advx&&gra->g[i].y<gra->g[j].y)count++;
				if(count==JIEDIAN/4)
				{
			//		cout<<"y1="<<count<<endl;
					return gra->g[i].y;
				}
			
		}

	}
    return 0;
}

int Getadv_y2(Graph *gra,int advx)
{
	int count;
	for(int i=0;i<JIEDIAN;i++)
	{
		if(gra->g[i].x>advx)
		{
			count=0;
			for(int j=0;j<JIEDIAN;j++)
				if(gra->g[j].x>advx&&gra->g[i].y<gra->g[j].y)count++;
				if(count==JIEDIAN/4)
				{
			//		cout<<"y2="<<count<<endl;
					return gra->g[i].y;
				}

		}
	}
    return 0;
}



Graph *init()
{
	Graph *gra=new Graph;
	for(int i=0;i<JIEDIAN;i++)
	{
		gra->g[i].x=random(1,100,i-rand());
		gra->g[i].y=random(1,100,i+rand());
	}
	gra->advx=Getadvx(gra);
	gra->adv_y1=Getadv_y1(gra,gra->advx);
	gra->adv_y2=Getadv_y2(gra,gra->advx);

    
	
	for(i=1;i<=JIEDIAN;i++)
	{
		cout<<gra->g[i-1].x<<","<<gra->g[i-1].y<<" ";
		if(i%10==0)
			cout<<endl;
	}
	cout<<"advx="<<gra->advx<<","<<"adv_y1="<<gra->adv_y1<<","<<"gra->adv_y2="<<gra->adv_y2<<endl;	

	return gra;
}


void Divide(Part *part,Graph *gra)
{
	int top1=0,top2=0,top3=0,top4=0;
	for(int i=0;i<JIEDIAN;i++)
	{
		if(gra->g[i].x<=gra->advx&&gra->g[i].y<=gra->adv_y1)part->PartI[top1++]=i;
		if(gra->g[i].x>gra->advx&&gra->g[i].y<=gra->adv_y2)part->PartII[top2++]=i;
		if(gra->g[i].x<=gra->advx&&gra->g[i].y>gra->adv_y1)part->PartIII[top3++]=i;
	    if(gra->g[i].x>gra->advx&&gra->g[i].y>gra->adv_y2)part->PartIV[top4++]=i;
	}
	
	cout<<"Group by:"<<endl;
	cout<<top1<<","<<top2<<","<<top3<<","<<top4<<","<<endl;
	for(i=0;i<JIEDIAN/4;i++)cout<<part->PartI[i]<<",";cout<<endl;
	for(i=0;i<JIEDIAN/4;i++)cout<<part->PartII[i]<<",";cout<<endl;
	for(i=0;i<JIEDIAN/4;i++)cout<<part->PartIII[i]<<",";cout<<endl;
	for(i=0;i<JIEDIAN/4;i++)cout<<part->PartIV[i]<<",";cout<<endl;

}






double Juli(Point point1,Point point2)
{
	return  sqrt(pow(point1.x-point2.x,2)+pow(point1.y-point2.y,2));
}



void  Getjuzhen(Juzhen *juzhen,int *src,Graph *gra)
{
	int j;
	for(int i=0;i<JIEDIAN/4;i++)
		for(j=i+1;j<JIEDIAN/4;j++)
			juzhen->g[i][j]=juzhen->g[j][i]=Juli(gra->g[src[i]],gra->g[src[j]]);
	for( i=0;i<JIEDIAN/4;i++)
		juzhen->g[i][i]=MAX;
    
	/*for( i=0;i<JIEDIAN/4;i++)
	{
		for(j=0;j<JIEDIAN/4;j++)
			cout<<juzhen->g[i][j]<<",";
		cout<<endl;
	}*/
				
}



void Copy(int *src,int *obj,int n)
{
	for(int i=0;i<n;i++)
	{
		obj[i]=src[i];
	}
}

double Count(int *road,Juzhen *gra)
{
	double sum=0;
	int i;
    for(i=0;i<JIEDIAN/4-1;i++)
		sum+=gra->g[road[i]][road[i+1]];
	sum+=gra->g[road[JIEDIAN/4-1]][0];
	return sum;
}

int Notinroad(int i,int top)
{
	int flag=1;
	for(int j=0;j<top;j++)
		if(temp[j]==i)flag=0;
	return flag;
}



void huisuall(int top,Juzhen *gra)
{
	
	int i;
	for(i=0;i<JIEDIAN/4;i++)
	{
		if(Notinroad(i,top))
		{
			temp[top]=i;
			if(top==(JIEDIAN/4-1))
			{
				double count=Count(temp,gra);
				if(count<roadmin){roadmin=count;
									//for(int j=0;j<JIEDIAN/4;j++)cout<<temp[j]<<",";
									//cout<<endl;
				                  Copy(temp,temp1,JIEDIAN/4);}
			}
			else huisuall(top+1,gra);
		}
		
	}
}
void Getlujing(Juzhen *juzhen,int *obj,int *src)
{
	int i;
	roadmin=MAX;temp[0]=0;
	huisuall(1,juzhen);
	cout<<"good"<<endl;
	//for(i=0;i<JIEDIAN/4;i++)cout<<temp1[i]<<",";
	//cout<<endl;
	
	for(i=0;i<JIEDIAN/4;i++)obj[i]=src[temp[i]];
	
	for(i=0;i<JIEDIAN/4;i++)cout<<obj[i]<<",";

}



void Getdivideway(Part *part,Graph *gra)
{
  Juzhen *juzhen=new Juzhen;
  
  Getjuzhen(juzhen,part->PartI,gra);
  Getlujing(juzhen,part->RpartI,part->PartI);
  cout<<endl;
  Getjuzhen(juzhen,part->PartII,gra);
  Getlujing(juzhen,part->RpartII,part->PartII);
  cout<<endl;
  Getjuzhen(juzhen,part->PartIII,gra);
  Getlujing(juzhen,part->RpartIII,part->PartIII);
  cout<<endl;
  Getjuzhen(juzhen,part->PartIV,gra);
  Getlujing(juzhen,part->RpartIV,part->PartIV);
  cout<<endl;

}

void Outputway(Part *part)
{
	int i;
	cout<<"the way is:"<<endl;
	for(i=0;i<JIEDIAN/4;i++)cout<<part->RpartI[i]<<"->";
	for(i=0;i<JIEDIAN/4;i++)cout<<part->RpartII[i]<<"->";
	for(i=0;i<JIEDIAN/4;i++)cout<<part->RpartIII[i]<<"->";
	for(i=0;i<JIEDIAN/4;i++)cout<<part->RpartIV[i]<<"->";
	cout<<part->RpartI[0];
}

void main()
{
	
	
	Graph *graph;
	graph=init();

	Part *part=new Part;
	Divide(part,graph);
	
	getchar();
	Getdivideway(part,graph);//将part->RpartI等数组存为分块的最佳路径

    Outputway(part);//output finally way 可在以后修改

 
}