TRAVELING SALESMAN USING BRANCH AND BOUND TECHNIQUE



TRAVELING SALESMAN USING BRANCH AND
    BOUND TECHNIQUE 




#include<iostream.h>
#include<conio.h>
int main()
{
int i,j,k,n,min,g[20][20],c[20][20],s,s1[20][1],s2,lb;
clrscr();
cout<<"\n TRAVELLING SALESMAN PROBLEM";
cout<<"\n Input number of cities:";
cin>>n;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
c[i][j]=0;
}}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(i==j)
continue;
else{
cout<<"input"<<i<<"to"<<j<<"cost:";
cin>>c[i][j];
}
}
}
for(i=2;i<=n;i++)
{
g[i][0]=c[i][1];
}
for(i=2;i<=n;i++)
{
for(j=2;j<=n;j++)
{
if(i!=j)
g[i][j]=c[i][j]+g[j][0];
}
}
for(i=2;i<=n;i++)
{
for(j=2;j<=n;j++)
{
if(i!=j)
break;
}
}
for(k=2;k<=n;k++){

if(i!=k && j!=k){
if((c[i][j]+g[i][k])<(c[i][k]+g[k][j]))
{
g[i][j]=c[i][j]+g[j][k];
s1[i][j]=j;
}
else
{
g[i][1]=c[i][k]+g[k][j];
s1[i][1]=k;
}
}
}
min=c[1][2]+g[2][1];
s=2;
for(i=3;i<n;i++)
{
if((c[i][i]+g[i][i])<min)
{
min=c[1][i]+g[i][1];
s=i;
}
}
int y=g[i][1]+g[i][j]+g[i][i];
lb=(y/2);
cout<<"Edge Matrix";
for(i=1;i<=n;i++)
{
cout<<"\n";
for(j=1;j<=n;j++)
{
cout<<"\t"<<c[i][j];
}
}
cout<<"\n min"<<min;
cout<<"\n\b"<<lb;
for(i=2;i<=n;i++)
{
if(s!=i && s1[s][1]!=i)
{
s2=i;
}
}
cout<<"\n"<<1<<"-->"<<s<<"-->"<<s1[s][1]<<"-->"<<s2<<"-->"<<1<<"\n";
getch();
return (0);
}


OUTPUT:

 TRAVELING SALESMAN PROBLEM
Input number of cities: 3
input1to2cost:20
input1to3cost:12
input2to1cost:33
input2to3cost:23
input3to1cost:34
input3to2cost:12
Edge Matrix
        0       20      12
        33      0       23
        34      12      0
 min21
3915
1-->2-->3-->1






RESULT:
            Thus, the above program has been compiled, executed and verified successfully.

TRAVELING SALESMAN USING BRANCH AND
    BOUND TECHNIQUE
 

Comments

  1. AnneFebruary 11, 2013 at 10:40 PM

    Hello Vive..i did try your program but what appear in the MS Prompt in the "min21" part would be

    min-858993440
    -858993437

    1-->2-->858993460-->3-->1

    I am using Microsoft Visual C++ 2010 Express and the only part that was omitted was "clscr();"

    Best regard.

    ReplyDelete
  2. UnknownApril 5, 2016 at 10:41 AM

    minimum cost is getting wrong in this code

    ReplyDelete
  3. AnonymousApril 6, 2016 at 4:38 PM

    Minimum cost for the cited example should be 79. Please check your code, and rectify the errors.

    ReplyDelete
  4. AnonymousNovember 10, 2016 at 10:01 PM

    wrong answer

    ReplyDelete
  5. radhaSeptember 18, 2018 at 5:08 PM

    Code works.Keep sharing Artificial Intelligence Online Training

    ReplyDelete
  6. UnknownApril 10, 2020 at 9:23 AM

    What is mean by 3915 in output

    ReplyDelete

Post a Comment

Popular posts from this blog

TRAVELING SALESMAN USING BRANCH AND BOUND TECHNIQUE

Image
The Traveling Salesman Problem (TSP) is a classic problem in computer science and optimization theory. The problem is defined as follows: given a set of cities and the distances between them, find the shortest possible path that visits each city exactly once and returns to the starting city. The Branch and Bound technique is an algorithmic paradigm for solving combinatorial optimization problems. The basic idea is to explore the search space by dividing it into smaller subproblems, and then pruning branches of the search tree that can be shown to lead to suboptimal solutions. The branch and bound algorithm for the TSP works by starting with an initial lower bound on the length of the optimal tour, and then exploring the search space by systematically building up partial tours and computing lower bounds on their completion. Sample C code for solving the Traveling Salesman Problem(TSP) using the branch and bound technique: #include <stdio.h> #include <stdlib.h> #include ...
Read more

OPERATING SYSTM’s ALGORITHM (In LINUX OS) - FIRST FIT, BEST FIT, WORST FIT ALGORITHM

FIRST FIT, BEST FIT, WORST FIT ALGORITHM PROGRAM: #include<stdio.h> int mem[20],proc[20],bp[20],bm[20],cm[20],cp[20],ms,ps,i,j,ch,y; main() {             printf(“\nEnter the number of memory segments”);             scanf(“%d”,&ms);             printf(“\nEnter the memory segment”);             for(i=0;i<ms;i++)             {                         scanf(“%d”,&mem[i]);                         bm[...
Read more

OPERATING SYSTM’s ALGORITHM (In LINUX OS) - BANKERS ALGORITHM

BANKERS ALGORITHM – SINGLE RESOURCES PROGRAM: #include<stdio.h> main() { int j=0,cmp=0,i,tot,avail,need[20],n,tr,max[20],hold[20]; printf("Enter the number of process"); scanf("%d",&n); printf("Enter the number of resources"); scanf("%d",&tr); printf("Enter the max,need,hold for each process"); for(i=0;i<n;i++) { printf("p%d",i); scanf("%d",&max[i]); scanf("%d",&hold[i]); } tot=0; for(i=0;i<n;i++) { tot=tot+hold[i]; need[i]=max[i]-hold[i]; } avail=tr-tot; while(j!=tr) { for(i=0;i<n;i++) { if(need[i]!=0&&need[i]<=avail) { avail=avail+hold[i]; need[i]=0; printf("%d\t%d\n",i,avail); cmp++; } } j++; } if(avail==tr) printf("safe state"); else printf("unsafe state"); }
Read more