<div>On Fri, Apr 30, 2010 at 3:10 PM, James Morris <span dir="ltr"><<a href="mailto:james@jwm-art.net" target="_blank">james@jwm-art.net</a>></span> wrote:<blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; ">
<a href="http://stackoverflow.com/questions/2746590/fast-block-placement-algorithm-advice-needed" target="_blank">http://stackoverflow.com/questions/2746590/fast-block-placement-algorithm-advice-needed</a></blockquote><div>
 </div></div>Sounds implicitly, NP-Hard, and complexity-equivalent of computing a minimum spanning tree ( <meta http-equiv="content-type" content="text/html; charset=utf-8"><a href="http://en.wikipedia.org/wiki/Minimum_spanning_tree">http://en.wikipedia.org/wiki/Minimum_spanning_tree</a> ) or various packing problems ( <meta http-equiv="content-type" content="text/html; charset=utf-8"><a href="http://en.wikipedia.org/wiki/Packing_problem">http://en.wikipedia.org/wiki/Packing_problem</a> <meta http-equiv="content-type" content="text/html; charset=utf-8"><a href="http://en.wikipedia.org/wiki/Bin_packing_problem">http://en.wikipedia.org/wiki/Bin_packing_problem</a> ).<div>
<br><div><div><div><div>Typical solutions include greedy approximation algorithms like  <a href="http://en.wikipedia.org/wiki/Bin_packing_problem#First-fit_algorithm">http://en.wikipedia.org/wiki/Bin_packing_problem#First-fit_algorithm</a> . ... Consider also that this same class of problem is  routinely solved in nature in linear time, and often in less than an eyeblink. Therefore consider heuristics that nature might use to solve such problems, such as <a href="http://en.wikipedia.org/wiki/Simulated_annealing">http://en.wikipedia.org/wiki/Simulated_annealing</a> or the similar concept of "soap-bubble-computer" ( <a href="http://en.wikipedia.org/wiki/Surface_tension#Liquid_surface_as_a_computer">http://en.wikipedia.org/wiki/Surface_tension#Liquid_surface_as_a_computer</a> ).</div>
<div><br></div><div>You mention "Bin Packing algorithms: their emphasis on optimal fit does not match the requirements of this algorithm."</div><div><span class="Apple-style-span" style="font-family: Arial, 'Liberation Sans', 'DejaVu Sans', sans-serif; font-size: 14px; border-collapse: collapse; line-height: 18px; ">The first-fit algo is one of many </span><span class="Apple-style-span" style="font-family: Arial, 'Liberation Sans', 'DejaVu Sans', sans-serif; font-size: 14px; border-collapse: collapse; line-height: 18px; "><a href="http://en.wikipedia.org/wiki/Approximation_algorithm">http://en.wikipedia.org/wiki/Approximation_algorithm</a></span><span class="Apple-style-span" style="font-family: Arial, 'Liberation Sans', 'DejaVu Sans', sans-serif; font-size: 14px; border-collapse: collapse; line-height: 18px; "> used to solve these class of probems -- they are "optimizing" for fit, but as an approximation, they don't really have "an emphasis on optimal fit"; they have an emphasis on completing their computation before the universe ends. :-)</span></div>
<div><br></div><div>Niels<br><a href="http://nielsmayer.com" target="_blank">http://nielsmayer.com</a><br></div>
</div></div></div></div>