切割优化算法

Question

我和我的一些在大学的朋友被分配了一个实际任务，开发一个网络应用程序，用于优化从某种材料切割矩形部件。像this列表中的应用程序，但更简单。基本上，如果在互联网上有这种优化算法的源代码，我很感兴趣。我计划使用Adobe Flex框架开发应用程序。编程部分将在Actionscript 3中完成。但是，我怀疑这个语言是否有任何优化样本。但是，对于Java，C++，C＃，Ruby或Python以及其他更流行的语言，可能会有一些（然后我只需要在AS中重写它）。所以，如果有人知道任何适合我的免费库或算法代码示例，我想听听你的建议。 :)

Answer 1

这可能是矫枉过正你所需要的，但下面的链接描述了一种方法，提供了很好的结果这种类型的问题：

http://www.intechopen.com/articles/show/title/a_greedy_algorithm_with_forward-looking_strategy

没有可用的代码，但该算法足够详细地描述它不难实现。我已经使用C＃实现了这一点（抱歉，无法分享该代码），并对结果感到非常满意。

Answer 2

当我想为我工作的木工公司做同样的事情时，我遇到了困难。问题本身是NP难的，所以你需要使用一个近似算法，如第一个拟合或最佳拟合算法。 搜索2d装箱算法。我找到的那个，你将面板从最大到最小排序，然后按顺序将它们添加到表单中，放入适合的第一个bin。对不起，没有与我和它在vb.net的代码无论如何。

Answer 3

这听起来就像stock cutting problem这是非常辛苦！最好的解决方案使用线性编程（通常基于单纯形法）和列生成（即使经过多年的约束解决研究项目，我感觉没有给出一半体面的解释）。总之，你不会想在Actionscript中尝试这种方法;因此，无论你实施的是什么，除了小问题之外，你不应该期望得到很好的结果。

然后，我可以提供的最好建议是查看是否可以将源矩形切成条（每个需要的最大矩形的宽度），然后将每个条的其余部分细分为“头”矩形已被删除。

我建议使用分支定界作为优化策略。 BnB通过彻底搜索树来追踪目前所见的最佳解决方案。当您找到解决方案时，请更新绑定并回溯寻找下一个解决方案。每当你知道你的搜索将你带到一个你认为不能找到比你找到的最好解决方案更好的解决方案的分支时，你可以在那个时候提前回溯。

由于这些搜索树将会非常大，因此您可能希望在搜索中放置一个时间限制并返回最佳效果。

希望这会有所帮助。