7

材料の落下や無駄を最小限に抑えてネスティングしようとしています。

Table A

Qty Type Description Length

2   W    16x19       16'
3   W    16x19       12'
5   W    16x19       5'
2   W    5x9         3'


Table B

Type Description StockLength

W    16X19       20'
W    16X19       25'
W    16X19       40'
W    5X9         20'

私はグリーディ アルゴリズム、ビン パッキング、ナップザック、1D-CSP、ブランチ アンド バウンド、ブルート フォースなどを調べました。私はそれがカッティングストックの問題であると確信しています。これを実行するための関数を考え出すのに助けが必要です。ストックの長さは 1 つだけではなく複数あり、ユーザーはあまり一般的ではない長さの在庫を入力する場合があります。PHP で使用する関数またはアルゴリズムを考え出して、最適化された切断パターンと無駄を最小限に抑えて必要なストックの長さを考え出す際の助けをいただければ幸いです。

ありがとう

4

2 に答える 2

4

あなたの質問が「コードを教えてください」である場合、あなたは良い解決策を実行するのに十分な情報を与えていないのではないかと思います。この回答全体を読むと、その理由がわかります。

あなたの質問が「アルゴリズムを教えてください」であるならば、私はあなたが間違った場所で答えを探しているのではないかと思います。これはテクノロジー指向のサイトであり、アルゴリズム指向のサイトではありません。もちろん、プログラマーはアルゴリズムを理解していますが（たとえば、strlenループのすべての反復で同じ文字列を渡すのが非効率的である理由、または非常に短いリストを除いてバブルソートが適切でない理由）、ここでのほとんどの質問は「言語/フレームワークYを使用してAPIXを使用しますか？」

このような複雑なアルゴリズムの質問に答えるには、特定の種類の専門知識が必要です（多くの数学的能力を含みますが、これに限定されません）。オペレーションズリサーチの分野の人々は、私たちのほとんどがこれまでに経験した以上に、この種の問題に取り組んできました。これがこのトピックに関する入門書です。

現実世界の問題に対する実用的な解決策を見つけようとしているエンジニアとして、私は最初にこれらの質問に対する答えを得るでしょう：

  • 解決しようとしている平均的な問題インスタンスの大きさはどれくらいですか？一般的な問題はNP完全であるため（Jitamaroがすでに述べたように）、適度に大きな問題のインスタンスではヒューリスティックを使用する必要があります。小さな問題のインスタンスのみを解決する場合は、正確な最適値を見つけるアルゴリズムの実装を回避できる可能性がありますが、もちろん、大きな問題のインスタンスを解決するためにソフトウェアを使用しないようにユーザーに警告する必要があります。 。

  • 問題の複雑さを軽減するために使用できるパターンはありますか？たとえば、アイテムは常にまたはほとんど常に特定のサイズまたは数量で提供されますか？もしそうなら、一般的なシナリオのための高品質のソリューションを生み出すことに焦点を当てた欲張りアルゴリズムを実装することができます。

  • 最適性と計算効率のトレードオフは何ですか？良い答えだけが必要な場合は、最適な答えを提供するために精神的または計算上の労力を無駄にしないでください。情報は、コンピュータによって提供されたかどうかにかかわらず、必要なときに利用できる場合にのみ役立ちます。

  • あなたの顧客は高品質のソリューションにいくら払っても構わないと思っていますか？アルゴリズムが最小限に抑えられているために事実上すべての人が実行できるデータベースやWebプログラミングとは異なり（たとえば、SQLデータベースがクエリの結果を提供する正確な手順をコーディングすることはめったにありません）、オペレーションズリサーチには数学とエンジニアリングの両方のスキルが必要です。あなたがそれらの料金を請求していない場合、あなたはお金を失っています。

于 2011-07-14T17:19:47.377 に答える
2

これは、1d ビンパッキングのバリエーションのように見えます。最適なものを試してから、テーブルの別の並べ替えで試してみてください b. とにかく、最適の 3/2 には解が存在しません。これは NP 完全問題であるためです。ここに素晴らしいチュートリアルがあります: http://m.developerfusion.com/article/5540/bin-packing . 私は自分の問題を解決するためにたくさん使いました。

于 2011-07-14T00:53:00.927 に答える