home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / sys / mac / programm / 14868 < prev    next >
Encoding:
Internet Message Format  |  1992-09-01  |  1.4 KB
  1. Path: sparky!uunet!usc!hacgate!lyra!root
  2. From: root@lyra.scg.hac.com (Dave Fisher)
  3. Newsgroups: comp.sys.mac.programmer
  4. Subject: Re: Packing Rects into the smallest possible container
  5. Summary: Check out VLSI journals
  6. Message-ID: <23118@hacgate.SCG.HAC.COM>
  7. Date: 1 Sep 92 23:10:02 GMT
  8. Sender: news@hacgate.SCG.HAC.COM
  9. Reply-To: fisher@lyra.hac.com (Dave Fisher)
  10. Organization: Hughes Aircraft Co., Carlsbad, CA
  11. Lines: 23
  12.  
  13. The "knapsack" problem is close; but a perfect fit of your problem
  14. is the VLSI problem called "2-D placement" or "bin packing".
  15.  
  16. Many algorithms have been published.  There are approaches that
  17. use optimization techniques, such as "greedy algorithms", "genetic
  18. algorithms", "spin-glass" (this one looked excellent but difficult),
  19. "simulated annealing", etc.  There have also been heuristic rule-based
  20. systems, straight algorithms, etc.
  21.  
  22. The best source for info is probably the conference proceedings for
  23. the "Design Automation Conference" (DAC), published annually.  Also try
  24. the journal called "VLSI".  Or ask a local VLSI CAD expert for some
  25. good references.
  26.  
  27. If you end up writing your own algorithm, here are a couple of tips:
  28. 1. Place larger blocks first
  29. 2. Try to find groups of 2 or more blocks which have a common width
  30.    or length and line them up -- this is very efficient.  
  31. 3. Allow for switching things around randomly, to try different possibilities.
  32. 4. Watch out for getting stuck in "local minima" if using #3.
  33.  
  34. Good luck!
  35. Dave
  36.