24. TRAVELLING SALES PERSON PROBLEM (TSP)

Code:

import java.util.*;

import java.text.*;

class TSP

{

int weight[][],n,tour[],finalCost;

final int INF=1000;

public TSP()

{

Scanner s=new Scanner(System.in);

System.out.println("Enter no. of nodes:=>");

n=s.nextInt();

weight=new int[n][n];

tour=new int[n-1];

for(int i=0;i<n;i++)

{

for(int j=0;j<n;j++)

{

if(i!=j)

{

System.out.print("Enter weight of "+(i+1)+" to "+(j+1)+":=>");

weight[i][j]=s.nextInt();

}

}

}

System.out.println();

System.out.println("Starting node assumed to be node 1.");

eval();

}

public int COST(int currentNode,int inputSet[],int setSize)

{

if(setSize==0)

return weight[currentNode][0];

int min=INF,minindex=0;

int setToBePassedOnToNextCallOfCOST[]=new int[n-1];

for(int i=0;i<setSize;i++)

{

int k=0;//initialise new set

for(int j=0;j<setSize;j++)

{

if(inputSet[i]!=inputSet[j])

setToBePassedOnToNextCallOfCOST[k++]=inputSet[j];

}

int temp=COST(inputSet[i],setToBePassedOnToNextCallOfCOST,setSize-1);

if((weight[currentNode][inputSet[i]]+temp) < min)

{

min=weight[currentNode][inputSet[i]]+temp;

minindex=inputSet[i];

}

}

return min;

}

public int MIN(int currentNode,int inputSet[],int setSize)

{

if(setSize==0)

return weight[currentNode][0];

int min=INF,minindex=0;

int setToBePassedOnToNextCallOfCOST[]=new int[n-1];

for(int i=0;i<setSize;i++)//considers each node of inputSet

{

int k=0;

for(int j=0;j<setSize;j++)

{

if(inputSet[i]!=inputSet[j])

setToBePassedOnToNextCallOfCOST[k++]=inputSet[j];

}

int temp=COST(inputSet[i],setToBePassedOnToNextCallOfCOST,setSize-1);

if((weight[currentNode][inputSet[i]]+temp) < min)

{

min=weight[currentNode][inputSet[i]]+temp;

minindex=inputSet[i];

}

}

return minindex;

}

public void eval()

{

int dummySet[]=new int[n-1];

for(int i=1;i<n;i++)

dummySet[i-1]=i;

finalCost=COST(0,dummySet,n-1);

constructTour();

}

public void constructTour()

{

int previousSet[]=new int[n-1];

int nextSet[]=new int[n-2]; for(int i=1;i<n;i++)

previousSet[i-1]=i;

int setSize=n-1;

tour[0]=MIN(0,previousSet,setSize);

for(int i=1;i<n-1;i++)

{

int k=0;

for(int j=0;j<setSize;j++)

{

if(tour[i-1]!=previousSet[j])

nextSet[k++]=previousSet[j];

}

--setSize;

tour[i]=MIN(tour[i-1],nextSet,setSize);

for(int j=0;j<setSize;j++)

previousSet[j]=nextSet[j];

}

display();

}

public void display()

{

System.out.println();

System.out.print("The tour is 1-");

for(int i=0;i<n-1;i++)

System.out.print((tour[i]+1)+"-");

System.out.print("1");

System.out.println();

System.out.println("The final cost is "+finalCost);

}

}

class TSPExp

{

public static void main(String args[])

{

TSP obj=new TSP();

}

}

OUTPUT :

Enter no. of nodes:=>

5

Enter weight of 1 to 2:=>4

Enter weight of 1 to 3:=>6

Enter weight of 1 to 4:=>3

Enter weight of 1 to 5:=>7

Enter weight of 2 to 1:=>3

Enter weight of 2 to 3:=>1

Enter weight of 2 to 4:=>7

Enter weight of 2 to 5:=>4

Enter weight of 3 to 1:=>7

Enter weight of 3 to 2:=>4

Enter weight of 3 to 4:=>3

Enter weight of 3 to 5:=>6

Enter weight of 4 to 1:=>8

Enter weight of 4 to 2:=>5

Enter weight of 4 to 3:=>3

Enter weight of 4 to 5:=>2

Enter weight of 5 to 1:=>4

Enter weight of 5 to 2:=>3

Enter weight of 5 to 3:=>2

Enter weight of 5 to 4:=>1

Starting node assumed to be node 1.

The tour is 1-2-3-4-5-1

The final cost is 14