Haskell中的动态编程高效表 [英] Efficient table for Dynamic Programming in Haskell

问题描述

我在Haskell中编写了 0-1背包问题 。我对迄今为止所达到的一般性的懒惰和级别感到非常自豪。

我开始提供创建和处理懒惰2D矩阵的函数。

  mkList f = map f [0 ..] 
 mkTable f = mkList（\ i  - > mkList - > fij））
 
 tableIndex table ij = table！一世 ！！ j 
  

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

  knapsackTable = mkTable f 
其中f 0 _ = 0 
f _ 0 = 0 
fij | ws !! i> j = leaveI 
 |否则= max takeI leaveI 
 where takeI = tableIndex knapsackTable（i-1）（j-（ws !! i））+ vs !! i 
 leaveI = tableIndex knapsackTable（i-1）j 
 
  - 重量值对;项目我有体重ws !!我和价值vs !!我
 ws = [0,1,2,5,6,7]  - 权重
 vs = [0,1,7,11 ，21,31]  - 值
  

最后用几个辅助函数来查看表

  viewTable表格maxI maxJ = take（maxI + 1）。 map（take（maxJ + 1））$ table 
 printTable table maxI maxJ = mapM_ print $ viewTable table maxI maxJ 
  

这非常简单。但我想更进一步。

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

• 取消装箱（不可变） [edit] li>
  
• 无界


• O（1）构建时间
  
• O（1）查找给定条目的时间复杂度，
  （更现实地说，最坏情况 O log n），其中n是 i * j 用于查找第i行第j列的条目）
  

如果您能解释您的解决方案为什么以及您的解决方案如何满足这些理想，则可获得奖励积分。可以进一步概括 knapsackTable ，并证明它是有效的。

在改进数据结构时，应该尽量满足以下目标：

• 如果我要求最大权重为10的解决方案（在我当前的代码中，那将是 indexTable kna psackTable 5 10 ，5表示包含项目1-5）只需执行最少量的工作。理想情况下，这意味着没有 O（i * j）用于强制表中每一行的脊椎所需的列长度。你可以说这不是真正的DP，如果你相信DP意味着评估整个表。


• 如果我要求打印整个表（像 printTable knapsackTable 5 10 ），每个条目的值应该只计算一次。给定单元格的值应该取决于其他单元格的值（DP风格：构思是，不要重复计算相同的子问题两次）
  
  
  < hr>
  
  

  想法：
  
  

  
  
  • Data.Array 有界：（
  
  
  • UArray strict：（$ / b>
    
  • Memoization技术（SO问题关于在Haskell DP）这可能工作
  
  
  
  
  

  答案使我的一些妥协只要信息丰富，理想的人将会得到高调的支持（无论如何，我是这样的）。答案最少的可能是接受的答案。

  解决方案

  首先，您对未装箱数据结构的判断可能有点误导。取消装箱的值必须严格，并且与不可变性无关。我要提出的解决方案是不可变的，懒惰的和盒装的。另外，我不确定你想以什么方式构建和查询是O（1）。我建议的结构是懒散地建造的，但是因为它可能是无限的，所以它的全部构造将需要无限的时间。查询结构将会花费O（k）个时间处理任意大小为k的特定键，但是当然，您查找的值可能需要更长时间才能计算。
  
  

  数据结构是一个懒线索。我在代码中使用了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 
  背包重量值= knapsackMem 
  其中knapsackMem = memo2背包'
  背包'0 w = 0 
  背包'i 0 = 0 
  背包'iw 
   |重量i> w = knapsackMem（pred i）w 
   |否则= max（knapsackMem（pred i）w）
  （knapsackMem（pred i）（w  -  weight i））+ value 
    

  基本上，它被实现为具有懒惰的脊椎和懒惰值的trie。它只受关键类型限制。因为整个事情都是懒惰的，所以在强制查询之前它的构造是O（1）。每个查询强制沿着trie和它的值的单个路径，所以它对于有界密钥大小 O（log n）是 O（1）。正如我已经说过的那样，它是不可变的，但不能拆箱。

  
  
  

  它将共享递归调用中的所有工作。它实际上并不允许你直接打印trie，但是像这样的东西不应该做任何多余的工作：
  
  

    mapM_（打印。uncurry（背包ws vs））$ range（（0,0），（i，w））
    

  
  

  I've coded up the 0-1 Knapsack problem in Haskell. I'm fairly proud about the laziness and level of generality achieved so far.

  I start by providing functions for creating and dealing with a lazy 2d matrix.

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

  I then make a specific table for a given knapsack problem

  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
  

  And finish off with a couple helper functions for looking at the table

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

  This much was pretty easy. But I want to take it a step further.

  I want a better data structure for the table. Ideally, it should be

  • Unboxed (immutable) [edit] never mind this
  • Lazy
  • Unbounded
  • O(1) time to construct
  • O(1) time complexity for looking up a given entry,
    (more realistically, at worst O(log n), where n is i*j for looking up the entry at row i, column j)

  Bonus points if you can explain why/how your solution satisfies these ideals.

  Also bonus points if you can further generalize knapsackTable, and prove that it is efficient.

  In improving the data structure you should try to satisfy the following goals:

  • If I ask for the solution where the maximum weight is 10 (in my current code, that would be indexTable knapsackTable 5 10, the 5 means include items 1-5) only the minimal amount of work necessary should be performed. Ideally this means no O(i*j) work for forcing the spine of each row of the table to necessary column length. You could say this isn't "true" DP, if you believe DP means evaluating the entirety of the table.
  • If I ask for the entire table to be printed (something like printTable knapsackTable 5 10), the values of each entry should be computed once and only once. The values of a given cell should depend on the values of other cells (DP style: the idea being, never recompute the same subproblem twice)

  ---

  Ideas:

  • Data.Array bounded :(
  • UArray strict :(
  • Memoization techniques (SO question about DP in Haskell) this might work

  Answers that make some compromises to my stated ideals will be upvoted (by me, anyways) as long as they are informative. The answer with the least compromises will probably be the "accepted" one.

  解决方案

  First, your criterion for an unboxed data structure is probably a bit mislead. Unboxed values must be strict, and they have nothing to do with immutability. The solution I'm going to propose is immutable, lazy, and boxed. Also, I'm not sure in what way you are wanting construction and querying to be O(1). The structure I'm proposing is lazily constructed, but because it's potentially unbounded, its full construction would take infinite time. Querying the structure will take O(k) time for any particular key of size k, but of course the value you're looking up may take further time to compute.

  The data structure is a lazy trie. I'm using Conal Elliott's MemoTrie library in my code. For genericity, it takes functions instead of lists for the weights and values.

  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
  

  Basically, it's implemented as a trie with a lazy spine and lazy values. It's bounded only by the key type. Because the entire thing is lazy, its construction before forcing it with queries is O(1). Each query forces a single path down the trie and its value, so it's O(1) for a bounded key size O(log n). As I already said, it's immutable, but not unboxed.

  It will share all work in the recursive calls. It doesn't actually allow you to print the trie directly, but something like this should not do any redundant work:

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

  这篇关于Haskell中的动态编程高效表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！