'I am trying to write a simple tsp question but meet some problems
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define max 100
void tsp(int Dis[max][max],int v[],int N,int count,int currPos,int cost,int ans){
/*for(j=1;j<N+1;j++){
if(visited[j]==0){
sum+=Dis[i][j];
visited[j] = 1;
DFS(visited,j,Dis,sum);
}
}*/
if(count == N&&Dis[1][currPos]>0){
if(ans> cost+Dis[1][currPos]) ans = cost+Dis[1][currPos];
//ans = min(ans,cost + Dis[1][currPos]);
return;
}
for (int i = 0;i<N+1;i++){
if(v[i]==0&&Dis[currPos][i]>0){
v[i] = 1;
tsp(Dis,v,N,count + 1,cost + Dis[currPos][i],ans);
v[i] = 0;
}
}
};
int main(int argc, char const *argv[])
{
int N;
int size = 1;
int count = 1;
char x[100] = {0};
FILE *fp=fopen(argv[1],"r");
if(fp==NULL){
printf("Cannot open the file,strike any key to exit!\n");
getchar();
exit(0);
}
for (int i = 0;!feof(fp);i++){
fscanf(fp,"%hhd",&x[i]);
}
N=x[0];
int Dis[N][N], City[N];
for(int i=1;i<N;i++){
size=size*i;
}
char y[size];
for (int i=1;i<size+1;i++){
y[i] = x[i];
//printf("%d\n",y[i]);
}
for(int i=2; i < N + 1; i++){
for(int j=1; j < i ; j++){
Dis[j][i] = y[count];
Dis[i][j] = y[count];
count+=1;
printf("(%d,%d),(%d,%d)",j,i,i,j);
printf("%d\n",Dis[j][i]);
}
}
for(int i=0;i<N;i++){
City[i]=i + 1;//create the number of city with 1 ...... N
}
int curr_constraint = 0;
int v[N+1];
for (int i = 1; i < N+1; i++){
v[i] = 0;
}
for(int i = 1;i<N+1;i++){
curr_constraint += Dis[i][i+1];
}
v[1]= 1;
int ans = INT_MAX;
printf("The orginal constraint is %d\n",curr_constraint);
tsp(Dis[N][N],v,N,0,1,0,ans);
return 0;
}
The question asks me to implement a tsp question which always starts with the number 1 city, it will read the data including the numbers of nodes and length between two citys from a txt file in the position of argv[1]. And then find the smallest way for all city without going back the first city.
The file is like following:
4
5
40 9
11 6 8
which means:
- the number of citys N = 4
- Distance: d[1][2] = 5, d[1][3] = 40, d[2][3] = 9, d[1][4] = 11, d[2][4] = 6, d[3][4] = 8.
I want to create a array including the distance in tsp function, but the lenght I read only in the main function. How to solve this problem?
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
