[prev in list] [next in list] [prev in thread] [next in thread] 

List:       ruby-talk
Subject:    Re: Ruby Quiz #62
From:       Ilmari Heikkinen <ilmari.heikkinen () gmail ! com>
Date:       2006-01-21 22:04:28
Message-ID: 854c25eb0601211404x1a47370bk3a7f0799e9a7348b () mail ! gmail ! com
[Download RAW message or body]

Hi,
On 1/19/06, Andrew Dudzik <adudzik@gmail.com> wrote:> I took a few shots at #62 and \
was unable to come up with anything that would> terminate in a reasonable amount of \
time. ("reasonable" = "overnight") I guess the computational complexity of an optimal \
solver is n!, whichwould make solving anything bigger than 10 boxes a feat. And since \
binpacking problem is strongly NP-hard, checking that a solution isoptimal would take \
non-polynomial time as well. A nice approach might be using neural nets / \
evolutionary algorithms /simulated annealing / some other funky optimization \
algorithm forfinding solutions that are better than what the greedy algorithmsgive, \
without taking years to run.

-Ilmari


[prev in list] [next in list] [prev in thread] [next in thread]