TSP的Java实现.rar.rar_ tsp java_TSP in Java_TSP ja_TSPLIB_java T

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); } }