Haskell中动态规划的高效表格

Question

我已经使用Haskell编写了0-1背包问题的代码。到目前为止，我对实现的惰性和通用程度感到相当自豪。

我首先提供了创建和处理惰性二维矩阵的函数。

mkList f = map f [0..]
mkTable f = mkList (\i -> mkList (\j -> f i j))

tableIndex table i j = table !! i !! j

然后我为给定的背包问题制作一个特定的表格

knapsackTable = mkTable f
    where f 0 _ = 0
          f _ 0 = 0
          f i j | ws!!i > j = leaveI
                | otherwise = max takeI leaveI
              where takeI  = tableIndex knapsackTable (i-1) (j-(ws!!i)) + vs!!i
                    leaveI = tableIndex knapsackTable (i-1) j

-- weight value pairs; item i has weight ws!!i and value vs!!i
ws  = [0,1,2, 5, 6, 7] -- weights
vs  = [0,1,7,11,21,31] -- values

最后，添加一些辅助函数来查看表格。

viewTable table maxI maxJ = take (maxI+1) . map (take (maxJ+1)) $ table
printTable table maxI maxJ = mapM_ print $ viewTable table maxI maxJ

这部分还是比较容易的。但我想更进一步。

我希望表格有一个更好的数据结构。理想情况下，它应该是：

• 未封装（不可变）[编辑]不要紧
• 延迟
• 无界
• O(1) 时间复杂度来构建
• 查找给定条目的时间复杂度为O(1)，
  （更现实的是，最坏情况下O(log n)，其中n是查找第i行、第j列的条目时i*j）

如果你能解释你的解决方案如何满足这些理想条件，那就更好了。

此外，如果你能进一步概括knapsackTable，并证明它的效率，那么将获得额外的奖励积分。

在改进数据结构时，你应该尝试满足以下目标：

如果我要求解的最大重量为10（在我的当前代码中，这将是indexTable knapsackTable 5 10，其中5表示包括第1-5个物品），则应该只执行必要的最小工作量。理想情况下，这意味着不需要对每行表格的脊柱强制执行O(i*j)的工作以达到必要的列长度。如果您认为DP意味着评估整个表格，则可以说这不是“真正”的DP。

如果我要求打印整个表格（类似于printTable knapsackTable 5 10），则每个条目的值应计算一次且仅计算一次。给定单元格的值应取决于其他单元格的值（DP风格：即永远不要重新计算相同的子问题）。

---

想法：

