algorithm - 回溯的替代方法

Question

我正在开发一个空间优化软件。它应该能够以最佳方式在更大的空间中布置小体积。有一些限制，例如一个体积不能移动或应该“躺在”另一个体积的内表面上，或者它不能被另一个体积覆盖，等等......

每个体积都表示为一个 3d 轴对齐边界框，或一组较小的 3d AABB(它们组装成一个更复杂的体积)。

我一直在考虑使用回溯来解决这个问题(尤其是分支定界技术)，但它在速度方面和在内存方面一样过于贪婪(即使是过度简化的使用)。

有谁知道可以解决这个问题的替代技术吗？

我不知道...但我确定存在此类软件，所以有一种方法(我不知道)。

感谢任何帮助，谢谢。

Answer 1

是的，这个问题有“解决方案”，而且它们是大型企业。很好地解决这个问题可以为你赚很多钱，因为它是 NP-hard 并且非常有用。 http://en.wikipedia.org/wiki/Bin_packing_problem

我的第一个想法是以离散线性规划方式重新表述问题，这已经完成了，如果您可以访问，请参阅下面的引用资料。

Mhand Hifi, Imed Kacem, Stephane Negre, Lei Wu (2010) “A Linear Programming Approach for the Three-Dimensional Bin-Packing Problem” 离散数学电子笔记, 36, 993–1000