home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / lang / c / 18318 < prev    next >
Encoding:
Text File  |  1992-12-14  |  2.3 KB  |  108 lines
  1. Path: sparky!uunet!mcsun!sun4nl!and!jos
  2. From: jos@and.nl (Jos Horsmeier)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: travelling salesman
  5. Message-ID: <4219@dozo.and.nl>
  6. Date: 14 Dec 92 14:48:29 GMT
  7. References: <FARID.92Dec11140244@gradient.cis.upenn.edu>
  8. Organization: AND Software BV Rotterdam
  9. Lines: 97
  10.  
  11. In article <FARID.92Dec11140244@gradient.cis.upenn.edu> farid@gradient.cis.upenn.edu (Hany Farid) writes:
  12. |
  13. |I am looking for code that enumerates the (N-1)!/2 possible paths of
  14. |the travelling salesman for a map with N cities.  Any help would be
  15. |appreciated.  
  16.  
  17. Note that only the first (N-1)! of all N! permutations need to be generated
  18. (since it doesn't matter which city is the start/end point) Also not that,
  19. when the cities are numbered 0 ... N-1, when the city _next_ to the starting
  20. point has a lower rank than the last city of the tour, this particular tour
  21. must occur somewhere earlier in the list of permutations (but backwards.)
  22.  
  23. Maybe an example clarifies things a bit: Consider N= 4:
  24.  
  25. 1234, 1243, 1324, 1342 (not valid: 2 < 3), 1423 (not valid: 3 < 4),
  26. 1432 (not valid: 2 < 4)
  27.  
  28. So, 1234, 1243 and 1324 are the three possible tours for N= 4.
  29.  
  30. Also note that we can stop generating permutations when the city next
  31. to the starting point has the highest rank number.
  32.  
  33. The following program does the job for you:
  34.  
  35. -----8<-----snip----------snip----------snip----------snip----------snip-----
  36. #include <stdio.h>
  37.  
  38. #define N 6    /* or any number you want */
  39.  
  40. void print_perm(a) 
  41. int *a;
  42. {
  43.     int i;
  44.  
  45.     for (i= 0; i < N; i++)
  46.         printf("%d ", a[i]);
  47.     printf("\n");
  48.  
  49. }
  50.  
  51. int main(void) {
  52.  
  53.        int i, tmp, a[N], b[N];
  54.  
  55.     /*
  56.      * Set up first permutation 
  57.      */
  58.        for (i = 0; i < N; i++) 
  59.         a[i] = b[i] = i;
  60.  
  61.     print_perm(a);
  62.  
  63.     /*
  64.      * Keep on generating permutations
  65.      */
  66.        for (i = 0; i < N; i++) {
  67.  
  68.               if (b[i] < i) {
  69.             tmp = a[i]; 
  70.             a[i] = a[b[i]];
  71.             a[b[i]] = tmp;
  72.         }
  73.  
  74.               if (--b[i] >= 0) {
  75.  
  76.                  tmp = a[i]; 
  77.             a[i] = a[b[i]]; 
  78.             a[b[i]] = tmp; 
  79.  
  80.             /* 
  81.              * Test for the same route backwards 
  82.              */
  83.             if (a[N-2] > a[0])
  84.                 print_perm(a);
  85.             /*
  86.              * Done first (N-1)!/2 ?
  87.              */
  88.             else if (!a[N-2])
  89.                 break;
  90.  
  91.             /*
  92.              * Reiterate again 
  93.              */
  94.             i= -1;
  95.             continue;
  96.  
  97.               }
  98.               b[i] = i;
  99.        }
  100. }
  101. -----8<-----snip----------snip----------snip----------snip----------snip-----
  102.  
  103. I hope this helps a bit,
  104.  
  105. kind regards,
  106.  
  107. Jos aka jos@and.nl
  108.