Re:Algorithmic fitting of Japanese candy
by lotyrin on Thursday November 17, 2016 @12:00AM
(#12974463)
Yeah, simulated annealing as to the order to place objects in is probably optimal for non-trivial values of n. Also, determinism can often be important and stochastic doesn't have to mean non-deterministic - seed the RNG.
Re:Algorithmic fitting of Japanese candy
by kwhitefoot on Friday November 18, 2016 @03:30AM
(#12985251)
> seed the RNG
This is something that can't be repeated often enough! Especially when running unit tests.
The approach we used was to start with a greedy best-first approach (like what is done by the Python library the author is using), and then try to improve on it by exploring the space of neighboring solutions. A "neighbor" here can be created by a pairwise permutation of candies (or mirrors in our case) in the order in which you're trying to fit them in the box, or trying to fit the candy flat instead of upright, etc.
You can do a hill-climb, which means you keep going as long as you can find a better neighbor, or you can use simulated annealing, which accepts a degradation in the solution (to avoid getting stuck in a local optimum) with a certain probability. This probability decreases over time so that you can eventually converge to a solution. Simulated annealing will work better than hill-climb, but its stochastic nature means two runs of the program might give you two different solutions (our client thought that was a bug!).