言わずと知れたナップサック問題は、動的計画法を用いると最適解を商品の個数とナップサックの容量に対して1次のオーダーで計算することができます。
また、この問題については近似解法が知られています.
とりあえず2通りの近似解法を知っているので, 動的計画法との計算時間と近似率の比較を行ってみようと思います。
設定
動的計画法による解法
省略
近似解法1
価値 / 容量 が大きなものから順番に詰めるだけナップサックに詰めていく方法です。
近似解 / 最適解 ≥ 1/2 以上が成立します。
近似解法2
劣モジュラ的な近似解法です。
価値 / 容量ではなく(現在のナップサックの価値 + 商品の価値) / (商品の容量)が最大のものを見つけ出して詰め込みます。
f(S) := \sum_{i \in S}v_iとすると, fは単調モジュラ関数になるため、制約付きの劣モジュラ最大化近似を適用していることになります。
実験条件
WとWMを固定して
Nを1から10000まで100刻みで動かして近似率と計算時間をプロットしてみました。
結果
W=100, WM=100
近似率
計算時間
W=100, WM=50
近似率
計算時間
W=100, MW=10
近似率
計算時間
まとめ
- 近似解法1の方が近似解法2よりも, 近似率, 計算時間ともに優れている.
- ナップサックの容量に対し, 商品の容量が小さくなると, 近似解法の近似率が上がる.
- 商品の個数が増えると, 近似解法の近似率が上がる傾向にある.
- しかし, 近似解法2ではナップサックの容量に対して、商品の容量が大きいと, 商品の個数がある程度増えると逆に近似率が下がる.(今回だとW=100, WM=100の場合)
- 動的計画法, 近似解法2ともに計算時間が商品数に対して線形に増加する.
実験に用いたPythonスクリプト
gist.github.com