• Data.Array 有界 :(
• UArray 严格 :(
• 备忘录技术 (有关Haskell中DP的SO问题) 这可能有效

对我的陈述理念做出一些妥协的答案将会得到我的赞同（无论如何），只要它们是有信息性的。最少妥协的答案可能会被“接受”。

- Dan Burton

---

注意，“unboxed”和“immutable”是不同的概念；你不能同时让一个变量既拥有“unboxed”特性又拥有“lazy”特性。 - Edward Z. Yang

@Edward和迄今为止的回答者们：谢谢；问题已编辑，删除了“非装箱”的内容。 - Dan Burton

我认为 mkTable f = mkList (mkList . f) 更易读。 - yairchu

Answer 1

首先，你对非装箱数据结构的标准可能有些误导。非装箱值必须是严格的，并且它们与不可变性无关。我要提出的解决方案是不可变的、惰性的和装箱的。此外，我不确定你希望构建和查询以O(1)的方式进行的方式。我提出的这种结构是惰性构建的，但由于其潜在的无限大小，它的完全构建将需要无限时间。对于任何大小为k的特定键，查询该结构将需要O(k)的时间，但当然，你查找的值可能需要进一步的计算时间。

这个数据结构是一个惰性trie。我在我的代码中使用Conal Elliott的MemoTrie库。为了实现通用性，它采用函数而不是列表来表示权重和值。

knapsack :: (Enum a, Num w, Num v, Num a, Ord w, Ord v, HasTrie a, HasTrie w) =>
            (a -> w) -> (a -> v) -> a -> w -> v
knapsack weight value = knapsackMem
  where knapsackMem = memo2 knapsack'
        knapsack' 0 w = 0
        knapsack' i 0 = 0
        knapsack' i w
          | weight i > w = knapsackMem (pred i) w
          | otherwise = max (knapsackMem (pred i) w)
                        (knapsackMem (pred i) (w - weight i)) + value i

这基本上是使用惰性脊柱和惰性值实现的trie。它只受键类型的限制。因为整个过程是惰性的，所以在强制查询之前的构建是O(1)。每次查询会强制将路径下的单个节点及其值进行计算，因此对于有界键大小来说时间复杂度是O(log n)，而不是O(1)。正如我所说，它是不可变的，但不是非装箱的。

它将在递归调用中共享所有工作。实际上，它并不允许直接打印trie，但像这样的代码不会执行任何冗余工作：

mapM_ (print . uncurry (knapsack ws vs)) $ range ((0,0), (i,w))

- Jake McArthur

---

O(1)对于有限的键大小来说很可爱，但它实际上是O(log n)，不是吗？这更值得注意，因为对于有限的n，O(2^n)也是O(1) :-) - sclv

如果你想要严谨一点，它的时间复杂度是O(k)，其中k是键的大小。由于在这种情况下键可能是机器整数或其他类型，因此k实际上是一个常数，而不仅仅是有界的。此外，如果忽略键的大小，它在元素数量方面的时间复杂度为O(1)，这也是我们通常衡量容器的方式。如果我们说平衡树的时间复杂度是O(log n)，那么说字典树的时间复杂度是O(log n)是不公平的。如果我们考虑键的大小，平衡树的时间复杂度实际上是O(k log n)，如果我们认为k因子是随元素数量对数增长的，那么树的时间复杂度将是O(log n log n)。 - Jake McArthur

好的。我的怒火现在已经燃起来了 :-). MemoTrie 将单词/整数/整型转换为小端位列表。bits 函数生成长度为 O(log n) 的列表。参考：http://codepad.org/BlRqzJKL。可能存在不像这样的字典树表示法，但 Conal 使用的一个却是如此（出于很好的原因，例如处理无界整数）。 - sclv

我会同意我们应该使用“k”而不是“n”这个术语，尽管我认为它们是等价的。 - sclv

只要我在强调这一点，记忆体是由构造密集的，因此最大键值大小 k 等同于容器的大小 n。 - sclv

你最后的评论让我信服了。你是对的。因为它们很密集，所以 k = log n。 - Jake McArthur

Answer 2

Unboxed意味着严格和有界。100% Unboxed的任何内容都不能是Lazy或Unbounded。通常的折衷方案是将[Word8]转换为Data.ByteString.Lazy，其中存在未装箱的块（严格的ByteString），它们以无限方式惰性地链接在一起。

使用“scanl”，“zipWith”和我的“takeOnto”，可以制作一个更高效的表生成器（增强以跟踪各个项）。这有效地避免了在创建表时使用（!!）：

import Data.List(sort,genericTake)

type Table = [ [ Entry ] ]

data Entry = Entry { bestValue :: !Integer, pieces :: [[WV]] }
  deriving (Read,Show)

data WV = WV { weight, value :: !Integer }
  deriving (Read,Show,Eq,Ord)

instance Eq Entry where
  (==) a b = (==) (bestValue a) (bestValue b)

instance Ord Entry where
  compare a b = compare (bestValue a) (bestValue b)

solutions :: Entry -> Int
solutions = length . filter (not . null) . pieces

addItem :: Entry -> WV -> Entry
addItem e wv = Entry { bestValue = bestValue e + value wv, pieces = map (wv:) (pieces e) }

-- Utility function for improve
takeOnto :: ([a] -> [a]) -> Integer -> [a] -> [a]
takeOnto endF = go where
  go n rest | n <=0 = endF rest
            | otherwise = case rest of
                            (x:xs) -> x : go (pred n) xs
                            [] -> error "takeOnto: unexpected []"

