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

Question

私と大学の私の友人のいくつかは、ある種の材料から長方形の部分をカットする最適化のためのネットアプリケーションを開発する実践的な課題を割り当てられました。 thisのアプリのようなものですが、もっと単純です。基本的には、この種の最適化アルゴリズムのソースコードがインターネット上にある場合は興味があります。私は、Adobe Flexフレームワークを使用してアプリケーションを開発する予定です。プログラミングの部分は、Actionscript 3、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

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

Answer 3

これはちょっとstock cutting problemのように聞こえますが、は非常に難しいです！最良の解決策は、線形プログラミング（通常はシンプレックス法に基づく）と列生成を使用します（数年後に研究プロジェクトを解決する制約を受けたにもかかわらず、まったく説明できないと感じます）。つまり、このアプローチをActionscriptで試してみることは望ましくありません。結果的に、あなたが実装するものは何でも、小さな問題以外には大きな成果を期待すべきではありません。

私が提供できる最良のアドバイスは、ソース矩形をストリップ（あなたが必要とする最大の矩形の幅）にカットしてから、 "ヘッド"の後に各ストリップの残りの部分を細分するか、長方形が削除されました。

最適化戦略としてbranch-and-boundを使用することをおすすめします。 BnBは、これまでに見られた最良のソリューションを追跡する網羅的なツリー検索を実行することによって動作します。ソリューションを見つけたら、バインディングを更新し、次のソリューションを探すバックトラックします。あなたが見つけた最高のものよりも優れたソリューションにつながることができないと分かっているブランチへの検索がわかっている場合は、その時点で早めにバックトラックすることができます。

これらの検索ツリーは非常に大きくなるため、検索に時間制限を設け、ベストエフォートを返すことをお勧めします。

これが役に立ちます。