割集优化算法

Question

我和我的一些大学朋友被分配了一个实际的任务，开发一个网络应用程序，用于优化从某种材料中切割矩形零件。有点像this list中的应用程序，但更简单。基本上，我感兴趣的是互联网上是否有这种优化算法的源代码。我计划使用Adobe Flex框架开发该应用程序。编程部分将在ActionScript3，ofc中完成。但是，我怀疑是否有针对该语言的优化示例。不过，可能有一些是针对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

这听起来就像stock cutting problem，它非常难！最好的解决方案使用线性编程(通常基于单纯形法)和列生成(即使在进行了多年的约束求解研究项目后，我也觉得无法给出一个像样的解释)。简而言之，您不会想在Actionscript中尝试这种方法；因此，无论您实现什么，除了小问题之外，您不应该期望获得好的结果。

因此，我能提供的最好的建议是，看看是否可以将源矩形切割成条形(每个最大矩形的宽度为您需要的宽度)，然后在移除"head“矩形后再细分每个条形的其余部分。

我建议使用分支定界作为您的优化策略。BnB的工作原理是进行详尽的树搜索，跟踪到目前为止看到的最佳解决方案。当您找到一个解决方案时，更新绑定，并回溯查找下一个解决方案。每当你知道你的搜索将你带到一个分支，你知道这个分支不能带来比你找到的最好的解决方案更好的解决方案，你可以在这一点上早期回溯。

由于这些搜索树非常大，您可能希望对搜索设置一个时间限制，然后返回您的最大努力。

希望这能有所帮助。

Answer 3

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