1

より大きなリストからアクティビティのサブセットを選択するアルゴリズムを開発しようとしています。選択した場合、各アクティビティは一定量の固定リソースを使用します (つまり、選択したアクティビティの合計が総予算を下回っている必要があります)。複数の実行可能なサブセットが存在する可能性があり、それらから選択する手段は、選択されていない活動の機会費用の計算に基づいています。

編集:これが0-1 ナップザックの問題ではない理由が 2 つあります。

  • ナップサックでは、重み (つまり、消費されるリソース) に整数値が必要ですが、私のリソース消費 (つまり、ナップザックの用語では質量) は連続変数です。(明らかに、ある程度の精度を選択して必要なリソースを量子化することは可能ですが、ビンのサイズは非常に小さくする必要があり、ナップサックはO(2^n)W.
  • アプリオリに機会費用を計算することはできません。つまり、それぞれの活動の適合性を個別に評価することはできませんが、特定の一連の選択された活動の効用や、既存のリストに追加のタスクを追加することによる限界効用を評価することはできます。

私が行った調査では、素朴なアプローチが示唆されています。

パワーセットを定義するパワーセット
の各要素について、セットにない項目に基づいてその効用を計算します
最高の効用を持つ要素を選択します

ただし、実行時間と必要なメモリを高速化する方法があることは知っています。例えば：

  • パワーセットを完全に列挙するO(2^n)ことはできますが、リストを完全に列挙する必要はありません。予算を超えるタスクのセットを見つけたら、それ以上のタスクを追加するセットは実行不可能であり、拒否される可能性があることがわかっているからです。つまり、{1,2,3,4}が実行不可能な場合、 も実行可能です{1,2,3,4} U {n}。ここで、n は、より大きなリストに残っているタスクのいずれかです。
  • 私は義務を要約しているだけなので、タスクの順序は重要ではありません (つまり、実行可能であれば、 、 など{1,2,3}もそうです)。{2,1,3}{3,2,1}
  • 最終的に必要なのは選択されたセットだけなので、おそらく比較目的でこれまでに見つかった最高の効用値のみが必要です。
  • すべての実行可能なものを確認したと確信できる限り、リストの列挙を保持する必要はありません。（ただし、以前に計算された実行可能なサブセットのデューティ合計を維持すると、実行時間が短縮される可能性があると思います。）

優れた再帰アルゴリズムが機能すると確信していますが、疑似コードであっても、それを定義する方法がわかりません (おそらく、いくつかの言語で実装されるため、これが最も理にかなっています-おそらくプロトタイピング用の Matlab と、後でコンパイルされた言語)。

4

3 に答える 3

2

ナップサック問題はNP完全です。つまり、問題を効率的に解決する方法はありません。ただし、動的計画法を使用した疑似多項式時間ソリューションがあります。詳細については、ウィキペディアのセクションを参照してください。

ただし、最大効用が大きい場合は、近似アルゴリズムを使用する必要があります。そのような近似スキームの1つは、最大の効用/コストを持つアイテムを貪欲に選択することです。予算が大きく、各アイテムのコストが小さい場合、これは非常にうまくいく可能性があります。

編集：セットにないアイテムに関してユーティリティを定義しているので、単にコストを再定義することができます。コストを無効にしてから、すべての値が正になるようにすべてをシフトします。

于 2011-07-29T15:05:21.673 に答える
1

他の人が言及したように、ナップザックの問題のいくつかのインスタンスを解決しようとしています。理論的には運命づけられていますが、実際には、アルゴリズムのパフォーマンスを向上させるために多くのことを行う可能性があります. ここにいくつかの（乱雑に分類された）アイデアがあります：

  • バックトラッキングに注意してください。{1, 2, 3, 4}これは、解決策として{1, 2, 3, 4} u {n}取り消し線を引いたら、見る価値がないというあなたの観察に対応しています。
  • 動的計画法を適用します。
  • 実際の要件を明確にしてください。
    • 多分あなたは最高のセットを必要としませんか？良いものはうまくいきますか？多項式時間で適切な解を提供するアルゴリズムがあるかどうかはわかりませんが、あるかもしれません。
    • たぶん、常に最高のセットは必要ありませんか? ランダム化されたアルゴリズムを使用するNPと、すべての実行の 1% (または「十分に安全」と見なされるもの) で失敗するリスクがある多項式時間でいくつかの問題を解決できます。

(覚えておいてください: 停止する問題は解決できないことを知ることと、「hello world」の実装が無期限に実行されるかどうかを判断するプログラムを構築することは別のことです。)

于 2011-07-29T15:25:55.590 に答える
0

次の反復アルゴリズムは、ソリューション セット全体を走査し、タスクのリスト、それらを実行するための総コスト、および実行されなかったタスクの機会コストを格納すると思います。

疑似多項式時間で実行されるようです。アクティビティ数の多項式と、予算内に収まるアクティビティ数の指数関数です。

ixCurrentSolution = 1

initialize empty set solution {
    oc(ixCurrentSolution)        = opportunity cost of doing nothing
    tasklist(ixCurrentSolution)  = empty set
    costTotal(ixCurrentSolution) = 0
    }

for ixTask = 1:cActivities
    for ixSolution = 1:ixCurrentSolution 
        costCurrentSolution = costTotal(ixCurrentSolution) + cost(ixTask)
        if costCurrentSolution < costMax
             ixCurrentSolution++
             costTotal(ixCurrentSolution) = costCurrentSolution 
             tasklist(ixCurrentSolution)  = tasklist(ixSolution) U ixTask 
             oc(ixCurrentSolution)       = OC of tasks not in tasklist(ixCurrentSolution)
        endif
    endfor
endfor
于 2011-08-09T19:38:40.400 に答える