3D装箱算法

Question

我正在寻找一个确定性的实现方式来实现任何3D装箱算法，即将许多小而不同的立方体放置在一个或多个更大的立方体中。解决方案可以与最优解有所不同。

它应该使用C、C++、Java、C#、IronPython、IronRuby或其他任何可以从.Net代码编译的语言编写。

我发现了这个C算法http://www.diku.dk/hjemmesider/ansatte/pisinger/3dbpp.c，但它没有旋转立方体以找到最佳匹配。我可以接受不将其倒置，但应支持水平旋转。

- Mouk

---

你声称正在寻找一个算法，但随后列出了编程语言。你是在寻找通用算法还是具体实现？ - Mads Elvheim

你想要最优解，还是一个相当不错的解决方案？这些长方体都是一样的吗？当你说旋转时，你指的是90度还是任意角度？ - Beta

@Mads-Elvheim：抱歉表述不够清晰。我需要一个具体的实现，可以直接调用。我发现很多论文使用整数线性规划或遗传算法来解决这个问题。但是我认为，对于这样一个常见的问题，一定有现成的实现。 - Mouk

@Kinopiko和Mouk，尝试将5个边长为1的正方形放入一个宽度为2.708的正方形中，然后再告诉我关于非90度角的情况。 - Beta

@Beta 确信了。有这样的算法吗？对我来说，90度旋转就足够了。 - Mouk

Answer 1

我已经用C ++为您描述的情况编写了一个近似算法，即3D矩形框，具有正交旋转。 您可以在已发布的论文中找到结果和算法： http://www.cs.ukzn.ac.za/publications/erick_dube_507-034.pdf

- user320450

---

源代码或C++应用程序是否在任何地方在线上可得到？ - Cole W

这对于一个简单的解决方案来说是不错的，但实际效果并不是很好。对于那些想要解释和帮助撰写的人，我建议阅读这本书：《背包问题》，作者是Martello和Toth，ISBN：0471924202。 - ars265

这个链接页面里找不到结果？这个URL还正确吗？ - Amr Elgarhy

@AmrElgarhy 从原始网址的名称来看，我猜测这篇论文是同一篇。 - psycho

Answer 2

我将wknechtel/3d-bin-pack的C代码转换为JavaScript。可以轻松移植到C#。

https://github.com/keremdemirer/3dbinpackingjs

你可以从index.html文件运行示例计算，并查看生成的报告。 pack1.js文件包含应用程序和算法。我不确定算法是如何工作的，但对于包装计算来说，结果令人满意。

- Kerem Demirer

Answer 3

这个问题是NP难的。你最好使用近似算法（直到某个天才解决了任何一个NP问题，或者一个非常幸运的家伙偶然发现了解决方案）。不幸的是，我不知道这个问题有什么著名的近似算法。

- ldog

---

在多项式时间内解决一个NP完全问题仍然不能为NP困难问题提供多项式解决方案 :) - BlueRaja - Danny Pflughoeft

对于小包裹来说，所需时间不是很长。因此，对于相当多的在线购物运输而言，暴力破解是一个公平的替代方案。 - ThomasRS

@ThomasRS 如果你愿意使用暴力方法，最好的选择是使用相应的整数线性规划(ILP)来表示问题，并将其输入到像gurobi这样的工具中，这样你会得到最好的效果。 - ldog

谢谢@idog，不过我已经编写了一个自定义实现，它进行了一些特定于应用程序的优化，例如考虑到相同尺寸的多个盒子等。 - ThomasRS