6

次のような問題があるとしましょう:

  • ナップザックの容量 = 2,000 万
  • アイテム数 = 500
  • 各アイテムの重量は1億から2000万の間の乱数です
  • 各アイテムの利益は1～10の乱数

では、私の問題に最適な方法はどれですか? GAまたは動的計画法?

初心者なので簡単な説明をお願いします。...

4

4 に答える 4

3

動的計画法は、時間O(numItems * knapsackCapacity)とO(knapsackCapacity)メモリ内で実行できます。これは、あなたの仕様では、次のようになることを意味します。

  • 操作について20.000.000 x 500 = 10.000.000.000- マシンによっては、おそらく数時間で実行が終了します。
  • 1 つのアイテムの利益は最大で 10 であり、最大で 500 個のアイテムを持つことができるため、理論上の最大利益は を超えることはできません10 x 500 = 5000。これは 2 バイト (短) で表すことができます。2 x 20.000.000 / 1024 / 1024 ~= 38 MBしたがって、DP 配列を格納するためのメモリも必要になります。繰り返しますが、それほど多くはありません。

他の人は、それぞれの長所と短所をすでに述べています。GA の方が早く終了しますが、DP ソリューションも数時間で終了し、正確な答えが得られます。

個人的には、解決策が得られるまで数時間待つことが問題にならない場合は、DP を選択します。

注:O(knapsackCapacity)メモリで実行される DP は次のとおりです。

dp[i] = maximum profit obtainable for weight i
for i = 1 to numItems do
  for j = knapsackCapacity down to items[i].weight do
    dp[j] = max(dp[j], dp[j - items[i].weight] + items[i].profit)
于 2013-02-13T14:16:14.723 に答える
0

「最善」の方法はなく、それぞれに長所と短所があります。
この場合、見つかった解の最適性とのトレードオフが生じます。GA は、最良の解を見つけることを保証するものではありません。
そして、解を計算するために必要な時間/空間 - 動的計画法を使用すると、冗長な計算を節約できますが、最良の解 (または、おそらくすべての解) を見つけるために、可能なすべての組み合わせを少なくとも 1 回は計算する必要があります。

于 2013-02-13T08:31:36.307 に答える
0

まず、動的計画法を、答えが最適な答えになることを保証できる正確なアルゴリズムと見なす必要があります。一方、GA はヒューリスティックなアルゴリズムであり、通常は局所的な最適値に収束します。ナップザックが整数の場合、疑似線形 (O(capacity*number_of_items)) である動的プログラミング ソリューションがあります。あなたの場合、約1e10の操作とメモリが必要です。単一のコンピューターで実現可能なもの。したがって、最適な答えを見つけることが重要で、十分な時間 (数時間程度) がある場合は、動的計画法のアプローチを使用できます。それ以外の場合は、GA などのヒューリスティック アルゴリズムを使用することをお勧めします。

于 2013-02-13T08:37:27.750 に答える