3

シンプルな最適化を行うアルゴリズムを設計する必要がありますが、「最小限の変更」機能を備えています。容量が 10 個のコンテナーが 3 つあり、その中に次のアイテムがあるとします。

Container 1: 2 3 3
Container 2: 4 4
Container 3: 1 5 1 1

すべてのコンテナは 8/10 まで満たされています。次に、サイズ 3 の次のアイテムを配置します。全体の空き容量は 6 ですが、空き容量が 3 のコンテナーはありません。ここで、最初のコンテナーのサイズ 2 のアイテムは別の場所に配置されるため、新しいアイテムをコンテナー 1 に配置できます。これは、このソリューションでは (コンテナー 3 の 2 つのアイテムを置き換えるのではなく) 変更が 1 つしか必要ないためです。したがって、必要な結果は次のようになります。

Container 1: 3 3 3(new item)
Container 2: 4 4 2(moved from Container 1)
Container 3: 1 5 1 1

私はすでにいくつかの調査を行いました.ナップザックの問題またはバディアルゴリズムのいずれかしか見つかりませんでしたが、これらが本当に私が探しているものであるかどうかはわかりません.

このアルゴリズムをできるだけシンプルに設計するのを手伝ってくれる人はいますか? 少量の大きなコンテナと大量のアイテムが含まれる状況を解決しているため、すべての可能性を列挙することは最適ではありません。

どうもありがとう！

更新私が何を求めているのかを明確にするために-1つの変更のみを行うことで状況を解決できるかどうかを判断することは問題ありません。問題は、「一手」が不可能な場合に、どのようにして最小限の代替品を見つけるかということです。

4

2 に答える 2

1

これは質問に対する回答ではありませんが、コメントするには長すぎます。ここで述べた問題は NP 完全であり (決定問題に適切に変更すると)、PARTITION 問題から還元できます。

x 1 , x 2 , ..., x nを PARTITION 問題のインスタンスとします。表記のために、x 1を x の最小サイズとし、W をすべての x の合計とします。さらに、簡単にするために、W が偶数であると仮定します。

与えられた問題のインスタンスを構築して、次のように PARTITION インスタンスをエンコードします。サイズ W、W/2-x 1、および x 1の 3 つのコンテナーがあります。最初に、最初のコンテナーにはサイズ x 1、x 2、...、x nの項目が含まれ、他の 2 つは空です。挿入する新しいアイテムはサイズ W/2 です。元のPARTITIONの問題に解決策がある場合にのみ、この新しいアイテムをこれらのコンテナーに挿入できることがわかります。

追加するために編集されました（より多くの証拠の詳細）

最初に、元の PARTITION 問題の解決策があると仮定します。つまり、x を 2 つのサブセット S 1と S 2に分割し、各サブセットの x の合計が W/2 になるようにします。S 1に最小要素x 1が含まれているとします。次に、x 1を 3 番目のコンテナーに移動し、S 1の他のすべての要素を2 番目のコンテナーに移動して、新しいアイテム用に最初のコンテナーに W/2 のスペースを残すことができます。

次に、新しい W/2 サイズの要素をこれらのコンテナーに挿入する何らかの方法があるとします。検査によると、これが発生する唯一の方法は、最初のコンテナーにスペースを作ることです。そして、これが起こる唯一の方法は、正確に W/2 相当のアイテムを最初のコンテナーから移動する (そして、正確に W/2 相当のアイテムを残す) ことです。明らかに、これはアイテムの元のセットを 2 つのサブセットに分割し、各サブセットのサイズが W/2 になるように定義します。

さて、この問題が NP 完全であるからといって、すべてが失われるわけではありません。これは単純に、すべてのインスタンスを多項式時間で解決するソリューションを思いついたと思われる場合は、その作業を確認する必要があることを意味します。表示されるインスタンスのタイプの構造 (例: 「少量の大きなコンテナーとその中の大量のアイテム」) は、有用なヒューリスティックの検索をガイドするのに役立つ場合があります。

于 2015-12-08T01:24:10.190 に答える
0

これらのコンテナが最初から構築されている場合、状態を追加して、どれが最も充填されていないかを示し、常に次のアイテムをそこに置くことができます。

コンテナのサイズをコンテナ内からコンテナ外に削除できれば、これはより簡単になる可能性があります。

ちょうど私の2セント。

于 2015-12-07T20:11:28.810 に答える