home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / lang / c / 18274 < prev    next >
Encoding:
Internet Message Format  |  1992-12-12  |  1.5 KB
  1. Path: sparky!uunet!spool.mu.edu!olivea!charnel!sifon!thunder.mcrcim.mcgill.edu!mouse
  2. From: mouse@thunder.mcrcim.mcgill.edu (der Mouse)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: travelling salesman
  5. Message-ID: <1992Dec12.231813.1257@thunder.mcrcim.mcgill.edu>
  6. Date: 12 Dec 92 23:18:13 GMT
  7. References: <FARID.92Dec11140244@gradient.cis.upenn.edu>
  8. Organization: McGill Research Centre for Intelligent Machines
  9. Lines: 39
  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.
  15.  
  16. This really isn't a C question; it's a general algorithms question.
  17. However, since the code is trivial and it's likely to be the easiest
  18. and quickest way to get this thread off of comp.lang.c,
  19.  
  20.     int cities[N]; /* holds city numbers, 0..N-1 */
  21.     int taken[N]; /* holds booleans */
  22.  
  23.     void enumerate(int depth)
  24.     {
  25.      if (depth < 0)
  26.       { /* we have a new path in cities, do something with it */
  27.       }
  28.      else
  29.       { for (cities[depth]=0;cities[depth]<N;cities[depth]++)
  30.          { if (!taken[cities[depth]])
  31.         { taken[citites[depth]] = 1;
  32.           enumerate(depth-1);
  33.           taken[citites[depth]] = 0;
  34.         }
  35.          }
  36.       }
  37.     }
  38. ....
  39.     ...enumerate(N-1)...
  40.  
  41. You can of course eliminate the recursion, but there's not much point;
  42. you recurse only N levels, and if N is large enough that this is likely
  43. to cause problems, you aren't going to finish the list before your
  44. computer crumbles into dust from age anyway.
  45.  
  46.                     der Mouse
  47.  
  48.                 mouse@larry.mcrcim.mcgill.edu
  49.