home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / lisp / 2845 < prev    next >
Encoding:
Internet Message Format  |  1992-11-10  |  1.1 KB
  1. From: Kirt.Undercoffer@f615.n109.z1.fidonet.org (Kirt Undercoffer)
  2. Sender: Uucp@blkcat.UUCP
  3. Path: sparky!uunet!blkcat!Uucp
  4. Newsgroups: comp.lang.lisp
  5. Subject: Satisfiability program available, common lisp
  6. Message-ID: <721425616.AA00000@blkcat.UUCP>
  7. Date: Tue, 10 Nov 1992 12:17:14 -0500
  8. Lines: 15
  9.  
  10.  DP> I'm very interested in "in practice" kinds of instances.  I wonder how
  11.  DP> hard the NP-complete instances that actually arise in areas outside of
  12.  DP> CS theory really are.
  13.  
  14.  DP> If you'd like to trade "hard" instances, let me know.
  15.  
  16. A real project at the Department of Agriculture gave rise to the Traveling
  17. Salesman Problem.  The project was a dBase or Clipper implementation of a
  18. varient of TSP - given n people and x locations and z,c,v constraints what is
  19. the optimum path during their day they need to take to visit a series of points?
  20.  Even with a realtively low number of constraints this problem was practically
  21. unsolveable as originally formulated (obviously - the program churned for three
  22. days or so to produce a path for one person - later the problem was
  23. simplified).
  24.  
  25.