tsptemp.java

人工智能经典问题TSP问题的Java实现

class Cities{
	private   int  num;//cities number
	private   int  cityFlag[];//the ist city
	private   int  cities[][];//cities constructor
	protected int  shortestPath[];//save the shortest paths older
	protected long pathLength;//the shortest path length
	protected int  cityToured[];//if the ist city is toured until now
	protected int  cNum;//the num of cities toured
    
	//construct the symmetry constructor diagram,
	public Cities(int n)
	{
		num=n;
		cities=new int[num][num];
		cityFlag=new int[num];
		shortestPath=new int[num];
		cityToured=new int[num];
		
		System.out.println("                       The TSP of "+num+" Cities");
		System.out.println("[1]:The TSP construcor diagram:\n");
		for(int i=0;i<num;i++)
		   for(int j=i;j<num;j++)
		   {
		   	if(i==j)
		   	  cities[i][j]=0;
		   	else
		   	{
		   	  double tempnum = 100 * Math.random();
		      cities[i][j]=(int)tempnum;	
		   	}   	
		   	
		   }
		for(int i=1;i<num;i++)
		   for(int j=0;j<i;j++)
		     cities[i][j]=cities[j][i];
		
		for(int i=0;i<num;i++)		   
		{
			System.out.print(" ");
			for(int j=0;j<num;j++)
			{
				if(cities[i][j]<10)
				  System.out.print(" "+cities[i][j]+"  ");
				else
				  System.out.print(cities[i][j]+"  ");				    
			}
			   
			System.out.print("\n");
		}
	}
	
	
	//initial the toured state
	public void initToured()
	{
		for(int i=0;i<num;i++)
		  cityFlag[i]=i;
		for(int i=0;i<num;i++)
		  cityToured[i]=0;
		cNum=0;
	}

	//get the TSP anwser
	public void getTSP(int startFlag)
	{
		int flag=0;//start flag next time
		long shorterLen=1000000;//the shortest next i
		
		if(cNum==0)//start from the first city
		{
			cNum++;
			shortestPath[0]=0;
			cityToured[0]=1;
			flag=0;
			getTSP(flag);
		}
		
		else if(cNum==num)
		{   
		    for(int i=0;i<num;i++)
			   pathLength+=cities[i][(i+1)%num];
			   
			System.out.println("\n[2]:The TSP anwser is: ");
			System.out.print("    ");
			for(int i=0;i<num;i++)
			   System.out.print(shortestPath[i]+"->");
			System.out.println("0");
			System.out.println("[3]:The Length of shortest path is: "+pathLength);
			
			
		}
		
		else
		{
			for(int i=0;i<num;i++)//select the shorter city next the flaged city
			{
				if(cityToured[i]==0)
				{
					if(cities[startFlag][i]<shorterLen)
					   shorterLen=cities[startFlag][i];
				}
			}
			
			for(int i=0;i<num;i++)
			{
				if(cityToured[i]==0)
				{
					if(cities[startFlag][i]==shorterLen)
					   flag=i;
				}
			}
			
			shortestPath[cNum]=flag;
			cityToured[flag]=1;
			cNum++;
			
			getTSP(flag);		
			
		}
	 	
		
		
	}
}

class TspTemp{
	public static void main(String args[]){
		Cities mycities=new Cities(15);
		mycities.initToured();
		mycities.getTSP(0);
		
	}
	
}