1 Replies - 282 Views - Last Post: 03 April 2013 - 03:19 PM Rate Topic: -----

#1 amanda3  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 28-March 13

what's wrong with my code? c programming

Posted 03 April 2013 - 03:08 PM

I wrote this program, it successfully compiles but when I run it I get a segmentation fault. Can anyone help me figure out why?
It's about the traveling salesman problem.
In this program I read an input file such as the following :
c 1
c 2
c 3
c 4
c 5
a 1 2 383
a 1 3 915
a 1 4 386
a 1 5 421
a 2 3 123
a 2 4 22
a 2 5 3456
a 3 4 956
a 3 5 170
a 4 5 434

where numbers in c from 1 to 5 represent the cities and the numbers in a represent the distances between those cities.
So the point of this program is to find a legal tour, a tour that costs the less.For example the tour 1 4 2 3 5 1 costs 6600.

Here's my code: what it does is read the input file and stores the cities' distances in a matrix.
Then it calls a function that generates the one tour starting from 1 to i number of cities. and then I try to find the smallest sum from all those tours generated.

#include <stdio.h>

int map[151][151] = {0};
int m = 0, sum = 0;
int boolArray[151] = {0};
int legal = 0;
int smallest;
int pArray[151] = {0};


void function(int S, int N) { // S is the starting and finishing city and N is the number of cities
  int b, k, z, y, x;
  
  if (m == N-1) {  // calculate the sum of the tour found 
    for (z=0; z < N; z++)
      sum += map[pArray[z]][pArray[z+1]];   
    return;
  }     
  x = S;
  if (legal == 0) { // store the starting city S in an array of index 0 and N
    pArray[m] = pArray[N] = x;
    boolArray[x] = 1; // check that city S is visited
    legal = 1;
  }
  
  y = 1;  // start comparing distances 
  if (y == x) y++;  
  else if (boolArray[y]) y++; 
  else {
    smallest = map[x][y];
    b = y;
  }    
  for (k=y+1; k<=N; k++) {
    if (k == x) continue;
    else if (boolArray[k]) continue;
    else if (map[x][k] < smallest) { 
      smallest = map[x][k];
      b = k;
    }
    else;
  }
  m++;
  pArray[m] = b;
  boolArray[b] = 1;
  function(b, N);
}

void inputCost (int n1, int n2, int n3) {
  map[n1][n2] = n3;
  map[n2][n1] = n3;
}
int main () {
  int i =0, num[150]={0}, n1, n2, n3;
  char type;
  int a, f, z, m, n;
  int d = 0;
  int tour[151] = {0};
  
  for (a=0; (scanf(" %c", &type) != EOF); a++) {
    switch (type) {
      case 'c': i++; scanf("%d", &num[i]); break;
      case 'a': scanf ("%d %d %d", &n1, &n2, &n3); 
                inputCost (n1, n2, n3); break;
      default : printf ("Please check your input file!\n");
      }    
    }
    
  for (f=1; f <=i; f++) {
    int boolArray[151] = {0};
  
    function(f, i);
      if (d == 0) {
        smallest = sum;
        for (z=0; z <= i; z++)
          tour[z] = pArray[z];
      }
      else if (sum < smallest) {
        smallest = sum;
        for (z=0; z <= i; z++)
          tour[z] = pArray[z];
      }
      else;
      d=1;
      legal = 0; 
      m = 0;
  }


return 0;
}


Is This A Good Question/Topic? 0
  • +

Replies To: what's wrong with my code? c programming

#2 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6092
  • View blog
  • Posts: 23,612
  • Joined: 23-August 08

Re: what's wrong with my code? c programming

Posted 03 April 2013 - 03:19 PM

Perhaps this might help:

Program received signal EXC_BAD_ACCESS, Could not access memory.
Reason: KERN_INVALID_ADDRESS at address: 0x00000001012e0e28
0x00000001000008b8 in function (S=32767, N=5) at am.c:16
16	      sum += map[pArray[z]][pArray[z+1]];   
(gdb) print z
$1 = 4
(gdb) print pArray[z]
$2 = 32767
(gdb) print pArray[z+1]
$3 = 1
(gdb) 



Do those values look sane?
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1