Traveling salesman problem is a classic NP hard problem.

Problem Statement: A salesman has to visit N number of cities, say A, B, C and D. He is starting from A, and need to visit all other cities in a way that he has to cover shortest distance.

Solution: Ideal solution will be to figure out all the permutations of traveling N cities, and then choose the one where distance traveled is smallest.

Finding all Permutations is definitely a trouble. 10! will take us into million permutations and moving ahead further adds to trouble.

One solution can be to pick random city from every city and move ahead. A little betterment will be to move to next nearest city instead of random city.

1. Start from city 0

2. Look for the nearest city, not visited already

3. Go to the nearest city, mark it visited

4. If not all city visited, go to 2

Here is a piece of code

` public static int travel()`

{

currcity=0;

path[index++]=0;

int[][] tempdistance=distance.clone();

printarr(tempdistance);

citiesLeft=removeArr(citiesLeft, currcity);

`while(citiesLeft.length>0)`

{

int nextcity=findNearest(currcity, tempdistance);

path[index++]=nextcity;

currcity=nextcity;

citiesLeft=removeArr(citiesLeft, currcity);

printarr(tempdistance);

}

//Final path

for(int i=0;i<path.length;i++) System.out.print(path[i]+">");

return -1;

}

Here is the complete code

public class TravelingSalesman {

static int distance[][]={

//AA=0; AB=1; AC=2; AD=3

{0,6,2,1},

{2,0,2,3},

{1,2,0,1},

{6,10,2,0}

};static int path[]=new int[4];

static int currcity=0;

static int index=0;

static int totalcity=0;

static int[] citiesLeft={0,1,2,3};public static void main(String sp[])

{

totalcity=distance[0].length;

System.out.println(travel());

}public static int travel()

{

/*

* 1. Start from city 0

* 2. Look for the nearest city, not visited already

* 3. Go to the nearest city, mark it visited

* 4. If not all city visited, go to 2

*/currcity=0;

path[index++]=0;int[][] tempdistance=distance.clone();

printarr(tempdistance);

citiesLeft=removeArr(citiesLeft, currcity);while(citiesLeft.length>0)

{

int nextcity=findNearest(currcity, tempdistance);

path[index++]=nextcity;

currcity=nextcity;

citiesLeft=removeArr(citiesLeft, currcity);

printarr(tempdistance);

}

//Final path

for(int i=0;i<path.length;i++) System.out.print(path[i]+”>”);

return -1;

}public static int[] removeArr(int[] arr, int num)

{

int[] citiesLeft=new int[arr.length-1];

if(citiesLeft.length==0)

return citiesLeft;

int j=0;

for(int i=0;i<arr.length;i++)

{

if(arr[i]!=num)

citiesLeft[j++]=arr[i];

}

return citiesLeft;

}public static boolean availableInCitiesLeft(int check)

{

for(int i=0;i<citiesLeft.length;i++)

{

if(citiesLeft[i]==check)

return true;

}

return false;

}public static int findNearest(int curr, int arr[][])

{

int nearest=0;

int nearestval=0;

for (int i=0;i<arr[0].length;i++) { if(availableInCitiesLeft(i)) if(arr[curr][i]>0)

if(nearestval<=0 || arr[curr][i]<nearestval)

{

nearestval=arr[curr][i];

nearest=i;}

}

return nearest;

}public static void printarr(int arr[][])

{

for(int i=0;i<arr[0].length;i++){

for(int j=0;j<arr[0].length;j++){

System.out.print(arr[i][j]+”,”);

}

System.out.println(“”);

}

System.out.println(“—————————-”);}

}