5

土場で使うアプリケーションを書いています。ボードまたはビームの長さの数を考えると、目標は、無駄を最小限に抑えながら必要なボードの数を計算することです。たとえば、ある特定のディメンションについて、次のショッピングリストがあるとします。

3x2.9
メートル5x1.6メートル
21x0.9メートル

土場では、利用可能なボードの長さを確認し、アプリケーションに入力します。この寸法は4.8メートルの長さで利用可能であるとしましょう。

簡単なアプローチは、残りのボードを降順の長さに合わせてみることです。

2.9 + 2.9 = 5.8なので、4.8メートルのボードには収まりません。2.9+
1.6 = 4.5なので、問題ありません。

残りの0.3メートルより短い長さはないので、このボードは「フル」です。このタイプをさらに2つ装着すると、次の長さが残ります。

2x1.6メートル
21x0.9メートル

さて、このアルゴリズムはかなりうまく機能します。しかし、2.9 + 1.6をフィッティングする代わりに、2.9 + 0.9 + 0.9=4.7をフィッティングするとどうなるでしょうか。その後、0.3メートルではなく、ボードごとに0.1メートルの廃棄物が発生します。

考えられるすべての組み合わせを列挙する際の問題の1つは、各長さがボードに複数回表示される可能性があり、ボードに取り付けられる長さの数も異なることです。すべてのボードの無駄を最小限に抑えるために使用できる既知のアルゴリズムはありますか？

また、土場で2つ以上の長さが利用できる場合はどうなりますか？たとえば、5.4、4.8、3.6メートル？これは確かに物事を複雑にします。利用可能な長さごとに選択したアルゴリズムを実行し、無駄の少ない長さを選択できます。しかし、最も洗練されたソリューションでは、使用可能な長さを混合できるため、最適な答えは1x 5.4、3x 4.8、6x3.6のようになります。しかし、初心者にとっては、答えを1つの長さに制限することに満足しています。

4

2 に答える 2

3

無駄を最小限に抑えることは、実際にはNP完全である一般化されたサブセット和問題の最適化問題であり、したがって、この問題の既知の多項式時間解はありません。

NP完全ですが、動的計画法を使用するか、ナップザック（重み=値=長さ、W =ボードサイズ）に縮小してこの問題の疑似多項式解を生成し、その疑似多項式解を使用できます。これは非常によく似ています。

ただし、ここではさらに注意が必要です。疑似多項式の解は整数を想定していますが、例ではそうではないことを示しています。固定小数点演算を使用して長さを表すことで解決できます（つまり、長さごとにドットの後に1桁しか使用しない場合、4.8は48として表示され、ドットの後に2桁を使用する場合は、480になります。 ...）。

注：このアルゴリズムは無駄を最小限に抑えますが、無駄を最小限に抑えるための「ログの最小数」を保証するものではありません。

いずれにせよ、解決策を見つけることはNP困難であるため、ログの使用量が最も少ない解決策を見つけることもNP困難です。

于 2012-05-03T13:20:06.940 に答える
2

あなたの特定の問題は、いわゆる「カッティングストック」クラスの問題の変形です。ウィキペディアの「板取り問題」（CSP）ページをご覧ください

私は、板取り問題のより単純なバージョンの平易な英語でのこの説明が好きです。AIMMSから：

「板取り問題：各決勝戦の需要を考慮して、材料の長いロール（生と呼ばれる）を所定のサイズの小さなロール（決勝戦と呼ばれる）にカットする方法。」

AIMMSによるこのpdfは良いです。

研究者が思いついた基本的なカッティングストック問題にはかなりの数のバリエーションがあることに注意してください。これらの整数計画法の講義では、一般化されたカッティングストック問題の適切な定式化について説明しています（17ページを参照） 。

これらのMILP問題は、目的関数と制約が標準CSPの基本パターンに従っているため、定式化するのはそれほど難しくありません。それらを効率的に解決するための技術に関する膨大な研究が存在します。

CPLEX、R、またはExcelソルバー（小さな問題の場合）などのLP / IPソルバーにアクセスできる場合は、問題を定式化してこれらのソルバーで試す価値があります。

お役に立てば幸いです。

于 2012-05-03T19:56:50.620 に答える