我和几个大学朋友被分配了一个实际任务：开发一个网络应用程序，以优化从某种材料中切割矩形部件。这类似于此列表中的应用程序，但更简化。基本上，我想知道在互联网上是否有这种优化算法的源代码。我计划使用Adobe Flex框架开发应用程序。编程部分将使用Actionscript 3完成。然而，我怀疑这种语言没有任何优化样例。虽然可能有一些适用于Java、C++、C#、Ruby或Python等更流行语言的优化示例（那么我只需要将其重写为AS）。因此，如果有人知道任何适合我的免费库或算法代码示例，我想听听您的建议。 :)
2个回答
6
这听起来就像股票切割问题，非常难！最好的解决方案使用线性规划（通常基于单纯形法）和列生成（即使在约束求解研究项目上多年后，我仍感到无法给出一个半可靠的解释）。简而言之，在Actionscript中您不会想尝试这种方法；因此，无论您实现什么，除了小问题以外，您都不应该期望获得很好的结果。
因此，我能提供的最好建议是看看是否可以将源矩形切成条带（每个条带的宽度为您需要的最大矩形的宽度），然后在“头”矩形被移除后细分每个条带的其余部分。
我建议将分支限界作为您的优化策略。BnB通过进行详尽的树搜索来跟踪迄今为止看到的最佳解决方案。当您找到解决方案时，请更新边界，并回溯寻找下一个解决方案。每当您知道您的搜索将带您到一个分支，您知道该分支不能导致比您已经找到的最佳解决方案更好的解决方案时，您可以在该点早期回溯。
因此，我能提供的最好建议是看看是否可以将源矩形切成条带（每个条带的宽度为您需要的最大矩形的宽度），然后在“头”矩形被移除后细分每个条带的其余部分。
我建议将分支限界作为您的优化策略。BnB通过进行详尽的树搜索来跟踪迄今为止看到的最佳解决方案。当您找到解决方案时，请更新边界，并回溯寻找下一个解决方案。每当您知道您的搜索将带您到一个分支，您知道该分支不能导致比您已经找到的最佳解决方案更好的解决方案时，您可以在该点早期回溯。
由于这些搜索树将非常庞大，您可能希望在搜索上设置时间限制，并返回您的最佳努力。
希望这可以帮到您。
- Rafe
2
我曾经在为我所工作的木工公司做同样的事情时遇到了困难。这个问题本身是NP-hard的，所以你需要使用近似算法，比如第一适配算法或最佳适配算法。 搜索2d装箱算法。我找到的算法是，按从大到小的顺序排序面板，然后按顺序将它们添加到板材中，在第一个适合的箱子中放置。抱歉我没有代码，并且它是vb.net。
- Kratz
5
虽然这个链接可能回答了问题，但最好还是在这里包含答案的重要部分并提供链接供参考。如果被链接的页面发生变化，仅有链接的答案可能会失效。-【来自审查】 - Mario Petrovic
1@MarioPetrovic：这是一个奇怪的评论原因，因为帖子中没有包含链接。我猜你的意思是答案建议搜索某些内容，这有点像包含链接但实际上没有链接吗？ - Jeremy Caney
我猜本来应该是一篇评论，但我误把它当成了一篇评论。我的错。 - Mario Petrovic
1@MarioPetrovic 这个问题本身应该被关闭，因为它在询问软件推荐。 - Rob
是的，那很有道理。 - Mario Petrovic
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接