C program to for traveling salesman problem?

Answer 1

#include<conio.h>

#include<stdio.h>

#include<stdlib.h>

#define N 50

//Travelling sales man problem , travelling between 6 cities.

//initializing the path lengths between cities and the paths to be included

//in population

void initialize(int pathlen[][6],int path[][6])

{

int i,j,k;

//obtaining pathlengths

for(i=0;i<6;i++)

{

for(j=0;j<6;j++)

{

if(j<i) //path length from a to b will be same as b to a

{

pathlen[i][j]=pathlen[j][i];

}

if(j==i) // path length from a to a will be 0

{

pathlen[i][j]=0;

}

if(j>i) // rest initialized

{

do{

pathlen[i][j]= random(20);

}while(!pathlen[i][j]);

}

}

}

// display the path lengths

printf("\n\tThe PATH LENGTHS ARE: \n" );

for(i=0;i<6;i++)

{

for(j=0;j<6;j++)

{

printf(" %5d ",pathlen[i][j]);

}

printf("\n\n");

}

// generating the population

for(i=0;i<20;i++)

{

for(j=0;j<6;j++)

{

path[i][j]=random(6);

for(k=j-1;k>=0;k--)

{

if(path[i][j]==path[i][k]) //checking to avoid repeatition

{

path[i][j] = random(6);

k=j;

}

}

}

}

}

// evaluating the fitness function or total distance

void evaluate(int pathlen[6][6],int path[20][6],int fx[20])

{

int sum =0,i,j,a,b;

//obtaing the sum of the path taken

for(i=0;i<20;i++)

{

sum=0;

for(j=0;j<5;j++)

{

a=path[i][j];

b=path[i][j+1];

sum=sum+pathlen[a][b];

}

fx[i]=sum;

}

//display the paths generated

printf("\n");

printf("\n\tPATH \t\tf(x) \n\n");

for(i=0;i<20;i++)

{

printf("\t");

for(j=0;j<6;j++)

{

printf(" %d",path[i][j]);

}

printf("\t%d",fx[i]);

printf("\n");

}

}

//selecting the two points for cross over and then performing partial Crossover

void selection(int fx[20],int pos[2],int posmax[2])

{

int min1=fx[0],min2=fx[0],i,max1=fx[0],max2=fx[0];

pos[0]=0;

pos[1]=0;

posmax[0]=0;

posmax[1]=0;

//calculating the minimum postion

for(i=1;i<20;i++)

{

if(fx[i]<min1)

{

min1=fx[i];

pos[0]=i;

}

}

//calaculating the second minimum position

for(i=1;i<20;i++)

{

if(fx[i]<min2&&i!=pos[0])

{

min2=fx[i];

pos[1]=i;

}

}

//calculating the max position

for(i=1;i<20;i++)

{

if(fx[i]>max1)

{

max1=fx[i];

posmax[0]=i;

}

}

//calculating the second max position

for(i=1;i<20;i++)

{

if(fx[i]>max2&&i!=posmax[0])

{

max2=fx[i];

posmax[1]=i;

}

}

printf("\n\tFIRST MINIMUM=%4d \tPOSITION=%4d\n\tSECOND MINIMUN=%4d \tPOSITION=%4d\n\tFIRST MAXIMUM=%4d \tPOSITION=%4d\n\tSECOND MAXIMUM=%4d \tPOSITION=%4d\n",min1,pos[0],min2,pos[1],max1,posmax[0],max2,posmax[1]);

}

//PERFORMING PARTIAL CROSSOVER

void crossover(int pos[2],int path[][6],int child[2][6])