improve oldList wv@(WV {weight=wi,value = vi}) = newList where
  newList | vi <=0 = oldList
          | otherwise = takeOnto (zipWith maxAB oldList) wi oldList
  -- Dual traversal of index (w-wi) and index w makes this a zipWith
  maxAB e2 e1 = let e2v = addItem e2 wv
                in case compare e1 e2v of
                     LT -> e2v
                     EQ -> Entry { bestValue = bestValue e1
                                 , pieces = pieces e1 ++ pieces e2v }
                     GT -> e1

-- Note that the returned table is finite
-- The dependence on only the previous row makes this a "scanl" operation
makeTable :: [Int] -> [Int] -> Table
makeTable ws vs =
  let wvs = zipWith WV (map toInteger ws) (map toInteger vs)
      nil = repeat (Entry { bestValue = 0, pieces = [[]] })
      totW = sum (map weight wvs)
  in map (genericTake (succ totW)) $ scanl improve nil wvs

-- Create specific table, note that weights (1+7) equal weight 8
ws, vs :: [Int]
ws  = [2,3, 5, 5, 6, 7] -- weights
vs  = [1,7,8,11,21,31] -- values

t = makeTable ws vs

-- Investigate table

seeTable = mapM_ seeBestValue t
  where seeBestValue row = mapM_ (\v -> putStr (' ':(show (bestValue v)))) row >> putChar '\n'

ways = mapM_ seeWays t
  where seeWays row = mapM_ (\v -> putStr (' ':(show (solutions v)))) row >> putChar '\n'

-- This has two ways of satisfying a bestValue of 8 for 3 items up to total weight 5
interesting = print (t !! 3 !! 5) 

- Chris Kuklewicz

Answer 3

懒惰的可存储向量: http://hackage.haskell.org/package/storablevector

无限制、懒惰的构造时间为 O(chunksize) ，索引时间为 O(n/chunksize)，其中chunksize可以根据需要设置得足够大。基本上是一个带有一些重要常数优势的懒惰列表。

- sclv

Answer 4

为了进行函数记忆化，我推荐使用类似Luke Palmer的memo combinators这样的库。该库使用tries（字典树）实现，它们是无界的，并且拥有O(key size)的查找时间复杂度。（通常情况下，你无法做到比O(key size)更好的查找时间复杂度，因为你总是需要访问key的每一位。）

knapsack :: (Int,Int) -> Solution
knapsack = memo f
    where
    memo    = pair integral integral
    f (i,j) = ... knapsack (i-b,j) ...

在内部，integral组合子可能会构建一个无限的数据结构。

data IntTrie a = Branch IntTrie a IntTrie

integral f = \n -> lookup n table
     where
     table = Branch (\n -> f (2*n)) (f 0) (\n -> f (2*n+1))

查找功能的工作原理如下：

lookup 0 (Branch l a r) = a
lookup n (Branch l a r) = if even n then lookup n2 l else lookup n2 r
     where n2 = n `div` 2

还有其他构建无限尝试的方法，但这种方法很受欢迎。

- Heinrich Apfelmus

Answer 5

为什么不使用Data.Map将另一个Data.Map放入其中？据我所知，它非常快。但它不会懒惰计算。

此外，您可以为您的数据实现Ord类型类。

data Index = Index Int Int

你可以直接将二维索引作为键值。你可以通过将此映射生成为列表并仅使用

实现懒惰。

fromList [(Index 0 0, value11), (Index 0 1, value12), ...] 

- pechenie

---

准确地说，它将是在骨架上严格的，但在元素上懒惰的。 - sclv

而且，实际上你只需要 Map (Int, Int) a，如果你的最大 i 和 j 小于 sqrt (maxBound :: Int)，那么你可以按照惯常的方式将它们投影到单个 Int 中，并使用 IntMap。 - sclv