algorithm - カット最適化アルゴリズム

Question

私と大学の何人かの友人は、ある種の材料から長方形の部品を切断する最適化のためのネット アプリケーションを開発するという実際的なタスクを割り当てられました。このリストのアプリのようなものですが、より単純化されています。基本的に、この種の最適化アルゴリズムのソース コードがインターネットで入手できるかどうかに興味があります。Adobe Flex フレームワークを使用してアプリを開発する予定です。プログラミングの部分は Actionscript 3 ofc で行われます。ただし、この言語の最適化サンプルがあるとは思えません。ただし、Java、C++、C#、Ruby、Python、およびその他のより一般的な言語用のものがあるかもしれません (その場合は、AS で書き直す必要があります)。ですから、私に合う無料のライブラリやアルゴリズム コードのサンプルを誰かが知っている場合は、あなたの提案を聞きたいです。:)

Answer 1

これは非常に難しいストックカットの問題のように聞こえます! 最良の解決策は、線形計画法 (通常はシンプレックス法に基づく) と列生成を使用します (これは、何年にもわたって制約を解決する研究プロジェクトを行った後でも、半分まともな説明をする能力がないと感じています)。要するに、Actionscript でこのアプローチを試したくないでしょう。したがって、何を実装しても、小さな問題以外に大きな結果を期待するべきではありません。

私が提供できる最善のアドバイスは、ソースの四角形をストリップ (必要な最大の四角形の幅のそれぞれ) にカットできるかどうかを確認し、「ヘッド」の四角形が削除された後、各ストリップの残りを細分化することです。 .

最適化戦略として分岐限定を使用することをお勧めします。BnB は、これまでに見られた最良のソリューションを追跡する徹底的なツリー検索を行うことによって機能します。解が見つかったら、境界を更新し、バックトラックして次の解を探します。検索の結果、見つけた最善の解決策よりも優れた解決策にはつながらないとわかっているブランチにたどり着くことがわかっている場合はいつでも、その時点で早い段階で後戻りできます。

これらの検索ツリーは非常に大きくなるため、おそらく検索に時間制限を設けて、最善の努力を返したいと思うでしょう。

お役に立てれば。

Answer 2

私が働いている木工会社で同じことをしたいと思ったとき、私は例を見つけるのに苦労しました. 問題自体は NP 困難であるため、最初の適合または最適な適合アルゴリズムのような近似アルゴリズムを使用する必要があります。2D ビン パッキング アルゴリズムを検索します。私が見つけたものは、パネルを最大から最小に並べ替えてから、シートに順番に追加し、最初に収まるビンに入れます。申し訳ありませんが、私と一緒にコードを持っていません。とにかくvb.netにあります。