{

int crosspt1,crosspt2,j,i,temp,temp1[2][6],temp2;

//TAKING 2 CROSS POINTS

do

{

crosspt1=random(5);

}while(crosspt1>2) ;

do

{

crosspt2=random(5);

}while(crosspt2<=3);

clrscr();

printf("\n\n\t The CROSSOVER POINTS ARE : %d , %d ",crosspt1,crosspt2);

printf("\n\n\tTHE PATHS FOR CROSSOVER ARE");

printf("\n\n\t\t");

for(j=0;j<6;j++)

{

child[0][j]=path[pos[0]][j];

printf(" %d",child[0][j]);

}

printf("\n\t\t");

for(j=0;j<6;j++)

{

child[1][j]=path[pos[1]][j];

printf(" %d",child[1][j]);

}

int cnt=0;

//swapping the paths between two crosspoints

for(j=crosspt1+1;j<=crosspt2;j++)

{

temp1[1][cnt]=child[0][j];

temp1[0][cnt]=child[1][j];

temp=child[0][j];

child[0][j]=child[1][j];

child[1][j]=temp;

cnt++;

}

//performing partial crossover

int k,m;

for(m=0;m<2;m++)

{

for(i=0;i<crosspt1+1;i++) //taking the path before crosspoint

{

for(j=0;j<cnt;j++) //comparing the path within crossover point

{

if(child[m][i]==temp1[m][j]) //if found then

{

if(m==0) //for child 1

{

temp2=temp1[1][j]; //take the path from child2 crossover

for(k=0;k<6;k++)

{

if(child[m][k]==temp2) //if still the path repeats then repeat the process again

{ temp2=child[1][k];

k=0;

}

}

child[m][i]=temp2; //finally putting the value in child

}

else //for child 2

{

temp2=temp1[0][j];

for(k=0;k<6;k++)

{

if(child[m][k]==temp2)

{temp2=child[0][k];

k=0;

}

}

child[m][i]=temp2;

}

}

}

}

}

for(m=0;m<2;m++)

{

for(i=crosspt2+1;i<6;i++) //now chehcking the path after the second cross point

{

for(j=0;j<cnt;j++) //comparing the path within crossover point

{

if(child[m][i]==temp1[m][j]) //if found then

{

if(m==0) //for child 1

{

temp2=temp1[1][j]; //take the path from child2 crossove

for(k=0;k<6;k++)

{

if(child[m][k]==temp2) //if still the path repeats then repeat the process again

{temp2=child[1][k];

k=0;

}

}

child[m][i]=temp2; //finally assigning the value

}

else //for child 2

{

temp2=temp1[0][j];

for(k=0;k<cnt;k++)

{

if(child[m][k]==temp2)

{temp2=child[0][k];

k=0;

}

}

child[m][i]=temp2;

}

}

}

}

}

//display AfTER CROSSOVER

printf("\n\tAFTER CROSSOVER\n\t\t");

for(j=0;j<6;j++)

{

printf(" %d",child[0][j]);

}

printf("\n\t\t");

for(j=0;j<6;j++)

{

printf(" %d",child[1][j]);

}

}

//insering the paths in population removing those having maximum populaiton

void insert(int child[2][6],int posmax[2],int path[20][6])

{

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

{

path[posmax[0]][j]=child[0][j];

path[posmax[1]][j]=child[1][j];

}

}

// performing mutation

void mutation(int child[2][6])

{

int sel=random(2);

int pos1=random(6);

int pos2=random(6);

int temp=child[sel][pos1];

child[sel][pos1]=child[sel][pos2];

child[sel][pos2]=temp;

}

void main()

