C code for Branch and Bound Issue -
so think on right track using branch , bound method solve heuristic solution traveling problem, however, segmentation fault in "least" function, still having hard time wrapping head around algorithm. fixing appreciated. requirements function (because main function looks funny) program should take 150 cities, , if reads under 60 seconds bonus points ( means don't fail) input file like(for example): c 1 c 2 1 2 300 'c' means "create city", , 'a' means "add boundary." why program set way is.
#include<stdio.h> #include<stdlib.h> #include<string.h> int cost=0; int main(){ int numcity ,a[151][151],visited[151],worthless,city1,city2,distance; char citystring[2]; a[1][1]=0; while(scanf("%s",citystring) != eof){ if(strcmp(citystring, "c") == 0){ scanf("%d", &worthless); numcity++; } else if(strcmp(citystring, "a") == 0){ scanf("%d %d %d",&city1,&city2,&distance); a[city1][city2] = distance; a[city2][city1] = distance; } } mincost(1,numcity,a,visited); printf("the minimum cost tour %d",cost); return 0; } int mincost(int city,int n,int a[151][151],int visited[151]){ int i,ncity; visited[city]=1; printf("%d->",city); ncity=least(city,n,a,visited); if(ncity==999999){ ncity=1; printf("%d",ncity); cost+=a[city][ncity]; } mincost(ncity,n,a,visited); } int least(int c,int n,int a[151][151],int visited[10]){ int i,nc=999999,min=999999,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!=999999) cost+=kmin; return nc; }
c arrays 0-indexed, index goes 1..n instead of 0..(n-1) ... why declared 151 instead of 150?
but crash due mincost calling unconditionally. think you're on right track having trouble wrapping head around algorithm ... think statements inconsistent. should sure understand algorithm before attmepting code it.
Comments
Post a Comment