1

製造環境で使用する学校用の簡単なソフトウェアの開発を依頼されました。

これがシナリオです：

サイズのリストが表示されます。各サイズはボードを反映しているため、たとえば、24 "x 30"のボード、30 "x 30"、30"x48"などがあります。これらのボードは、原材料を切断するプロセスの副産物です。

原材料は、60"x120"と48"x96"の2種類のボードサイズで提供されます。

彼らは、原材料からボードを切り取る最良の方法を知りたがっています。「最良の」方法とは、原材料と残留物の量が最も少ない方法と定義されています。彼らはまた、使用される原材料の量を知りたいので、例えば、60"x120"の30枚のボードと48"x96"の3枚のボードです。

ボードは水平または垂直にカットできます。つまり、24"x30"は24"x30"または30"x24"のいずれかにカットできます。

全体で50枚のボードが与えられた場合（同じサイズの場合もあります）、2 ^ 50の異なる組み合わせを使用できます。これは、何千もの異なるボードサイズでソフトウェアを実行するため、長すぎるようです。

このシナリオに合うかもしれないアルゴリズムを誰かが知っているのだろうか。

ありがとう！

4

3 に答える 3

3

長方形の2D切断およびパッキング問題の古典的な単純なアルゴリズムは、Wangのアルゴリズムです。

ただし、純粋なWangのアルゴリズムでは、最適なギロチンカットパターン、つまり、すべてのカットが残りの材料の一方のエッジから反対側のエッジまで移動するパターンを生成できます。次のような非ギロチンパターンを生成することはできません

+---------+---+
|         |   |
+---+-----+   |
|   |     |   |
|   |     |   |
|   +-----+---+
|   |         |
+---+---------+

それでも、多くのアプリケーションでは、ギロチンカットパターンで十分であると考えられています。したがって、そのアルゴリズムを検討することをお勧めします（非常に単純であるため）。

シミュレーテッドアニーリング技術に基づく近似ランダム化アルゴリズムもあります（詳細な説明は、非ギロチンパターンを生成できるVLSIデザインブックのシミュレーテッドアニーリング（ネット上では見つかりません）にあります）。

いずれにせよ、そのような問題の正確な解決策を見つけるには、通常、多種多様な可能性のあるバリアントを生成および分析するためにかなりの量の計算が必要であり、ほとんどの場合、それは非現実的です。ほとんどの場合、人々ははるかに高速に動作する優れた近似/ヒューリスティックアルゴリズムに固執することを好みます。Wangのアルゴリズムは、検索を高速化する多数のヒューリスティックフィルターを使用してカスタマイズできます（最適なソリューションを失い、「ほぼ」最適なソリューションに置き換えるリスクがあります）。

于 2012-07-19T05:29:15.883 に答える
0

最初に頭に浮かぶのは、ビンパッキングアルゴリズムを使用して、特定の原材料からできるだけ多くのボードをパックできることです。

また、遺伝的アルゴリズムを試して使用し、最適な切断パターンを検索することもできます。GAは、ビンパッキングアルゴリズムと同じくらい常に効果的である可能性があります（そうでない可能性もあります）が、GAでの実行時間を指定できるため、たとえば、一定時間後に最適なソリューションを選択します。

とはいえ、工場は同じサイズの材料でバッチ処理を行う傾向があると思うので、実際の切断が行われる前に（おそらく遅い）ビンパッキングアルゴリズムを実行できるようにするのが最善かもしれません。

于 2012-07-19T05:18:33.090 に答える
0

これは難しい問題であり、板取り問題と非常によく似ています。ビンパッキング問題も参照してください。

于 2012-07-19T05:19:42.680 に答える