travelling...

This is a discussion on travelling... within the C Programming forums, part of the General Programming Boards category; Has anybody here delt with the travelling salesman problem before? Woudl anybody know an algorithm or psuedocode for trying to ...

  1. #1
    Unregistered
    Guest

    travelling...

    Has anybody here delt with the travelling salesman problem before?
    Woudl anybody know an algorithm or psuedocode for trying to solve the travelling salesman problem.

    If anyone else has any other advice it would be much appreciated

  2. #2
    Unregistered
    Guest
    ?

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >Has anybody here delt with the travelling salesman problem before?
    Yes.

    >If anyone else has any other advice it would be much appreciated
    Web searches do wonders for finding algorithms and source code when you don't want to figure it out yourself.

    -Prelude
    My best code is written with the delete key.

  4. #4
    Unregistered
    Guest
    Well websearches produced nothing for me and all i wanted is a bit of help to get started.

  5. #5
    Unregistered
    Guest

  6. #6
    Unregistered
    Guest
    I hardly found anything useful, but i did find this piece of code which i am not really understanding well...

    Code:
    /*
     * This program checks the length of a tour.  Give the points data file
     * name on the command line.
     */
    #include <stdio.h>
    #include <math.h>
    
    typedef struct _point {
            float        x, y, z;
    } point;
    
    float distance (point v[], int i, int j) {
            float        dx, dy, dz;
    
            dx = v[i].x - v[j].x;
            dy = v[i].y - v[j].y;
            dz = v[i].z - v[j].z;
            return sqrt (dx*dx + dy*dy + dz*dz);
    }
    
    float tour_length (int tour[], point v[], int n) {
            int        i, from, to;
            float        sum;
    
            /* sum up distances between cities on the tour */
            
            sum = 0;
    
            /* start at city 0 */
    
            from = 0;
            for (i=1; i<n; i++) {
    
                    /* find distance to next city in tour */
    
                    to = tour[i];
    
                    /* add that to the length of the tour */
    
                    sum += distance (v, from, to);
    
                    /* the next source is the current target */
    
                    from = to;
            }
    
            /* add in the distance back to the first city */
    
            sum += distance (v, from, 0);
            return sum;
    }
    
    int main (int argc, char *argv[]) {
            char        present[1000];
            int        i, j, n, tour[1000];
            float        length, min;
            point        cities[1000];
            FILE        *f;
    
            if (argc != 2) {
                    fprintf (stderr, "Usage: %s <filename>\n", argv[0]);
                    exit (1);
            }
            f = fopen (argv[1], "r");
            if (!f) {
                    perror (argv[1]);
                    exit (1);
            }
            fscanf (f, "%d\n", &n);
            for (i=0; i<n; i++) {
                    fscanf (f, "%f %f %f\n", &cities[i].x, &cities[i].y, &cities
    [i].z);
            }
            fclose (f);
            bzero (present, n);
            for (i=0; i<n; i++) {
                    scanf ("%i", &tour[i]);
                    if (feof (stdin)) {
                            fprintf (stderr, "unexpected end of file!\n");
                            exit (1);
                    }
                    if (tour[i] >= 0 && tour[i] < n) 
                            present[i] = 1;
                    else {
                            fprintf (stderr, "index %d out of bounds!\n", tour
    [i]);
                            exit (1);
                    }
            }
            for (i=0; i<n; i++) if (!present[i]) {
                    fprintf (stderr, "not all points in tour, missing %d!\n", 
    i);
                    exit (1);
            }
            length = tour_length (tour, cities, n);
            printf ("length of tour is %f\n", length);
            exit (0);
    }
    Can anyone explian it to me?/

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. War with China
    By nickname_changed in forum A Brief History of Cprogramming.com
    Replies: 92
    Last Post: 08-18-2005, 12:31 PM
  2. Travelling through Norway and northern Sweden
    By Shiro in forum A Brief History of Cprogramming.com
    Replies: 0
    Last Post: 07-13-2002, 09:20 AM
  3. A Common Scientific Belief
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 10
    Last Post: 03-29-2002, 04:54 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21