0

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

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

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

有谁知道适合这个问题的替代技术？

我不知道......但我确信这类软件存在，所以有一种方法（我不知道）。

任何帮助表示赞赏，谢谢。

4

2 回答 2

1

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

我的第一个想法是以离散线性编程方式重新表述问题，这已经完成，如果您有访问权限，请参阅下面的参考资料。

Mhand Hifi、Imed Kacem、Stephane Negre、Lei Wu (2010)“三维装箱问题的线性规划方法”离散数学中的电子笔记，36, 993–1000

于 2013-10-29T00:40:08.723 回答
0

如果您还没有看过，我建议您看一下动态编程方法。您的问题听起来类似于典型的动态编程问题“切割布”问题。这是裁布问题：

裁布。给您一块尺寸为 XY 的矩形布，其中 X 和 Y 是正整数，以及可以使用该布制作的 n 个产品的列表。对于每个产品 i 2 [1; n] 您知道需要一块尺寸为 ai bi 的长方形布，并且该产品的最终售价为 ci。假设 ai、bi 和 ci 都是正整数。您有一台机器可以将任何矩形布片水平或垂直切成两块。设计一种算法，确定 XY 块布的最佳回报，即裁切布块的策略，以使由所得块制成的产品给出最大的销售价格总和。您可以随意制作任意数量的给定产品副本，如果需要，也可以不制作。

以下是我将裁布问题划分为子问题的方法：

V( i,j) = max { V(i - ai, j- bi ) + ci,
                V(i - bi, j - ai ) + ci
              }
于 2013-10-29T00:31:47.297 回答