4

プロジェクトに取り組んでいると、この問題に遭遇しました。ここでは、問題の実際の領域外の用語で言い換えます (花火と形状の口径について話すことはできると思いますが、理解がさらに複雑になります)。それを解決するための（おそらくおおよその）アルゴリズムを探しています。

さまざまなサイズのn 個のコンテナーと、さまざまなサイズの職業とさまざまな色の m個のオブジェクトがあります (オブジェクトは多色になる可能性があるため、オブジェクトの色は本当にセットです)。

私の目的は、コンテナーごとにさまざまな色が最小限に抑えられるように、すべてのオブジェクトをコンテナーに収めることです (それが可能であることは既にわかっています)。「色の種類が最小限に抑えられている」とは、コンテナごとの異なる色の数の合計が最小限であることを意味します。

例。サイズ 2 の 2 つのコンテナと、{red}、{red, green}、{blue}、{blue, green} の色を持つ 4 つのオブジェクトがあり、それぞれのサイズは 1 です。最適なソリューションは [{red} 、{赤、緑}]、[{青}、{青、緑}]、合計の種類は 2+2=4 です。悪い解決策は [{red}, {blue}], [{red, green}, {blue, green}] で、合計の種類は 2+3=5 です。

私の推測では、ナップザックの問題よりも難しいように聞こえるので、この問題は NP 困難であると思います。オブジェクトの値は負の値に変換され、さらに同じコンテナー内の他のオブジェクトに依存します。しかし、おおよその解決策を得るために問題に取り組む方法については、私には良い考えがありません。とにかくそれは大歓迎です。

4

1 に答える 1

3

ビンパッキングまたはナップザック？

この問題は、ナップザックの問題よりもビンパッキングの問題と共通しているようです。ナップザック問題では、1 つのナップザックしか満たすことができませんが、それを超えてはならない容量があります。そして、入れるアイテムの合計値を最大化しながら、これを行う必要があります。ここでは、すべてのアイテムを使い切る必要はありません。

ただし、ビン詰めの問題では、それぞれに容量を持つ複数のビンがあります。すべてのアイテムをいくつかのビンに適合させながら、ビンの数を最小限に抑えることに関心があります。また、各ビンの容量の制約も考慮する必要があります。ナップザックとは異なり、ここではすべてのアイテムを使い切る必要があります。

あなたの場合、ビンの数を最小限に抑えようとしていますが、2 つ未満に収まらないだけです。また、すべてのオブジェクトを使い果たしたいと考えています。容量の制約についてはあまり言及されていませんが、それも尊重する必要があると思います。これまでのところ、ビン詰め問題とほとんど同じように見えます。また、追加の制約が 1 つあります。それは、各コンテナー内の色の数を最小限に抑えることです。

NPハード？

さて、私はそれが NP 困難であるというあなたの予感を共有し始めています。これには、ビンパッキングのすべての要素と 1 つの追加の制約があります。ビンパッキングからの削減は、たとえば、すべて赤く着色されたオブジェクトを持つインスタンスを使用することで、簡単に示すことができます。問題が NP にあることを示す必要があるだけです。つまり、多項式時間で結果を検証できることを示します。ほら、そこに非公式の証拠があります！

貪欲なヒューリスティック I

これは、役立つ可能性のある貪欲なヒューリスティックです。

表現: セットを使用する代わりに、長さkのビット シーケンスを検討してください。ここで、kは、使用している個別の色の数です。つまり、赤、緑、青の 3 色があるとします。[青] は 001、[緑、青] は 011、[赤] は 100 などと表します。

  1. 001、010、100、011、110、111 などの順序になる比較関数を使用して、色のビット シーケンスで項目を並べ替えます。このような比較関数 は、ビット シーケンスのハミング重みの重み付き関数として考案できます。とその実際の数値。

  2. 多くのカラー パターン (ビット シーケンス) は、多くのオブジェクトで共有される可能性が高いことに注意してください。これらのオブジェクトは、並べ替えられたリストに連続したオブジェクトとして表示されます。

  3. 並べ替えられたリストをトラバースして、同じカラー パターンの連続するアイテムを同じビンに割り当てます。単色から多色のアイテムに移行します。

  4. 各ビンの容量を使い果たすまで、この方法を続けます。

貪欲なヒューリスティック II

もう 1 つの方法は、逆の順序でビンの充填を開始することです。色の数が最も多いオブジェクトから始めます。連続するオブジェクトが収まる場合は、同じビンに再度入力します。より少ない色のアイテムに到達したら、その色が既にカバーされている既存のビンにそれらを合わせます.

結論

これらの 2 つのアプローチはどちらも最適ではありませんが、それはまだわかっていませんでしたか? 問題が NP 困難であることの非公式な証明をスケッチしました。

幸運を！

于 2012-04-21T06:33:46.627 に答える