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(“—————————-”);

}

}