TSP问题(贪心法）最近邻点和最短连接

1.最近邻点法 (贪心策略 TSP）

2. 最短连接 TSP问题 贪心算法

#include<stdio.h>
#include<iostream>
using namespace std;



//采用最近邻点贪心策略求TSP问题。 
int TSP1(double arc[6][6],int w)//假定从顶点w出发
{
	int n=6;
	int  edgeCount=0;//哈密顿回路的边数 
	int TSPLength=0;
	int min,u,v;
	
	int flag[n]={0}; // 顶点均未加入哈密顿回路
	
	u=w;//w为出发点   u为加入到哈密顿回路的点 
	flag[w]=1; 
	
	while(edgeCount<n-2) //已经加入一个出发点，只需要再4个点  0  1   2   3 四次找点
	{
		min=100;
		for(int j=1;j<n;j++)  //求arc[u]的最小值 
		{
			if((flag[j]==0) && (arc[u][j]!=0) &&((arc[u][j]!=100e5))&& (arc[u][j]<min)) //j点没有被加入哈密顿回路  排除自己  找到最小值 
		     {
		        	v=j;//v点最终是距离u点最近的点 
				 min=arc[u][j];
				  
			 }
					 
		 } 
		 //找到距离u点的最近的点，把它加入哈密顿回路
		 TSPLength+=arc[u][v];
		 flag[v]=1;
		 edgeCount++;
		 cout<<u<<"-->"<<v<<endl;   
		 u=v;  //把v点赋值给u，接下来找距离v点最近的点      while循环控制直到所有点都被加入进去 	  
	}
	cout<<v<<"-->"<<w<<endl;//输出最后的回边
	return (TSPLength+arc[u][w]);//返回最终的最短哈密顿回路的长度!! 

 } 
 int main() 
 {
 		double arc[6][6]={
		     {0,0,0,0,0,0},
	         {0,100e5,3,3,2,6},
	         {0,3,100e5,7,3,2},
	         {0,3,7,100e5,2,5},
	         {0,2,3,2,100e5,3},
	         {0,6,2,5,3,100e5}
	        };
	       
	int n2=TSP1(arc,1);
	cout<<n2; 
 }

#include<stdio.h>
#include<iostream>
#include<malloc.h> 
using namespace std;


//查找最小边函数  Search 
pair<int,int> Search(int **A,int N,int *flag,int **AF) { //查找最小边

 int min=10e5,a=0,b=0;
 for(int i=0; i<N; i++) {
  for(int j=0; j<i; j++) {
   if(!AF[i][j]&&flag[i]<2&&flag[j]<2&& A[i][j]<min) {//如果这条边没有走过，两边的城市没有同时有两个被走过的边 
    a=i; 
    b=j;
    min=A[i][j];//依次比较 
   }
  }
 }
 flag[a]++;
 flag[b]++;
 AF[a][b]=1;
 return pair<int,int>(a,b);
}



//TSP2
int TSP2(int **A,int N,int *flag,int **AF) {
 int tsp=0,i,j,k;
 for(k=0; k<N; k++) {//选择N次最短边 
  pair<int,int> a=Search(A,N,flag,AF);
  tsp+=A[a.first][a.second];//每次加入最增的最短边 
 }
 return tsp;
}




int main() 
 {
 	
 	//N初始化
	 int N=5; 
 	
	 	
 	//A初始化(城市之间的距离)
 	int **A=(int **)malloc(N*sizeof(int));
	cout<<"输入5个城市之间的距离(0表示城市间不通):"<<endl;
	for(int i=0;i<N;i++)
	{
		A[i]=(int*)malloc(N*sizeof(int));
		for(int j=0;j<N;j++)
		{
			cin>>A[i][j];
		}
	}		 
	
		
	//AF初始化，记录边是否走过 
	int **AF=(int **)malloc(N*sizeof(int));//记是否边走过，初始值设为0，走过设为1
	for(int i=0;i<N;i++)
	{
		AF[i]=(int*)malloc(N*sizeof(int));
		for(int j=0;j<N;j++)
		{
			AF[i][j]=0;
		}
	}
 	  
 	  
 	//flag初始化,记录城市是否走过 
	int *flag=(int *)malloc(N*sizeof(int));//标记是否城市走过，初始值设为0，走进去又走出来成为2 
    for(int i=0;i<N;i++)//设置flag的初值 
	{
		flag[i]=0;
	}
	   
	  	  
    cout<<"最短路径长度：";
	cout<<TSP2(A,N,flag,AF);
 }