{

clrscr();

randomize();

int pathlen[6][6],path[20][6],fx[20],pos[2],posmax[2],child[2][6];

printf("\n\t\t\t TRAVELLING SALESMAN PROBLEM ");

printf("\n\t\t\t_____________________________");

printf("\n\n\n\t\tTHE TRAVELLING SALES MAN PROBLEM DEALS WITH THE FACT");

printf("\n\n\t\tTHAT A SALESMAN TRAVELS BETWEEN CITIES TAKING THE PATH");

printf("\n\n\t\tTHAT IS OF MINIMUN DISTANCE.");

printf("\n\n\n\t\tTO OBTAIN THE MINIMUM DISTANCE WE USE GENETIC ALGO");

printf("\n\n\t\tWHERE WE TAKE AN INITIAL POPULATION OF 20 PATHS AND ");

printf("\n\n\t\tAND THEN THROUGH FITNESS FUNCTION WE OBTAIN THE PATHS ");

printf("\n\n\t\tWITH MINIMUN DISTANCE AND REPLACE THEM WITH THE CHILDS ");

printf("\n\n\t\tAFTER PARTIAL CROSSOVER WITH MAXIMUM DISTANCE.");

getch();

clrscr();

initialize(pathlen,path);

evaluate(pathlen,path,fx);

getch();

selection(fx,pos,posmax);

crossover(pos,path,child);

mutation(child);

getch();

insert(child,posmax,path);

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

{

evaluate(pathlen,path,fx);

selection(fx,pos,posmax);

crossover(pos,path,child);

mutation(child);

insert(child,posmax,path);

}

evaluate(pathlen,path,fx);

selection(fx,pos,posmax);

crossover(pos,path,child);

insert(child,posmax,path);

evaluate(pathlen,path,fx);

getch();

}

Answer 2

#include<stdio.h>

int cost=0;

void get(int a[10][10],int n,int visited[10])

{

int i,j,max,src,dest,wt;

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

{

visited[i]=0;

for(j=1;j<=n;j++)

{

a[i][j]=999;

}

}

max=n*(n-1)/2;

for(i=1;i<=max;i++)

{

printf("\nEnter source and destination:");

scanf("d",&src,&dest);

if(src==0&&dest==0)

break;

else

{

printf("\nEnter the distance:");

scanf("%d",&wt);

a[src][dest]=wt;

a[dest][src]=wt;

}

}

printf("\nCost Matrix");

printf("\n~\n");

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

{

for(j=1;j<=n;j++)

{

if(a[i][j]!=999)

printf("%d\t",a[i][j]);

else

printf("0\t");

}

printf("\n");

}

}

int least(int c,int n,int a[10][10],int visited[10])

{

int i,nc=999,min=999,kmin;

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

{

if((a[c][i]!=0)&&(visited[i]==0))

{

if(a[c][i]<min)

{

min=a[i][1]+a[c][i];

kmin=a[c][i];

nc=i;

}

}

}

if(min!=999)

cost+=kmin;

return nc;

}

void mincost(int city,int n,int a[10][10],int visited[])

{

int i,ncity;

visited[city]=1;

printf("%d->",city);

ncity=least(city,n,a,visited);

if(ncity==999)

{

ncity=1;

printf("%d",ncity);

cost+=a[city][ncity];

return;

}

mincost(ncity,n,a,visited);

}

void put()

{

printf("\nMinimun cost for visiting all cities:%d\n",cost);

}

int main()

{

int n,a[10][10],visited[10];

printf("\nTravelling Salesman Problem Using Branch and Bound");

printf("\n**************************************************");

printf("\n Enter number of Cities:");

scanf("%d",&n);

get(a,n,visited);

mincost(1,n,a,visited);

put(); return 0;

}

OUTPUT:

Travelling Salesman Problem Using Branch and Bound

**************************************************

Enter number of Cities:5

Enter source and destination:1 2

Enter the distance:3

Enter source and destination:1 3

Enter the distance:1

Enter source and destination:1 4

Enter the distance:5

Enter source and destination:1 5

Enter the distance:8

Enter source and destination:2 3

Enter the distance:6

Enter source and destination:2 4

Enter the distance:7

Enter source and destination:2 5

Enter the distance:9

Enter source and destination:3 4

Enter the distance:4

Enter source and destination:3 5

Enter the distance:2

Enter source and destination:4 5

Enter the distance:3

Cost Matrix

~

0 3 1 5 8

3 0 6 7 9

1 6 0 4 2

5 7 4 0 3

8 9 2 3 0

1->3->5->4->2->1

Minimum cost for visiting all cities:16