I am working on a class project to solve the wandering Salesman problem, which is basically the TSP, except you don't return to the source. I took the approach of finding all possible permutations of a set of vertices and then iteratively calculating the length and comparing them to find the smallest. I know it's not the best approach, but its what our professor wanted.
When I run the code below, it works fine and gives me the right answers when the input array is less than 7 X 7. But when its 7 X 7, it returns "Bus Error: 10", and if the size is 12 x 12, it returns "Segmentation Fault : 11". I looked up these problems for hours and couldn't figure out what's wrong. I'm not much of an expert in C programming, and I'm honestly really confused with pointers. Thank you so much for the help, I appreciate it greatly!
Oh, and sorry about the messy code.
#include <stdio.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include<stdlib.h>
int x = 0;
int a[];
void swap (int v[], int i, int j) {
int t;
t = v[i];
v[i] = v[j];
v[j] = t;
}
/* recursive function to generate permutations */
int* perm (int v[], int n, int i) {
/* this function generates the permutations of the array
* from element i to element n-1
*/
int j;
/* if we are at the end of the array, we have one permutation
* we can use (here we print it; you could as easily hand the
* array off to some other function that uses it for something
*/
if (i == n) {
for (j=0; j<n; j++){ a[x] = v[j]; x++;} // printf ("%d ", v[j]);
// printf ("\n");
}
else
/* recursively explore the permutations starting
* at index i going through index n-1
*/
for (j=i; j<n; j++) {
/* try the array with i and j switched */
swap (v, i, j);
perm (v, n, i+1);
/* swap them back the way they were */
swap (v, i, j);
}
return a;
}
int fact(int n){
if(n==1){
return 1;
}
else{
return n * fact(n-1);
}
}
int findShortestPath(int **v , int length){
int pathArrayMultiplier = 0;
int ShortestPathLength = 99999;
printf("Called");
int arrayOfVertices[length-1];
for(int i=0 ; i<length-1 ; i++){
arrayOfVertices[i] = i+2;
}
int n = fact(length-1);
bool doBreak = false;
int pathArray[length-1];
//printf(" Called 3");
printf(" %d" , n);
int* Answer;
Answer = malloc(sizeof(int *));
Answer = perm(arrayOfVertices , length-1 , 0);
printf("Called 4");
int j =-1;
for(int i=0 ; i< n*(length-1) ; i++){
doBreak = false;
j++;
printf("%d " , *(Answer + i));
pathArray[j] = *(Answer+i);
if(j == length-2)
{
j = -1;
// Check for negative values. If any value is negative, disregard path
int checklength = *((int *)v + 0 *length + (pathArray[0]-1));
if(checklength < 0){
printf("First check called");
continue;}
for(int i =0 ; i<length-2 ; i++){
if(*((int *)v + (pathArray[i]-1) * length + (pathArray[1 + i]-1)) < 0){
doBreak = true;
printf("Second Check called");
break;}
}
if(doBreak) { pathArrayMultiplier++; continue;}
printf("\n");
int pathLength = *((int *)v + 0 *length + (pathArray[0]-1));
for(int i =0 ; i<length-2 ; i++){
pathLength = pathLength + *((int *)v + (pathArray[i]-1) * length + (pathArray[1 + i]-1));}
printf("Path Length is %d\n" , pathLength);
if(pathLength < ShortestPathLength) { ShortestPathLength = pathLength;}
}
}
printf("\n\n Shortest Path Length is %d \n" , ShortestPathLength);
return ShortestPathLength;
}
int main () {
int len = 5;
printf("Array is initialized");
int v[7][7] = {0,7,-1,10,1,-1,-1,7,0,-1,-1,10 ,-1 ,1,-1,-1,0,10,1,10,-1,10,-1,10, 0,8,-1,-1,-1,10,1,8,0,10,-1,-1,-1,10,-1,10,0,70,-1,1,-1,-1,-1, 70 , 0};
printf("Array is initialized");
int **realArrayPointer = v;
findShortestPath(realArrayPointer, 7);
return 0;
}
Your code is a mess and practically unreadable. However, I took it upon myself as a challenge to see if I could spot your bug. What I saw is that you declare an empty array at the top:
int a[];
and then you write to this array:
a[x] = v[j];
x++;
You never even reset x back to 0, anywhere. So basically, right from the start you are writing to unallocated memory, but the bigger your input set, the more unallocated memory you write to.
There could be other problems with your code. I definitely saw a whole bunch of other things that indicated an incorrect understanding of pointers, but they wouldn't necessarily cause a fatal error. Please at the very least get some kind of auto-indent program to make your code readable.