TSP.rar_Nearest neighbor_TSP JAVA_tsp

/* * Main.java * * Created on 2011年10月6日, 下午 6:59 * * To change this template, choose Tools | Template Manager * and open the template in the editor. */ package tsp; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.FileWriter; import java.io.IOException; import java.io.FileReader; import java.util.ArrayList; import java.util.Iterator; import java.util.TreeMap; /** * * @author Yagami */ public class TSP { static final String filename ="src\tsp\kroA100.tsp" ; //E:\\u1060.tsp" ;" static int matrixSize = 0; double [][] distanceMatrix ; double best_fitness = 999999999999.99999; public TSP (int option) { System.out.println ("============================= Preprocess ============================="); double [][] cityMatrix = getCityMatrix (filename); //取得 City 座標 (X,Y) switch (option) { case 1 : // Option : print this.distanceMatrix = getDistanceMatrix (cityMatrix,false); break ; case 2 : //Option write this.distanceMatrix = getDistanceMatrix (cityMatrix,true); break ; default : this.distanceMatrix = getDistanceMatrix (cityMatrix) ; //參數加布林 true = 輸出.txt ; false = 螢幕輸出 break ; } System.out.println ("======================================================================"); } public TSP () { double [][] cityMatrix = getCityMatrix (filename); //取得 City 座標 (X,Y) this.distanceMatrix = getDistanceMatrix (cityMatrix); System.out.println ("============================= Preprocess Finish !! ============================="); } /** * @param args the command line arguments */ public static void main (String[] args) { new TSP (); } private double[][] getCityMatrix (String filename) { double[][] cityMatrix = null ; FileReader fr = null ; BufferedReader br = null ; try { fr = new FileReader (filename) ; br = new BufferedReader (fr) ; for (int i = 0 ; i<6 ; i++) { String str = br.readLine () ; if(i==3) { String [] token = str.split (" ") ; this.matrixSize = Integer.parseInt (token [1]) ; } } cityMatrix = new double[this.matrixSize][2] ; String str = null ; int raw = 0 ; while(!( str = br.readLine ()).equals ("EOF")) { String [] token = str.split (" ") ; cityMatrix[raw][0] = Double.parseDouble (token[1]) ; cityMatrix[raw][1] = Double.parseDouble (token[2]) ; raw ++ ; } } catch (IOException ex) { ex.printStackTrace (); } finally { try { br.close (); fr.close (); } catch (IOException ex) { ex.printStackTrace (); } } return cityMatrix ; } private double[][] getDistanceMatrix (double [][] cityMatrix , boolean bolean ) { double [][] distanceMatrix = getDistanceMatrix ( cityMatrix ) ; if(!bolean) { for(int x = 0 ; x < cityMatrix.length ; x++) { for(int y = 0 ; y <cityMatrix.length ; y++) { System.out.print ( distanceMatrix[x][y] + "\t"); } System.out.println (); } } else { writeData (filename.replaceAll (".tsp","_DistanceMatrix.txt") , distanceMatrix); } return distanceMatrix ; } private double[][] getDistanceMatrix (double [][] cityMatrix ) { double [][] distanceMatrix = new double [cityMatrix.length][cityMatrix.length]; for(int x = 0 ; x < cityMatrix.length ; x++) { for(int y = 0 ; y <= x ; y++) { if(x == y) { distanceMatrix[x][y] = 0.0 ; } else { double delX = cityMatrix[x][0] - cityMatrix[y][0] ; double delY = cityMatrix[x][1] - cityMatrix[y][1] ; distanceMatrix[x][y] = Math.sqrt (Math.pow (delX,2)+(Math.pow (delY,2))); distanceMatrix[y][x] = Math.sqrt (Math.pow (delX,2)+(Math.pow (delY,2))); } } } return distanceMatrix ; } private void writeData (String filename , double [][] Matrix) { if(Matrix.length == Matrix[0].length) { FileWriter fw = null; BufferedWriter bw = null ; try { fw = new FileWriter (filename); bw = new BufferedWriter (fw); for(int x = 0 ; x < Matrix.length ; x++) { for(int y = 0 ; y <Matrix.length ; y++) { bw.write ( Matrix[x][y] + "\t"); } bw.newLine (); } } catch (IOException ex) { ex.printStackTrace (); } finally { try { bw.close (); fw.close (); } catch (IOException ex) { ex.printStackTrace (); } } } else { System.out.println ("Error : 非方陣無法適用該 method !! - writeData (String , double [][])"); } } public ArrayList< Double > getPopulationFitness (ArrayList < int[] > population) { ArrayList < Double > fitnesses = new ArrayList < Double > () ; Iterator < int[] > it = population.iterator (); while(it.hasNext ()) { int [] temp = it.next () ; fitnesses.add (getFitness (temp)); } return fitnesses ; } public double getFitness (int [] chromosome) { double fitness = 0.0 ; for ( int i = 0 ; i < chromosome.length-1 ; i ++ ) { fitness = fitness + distanceMatrix[ chromosome[i]-1 ][ chromosome[i+1]-1 ] ; //city 命名由1~N 故(chromosome[i]-1) } fitness = fitness + distanceMatrix[ chromosome[chromosome.length-1]-1 ][ chromosome[0]-1 ] ; if(fitness < best_fitness) { best_fitness = fitness ; } return fitness ; } }