【Haskell】ナップサック問題を解く

2016-07-15
#haskell

Haskellのリモート勉強会Remote.hs #05 アルゴリズムでパズルを解こうというものに参加してみた。今回のお題はナップサック問題だった。

総当り法で解く

アイテムを含む／含まない場合のすべてについて条件を満たすかチェックして、有効な場合について価値が最大になる組み合わせを調べれば、とりあえずは望みの答えが求まる（計算量はなので、要素が増えると計算量が爆発する）。 手始めにこの方法を使って力任せに解いてみる。

品物の組み合わせを列挙する関数は必要になるたびに再帰で実装しようとして毎回コンパイルエラーで苦労する。 今回もなんとか実装した後で初めて知ったんだけど、Data.Listのsubsequencesという関数でリストの要素のすべての組み合わせを列挙できた。 最初からこれを知ってれば総当りは結構簡単に調べられたのだった。

インポートと、型定義：

import Data.List (maximumBy, subsequences)
import Data.Function (on)

type Value = Integer
type Capacity = Int
data Item = Item { value :: Value, capacity :: Capacity }
  deriving Show

totalValue :: [Item] -> Value
totalValue = sum . map value

totalCapacity :: [Item] -> Capacity
totalCapacity = sum . map capacity
  • Item が品物、 Value が価値、 Capacity が容量
  • totalValue で品物リストの価値合計、 totalCapacity で容量合計を計算する

総当りでナップサック問題を解く本体：

knapsackBF :: Capacity -> [Item] -> [Item]
knapsackBF maxCapacity = maximumBy (compare `on` totalValue) . filter isValid . allCombinations
  where  allCombinations = subsequences
         isValid items = totalCapacity items <= maxCapacity
  • 最大容量maxCapacityと品物リストを受け取って、価値が最大になる品物リストを返す
  • 品物リストの全ての組み合わせ（allCombinations）の中で、最大容量を超えないものだけを取り出し（filter isValid）、その中で価値の合計が一番高いものを選ぶ（maximumBy (compare on totalValue)）

動的計画法で解く

総当りだとちょっと品物の数が増えると計算量が爆発して終わらなくなってしまう。 動的計画法（Dynamic Programming）という方法でナップサック問題を解く方法が問題の解答に載っていたので、それをHaskellでも動かしてみた。

ナップサック問題にDPをあてはめるには総当りでの考え方とは逆に、品物の全パターンではなく容量の全パターンを軸に考える。 0から最大容量のそれぞれの場合で価値が最大になるにはどういう組み合わせにすればいいか、というのを品物を１個ずつ調べていく。

初期状態は品物を１つも追加してない状態で、各容量すべてを価値０と置く。 ある段階まで計算が終わってるとして次の品物（価値、容量）を考える。 各容量は、その品物を追加しなかった場合である「その容量でのその時点の最高価値」と、した場合の「容量-のその時点の最高価値」+（ただし容量がより少ない場合にはその品物を加える事ができないので０）の２つを比べて、大きい方を選択する（言葉で説明するの難しい…）。 この手順をすべての品物に対して行うと、最大容量での価値が望みの解答になっている（これでどうして求まるのかも直感的には分かりづらい…）。

プログラムにするにはさらにひねる必要があって、少ない容量をルックアップする代わりに前に0を挿入してやった：

knapsackDP :: Capacity -> [Item] -> [Item]
knapsackDP maxCapacity = snd . last . foldl step initial
  where initial = replicate (maxCapacity + 1) empty
        empty = (0, [])  -- (value, items)
        step previous item = zipWith chooseValuable itemIncluded notIncluded
          where itemIncluded = shift ++ map addItem previous
                notIncluded = previous
                addItem (v, items) = (v +  value item, item : items)
                chooseValuable a b = maximumBy (compare `on` fst) [a, b]
                shift = replicate (capacity item) empty
  • 初期状態は initial
  • １ステップすすめる関数 step で、 zipWith chooseValuable itemIncluded notIncluded で、アイテムを含めた場合と含めない場合の価値の高い方を選択
  • それを foldl ですべての品物に対して行って、lastで最大容量のときの最終的な価値が得られる
  • 計算量は、メモリ消費量は
    • 上記のコードがHaskell処理系でそのように振る舞うかは検証してない

参考

関連記事

新着記事