nearestneighbouralgorithm.java

collective processing environment for mobile devices. It is an environment for mobile device to solv

/******************************************************************************
   
   Project Name.......: Travelling Salesman Problem
   Project Number.....: 18050315
   Description........: The famous travelling salesman problem, in which the 
			program tries to find the minimum distance between 
			given cities.
   Technical Details..: * Using trees.
			* The permute function.
   Compiler...........: Java(R) 2 SDK, Standard Edition, v 1.2.1
   Author.............: Ozer Senturk
   Web Site...........: www23.brinkster.com/ozersenturk/projects.htm
   E-Mail.............: [e-mail]

******************************************************************************/

import java.io.*;    //...For file operations...
import java.util.*;  //...For StringTokenizer...

public class NearestNeighbourAlgorithm{
	
	int number = 0;        //...Number of first cities that will be read...
	File inFile;           //...The input file...
	City Cities[];         //...The first "number" cities that are read...
	City Result[];         //...The resulting sequence of cities... 
	int Indices[];         //...Indices of the resulting sequence...
	double Distances[][];  //...The distances between cities...
	int lastIndex;         //...Last index of the Result array...
	int candidateIndex;    //...The index of the Cities array that is candidate to be the next...
	FileReader fr;
	BufferedReader br;
	String name, theta, phi, space;
	StringTokenizer st;
	int i, j;
	double minDistance = 999999999;  	
	double totalDistance;
	long beginTime, endTime;   //...For the time elapsed...
	
	//...Calculates the distance between two cities given their theta and phi coordinates...
	double calculateDistance(double theta1, double phi1, double theta2, double phi2){
		theta1 = Math.toRadians(theta1);
		theta2 = Math.toRadians(theta2);
		phi1   = Math.toRadians(phi1);
		phi2   = Math.toRadians(phi2);
		return 6400 * Math.acos(Math.cos(phi1) * Math.cos(phi2) * (Math.cos(theta1) * Math.cos(theta2) +
			Math.sin(theta1) * Math.sin(theta2)) + Math.sin(phi1) * Math.sin(phi2));
	}
	
	public void printResult() throws Exception{
		double elapsedTime = (double)(endTime - beginTime) / (double)1000;

		File out = new File("nna_tsp" + number + ".txt");
		FileWriter fw = new FileWriter(out);
		PrintWriter pw = new PrintWriter(fw);
		pw.println("********************************************");
		pw.println("* Solutions By Nearest Neighbour Algorithm *");
		pw.println("********************************************");
		pw.println();
		pw.println("Number of cities...: " + number);
		pw.println();
		pw.println("Distances between cities...:");
		for(i = 0; i < number; i++)
			for(j = i + 1; j < number; j++)
				pw.println(Cities[i].name + " - " + Cities[j].name + " ...: " + Distances[i][j]);
		pw.println();
		pw.println("Shortest tour is...:");
		for(i = 0; i < number; i++)
			pw.print(Result[i].name + " - ");
		pw.println("Istanbul");
		pw.println("Minimum distance is...: " + totalDistance);
		pw.println("Time elapsed...: " + elapsedTime + " seconds");
		fw.close();
		System.out.println("Minimum distance is...: " + totalDistance);
		System.out.println("Time elapsed...: " + elapsedTime + " seconds");
		System.out.println("Check file \"nna_tsp" + number + ".txt\" for details.");
	}

	public NearestNeighbourAlgorithm(String args[]) throws Exception{
		beginTime = System.currentTimeMillis(); //...Get the start time...
		//...Make sure that number of arguments is correct...
		if(args.length != 2){
			System.out.println("ERROR...\nUsage: javac OptimumSolver <Number> <FileName>");
			System.exit(0);
		}
		//...Make sure that file exists and is readable...
		inFile = new File(args[1]);
		if(!inFile.exists() || !inFile.canRead()){
			System.out.println("ERROR...\nCan not read from input file \"" + inFile + "\"");
			System.out.println("Make sure that file exists and is readable");
			System.exit(0);
		}
		//...Make sure that number is an integer...
		try{
			number = Integer.parseInt(args[0]);
		}
		catch(Exception e){
			System.out.println("ERROR...\nNumber should be an integer");
			System.exit(0);
		}
		//...Up to know everything is fine...
		//...Read the file and fill in the "Cities" array...
		Cities = new City[number];
		fr = new FileReader(inFile);
		br = new BufferedReader(fr);
		for(i = 0; i < number; i++){
			name  = br.readLine();
			theta = br.readLine();
			phi   = br.readLine();
			space = br.readLine();
			st = new StringTokenizer(name, ",");
			name = st.nextToken();
			Cities[i] = new City(name, Double.parseDouble(theta), Double.parseDouble(phi));
		}
		//...Create the result array...
		Result = new City[number];
		//...Create the indices array...
		Indices = new int[number];
		//...Fill in the "Distance" array...
		Distances = new double[number][number];
		for(i = 0; i < number; i++)
			for(j = 0; j < number; j++)
				Distances[i][j] = calculateDistance(Cities[i].theta, Cities[i].phi, 
								    Cities[j].theta, Cities[j].phi);
		//...Apply the nearest neighbour algorithm...
		Result[0] = Cities[0]; //...Put the starting point...
		Cities[0].picked = true;
		Indices[0] = 0;
		lastIndex = 0; //...Last index of the Result array...
		candidateIndex = 0;
		//...Get the nearest point to the lastIndex'ed element...
		for(i = 0; i < number - 1; i++){
			minDistance = 999999999;
			for(j = 0; j < number; j++){
				if(Cities[j].picked != true){
					if(Distances[Indices[lastIndex]][j] < minDistance){
						candidateIndex = j;
						minDistance = Distances[Indices[lastIndex]][j];
					}
				}
			}
			Result[++lastIndex] = Cities[candidateIndex];
			Indices[lastIndex] = candidateIndex;
			Cities[candidateIndex].picked = true;
		}
		//...Calculate the total distance...
		for(i = 0; i < number; i++){
			totalDistance += Distances[Indices[i]][Indices[(i + 1) % number]];
		}	
		endTime = System.currentTimeMillis(); //...Get the end time...
		//...Print the result in a file...
		printResult();						
	}

	public static void main(String args[]) throws Exception{
		NearestNeighbourAlgorithm nna = new NearestNeighbourAlgorithm(args);
	}
}

class City{
	String name;    //...The name of the city...
	double theta;   //...The theta coordinate...
	double phi;     //...the phi coordinate...
	boolean picked; //...Is the item picked or not...
	
	City(String Name, double Theta, double Phi){
		name = Name;
		theta = Theta;
		phi = Phi;
		picked = false;
	}
}