我和我在大学的一些朋友被分配了一项实际任务，即开发一个网络应用程序，以优化从某种材料切割矩形零件。类似于此列表中的应用程序，但更简单。基本上，我很感兴趣互联网上是否有这种优化算法的源代码。我计划使用 Adobe Flex 框架开发应用程序。编程部分将在 Actionscript 3, ofc 中完成。但是，我怀疑这种语言是否有任何优化示例。不过，可能有一些用于 Java、C++、C#、Ruby 或 Python 以及其他更流行的语言（然后我只需要在 AS 中重写它）。因此，如果有人知道任何适合我的免费库或算法代码示例，我想听听您的建议。:)
问问题
21439 次
2 回答
4
这听起来就像是非常困难的股票切割问题！ 最好的解决方案使用带有列生成的线性规划（通常基于单纯形法）（即使经过多年的约束解决研究项目，我也觉得无法给出一个半体面的解释）。简而言之，您不会想在 Actionscript 中尝试这种方法。因此，无论你做什么实施，除了小问题之外，你不应该期望在任何事情上都能取得好的结果。
那么，我能提供的最好建议是看看你是否可以将源矩形切割成条带（每个你需要的最大矩形的宽度），然后在“头部”矩形被移除后细分每个条带的其余部分.
我建议使用分支定界作为您的优化策略。BnB 通过进行详尽的树搜索来跟踪迄今为止看到的最佳解决方案。当您找到解决方案时，更新边界，并回溯寻找下一个解决方案。每当您知道您的搜索会将您带到一个您知道无法找到比您找到的最佳解决方案更好的解决方案的分支时，您可以尽早回溯。
由于这些搜索树将非常大，您可能希望对搜索设置时间限制并尽最大努力返回。
希望这可以帮助。
于 2010-12-05T22:20:01.900 回答
2
当我想为我工作的木工公司做同样的事情时，我很难找到例子。问题本身是 NP 难的，因此您需要使用近似算法，如第一次拟合或最佳拟合算法。搜索二维装箱算法。我找到的那个，你将面板从最大到最小排序，然后按顺序将它们添加到工作表中，放入第一个适合的垃圾箱。抱歉，无论如何我都没有代码，它在 vb.net 中。
于 2010-12-05T19:27:14.103 回答