裁剪优化算法
我和我的一些大学朋友被分配了一项实际任务，即开发一个网络应用程序，以优化从某种材料中切割矩形零件。类似此列表中的应用程序，但更简单。基本上，我感兴趣的是互联网上是否有此类优化算法的源代码。我计划使用 Adobe Flex 框架开发该应用程序。编程部分将在 Actionscript 3, ofc 中完成。但是，我怀疑这种语言是否有任何优化示例。不过，可能有一些适用于 Java、C++、C#、Ruby 或 Python 以及其他更流行的语言（然后我只需要用 AS 重写它）。因此，如果有人知道任何适合我的免费库或算法代码示例，我想听听您的建议。 :)
Me and some of my friends at college were assigned a practical task of developing a net application for optimization of cutting rectangular parts from some kind of material. Something like apps in this list, but more simplistic. Basically, I'm interested if there is any source code for this kind of optimization algorithms available on the internet. I'm planning to develop the app using Adobe Flex framework. The programming part will be done in Actionscript 3, ofc. However, I doubt that there are any optimization samples for this language. There may be some for Java, C++, C#, Ruby or Python and other more popular languages, though(then I'd just have to rewrite it in AS). So, if anyone knows any free libs or algorithm code samples that would suit me, I'd like to hear your suggestions. :)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这听起来就像库存切割问题，极其困难！最好的解决方案使用线性编程（通常基于单纯形法）和列生成（即使在约束解决研究项目多年之后，我也觉得没有能力给出半体面的解释）。简而言之，您不会想在 Actionscript 中尝试这种方法；因此，无论你实施什么，除了小问题之外，你不应该指望得到好的结果。
那么，我能提供的最好建议是看看是否可以将源矩形切成条（每个您需要的最大矩形的宽度），然后在删除“头”矩形后细分每个条的剩余部分。
我建议使用分支定界作为优化策略。 BnB 的工作原理是进行详尽的树搜索，跟踪迄今为止看到的最佳解决方案。当找到解决方案时，更新边界，然后回溯寻找下一个解决方案。每当您知道您的搜索将您带到一个分支，而您知道该分支无法带来比您找到的最佳解决方案更好的解决方案时，您可以在那时尽早回溯。
由于这些搜索树非常大，因此您可能希望对搜索设置时间限制，并尽最大努力返回。
希望这有帮助。
This sounds just like the stock cutting problem which is extermely hard! The best solutions use linear programming (typically based on the simplex method) with column generation (which, even after years on a constraint solving research project I feel unequipped to give a half decent explanation). In short, you won't want to try this approach in Actionscript; consequently, with whatever you do implement, you shouldn't expect great results on anything other than small problems.
The best advice I can offer, then, is to see if you can cut the source rectangle into strips (each of the width of the largest rectangles you need), then subdivide the remainder of each strip after the "head" rectangle has been removed.
I'd recommend using branch-and-bound as your optimisation strategy. BnB works by doing an exhaustive tree search that keeps track of the best solution seen so far. When you find a solution, update the bound, and backtrack looking for the next solution. Whenever you know your search takes you to a branch that you know cannot lead to a better solution than the best you have found, you can backtrack early at that point.
Since these search trees will be very large, you will probably want to place a time limit on the search and just return your best effort.
Hope this helps.
当我想为我工作的木工公司做同样的事情时，我很难找到例子。该问题本身是 NP 困难的，因此您需要使用近似算法，例如首次拟合或最佳拟合算法。
搜索 2d bin-packing 算法。我找到的，您将面板从大到小排序，然后按顺序将其添加到纸张中，放入第一个适合的箱子中。抱歉，我没有代码，而且它在 vb.net 中。
I had trouble finding examples when I wanted to do the same for the woodwoorking company I work for. The problem itself is NP-hard so you need to use an approximation algorithm like a first fit or best fit algorithm.
Do a search for 2d bin-packing algorithms. The one I found, you sort the panels biggest to smallest, then add the to the sheets in in order, putting in the first bin it will fit. Sorry don't have the code with with me and its in vb.net anyway.