4

例如，使用列表拉链，一个人能够穿过一维空间。是否有任何类似的优雅和有效的方式来编码通过二维网格行走（没有模式）的概念？

4

1 回答 1

6

真正的问题是，你想穿过 2D 网格做什么？

是随机访问还是某种模式？动态编程问题通常被建模为遍历 2D 网格，但它不是随机访问，而是非常有规律的。以及我们可以使用的模式。

例如，考虑寻找两个字符串之间的编辑距离的问题，我们给出：

-- the cost of replacing one character with another
charEditCost :: Char -> Char -> Int

-- the cost of inserting a character
charInsertCost :: Char -> Int

我们可以给出以下递归来确定两个字符串之间的编辑距离：

editDistance [] [] = 0
editDistance (a:as) [] = editDistance as [] + charInsertCost a
editDistance [] (b:bs) = editDistance [] bs + charInsertCost b
editDistance (a:as) (b:bs) = minimum
  [ editDistance as bs + charEditCost a b
  , editDistance (a:as) bs + charInsertCost b
  , editDistance as (b:bs) + charInsertCost a
  ]

但这确实效率低下 - 请注意在第四个等式中，如何editDistance as bs计算三次 - 一次直接计算，一次由 计算editDistance (a:as) bs，一次由计算editDistance as (b:bs)。

动态规划技术告诉我们引入二维网格来缓存结果：

editDistance as bs = last . last $ grid where 
  firstRow j = grid !! 0 !! (j-1) + charInsertCost (as!!j)
  firstCol i = grid !! (i-1) !! 0 + charInsertCost (bs!!i)
  innerCel i j = minimum
    [ grid !! (i-1) !! (j-1) + charEditCost (as!!j) (bs!!i)
    , grid !! i !! (j-1) + charInsertCost (as!!j)
    , grid !! (i-1) !! j + charInsertCost (bs!!j)
    ]
  grid = (          0 : [ firstRow j   | j <- [1..length as] ] ) : 
       [ ( firstCol i : [ innerCel i j | j <- [1..length as] ] ) | i <- [1..length bs ]

这仍然给出了可怕的渐近性，因为!!是 O(n)。但是我们可以通过注意我们不需要随机访问来改进这一点。我们确切地知道我们需要哪些单元格来计算网格的每个单元格。所以我们需要做的就是在需要时提供这些细胞。

就像经典fibs = 1 : 1 : zipWith (+) fibs (tail fibs)提供的fibs!!(i-1)和fibs!!(i-2)及时计算fibs!!i一样，我们可以在这里做同样的事情。

editDistance as bs = last . last $ grid where
  firstRow = scanl (+) 0 $ map charInsertCost as
  firstCol = scanl (+) 0 $ map charInsertCost bs
  grid = ( 0 : firstRow ) : zipWith3 mkRow bs firstCol grid
  mkRow b firstCel lastRow = let thisRow = firstCel : zipWith4 (mkCel b) as thisRow lastRow (tail lastRow) in thisRow
  mkCel b a leftCel aboveLeftCel aboveCel = minimum
    [ aboveLeftCel + charEditCost b a
    , aboveCel + charInsertCost b
    , leftCel + charInsertCost a
    ]

并非 2D 网格上的每个问题都适合这种打结方式，但它确实适用于某些人。

于 2015-10-18T02:48:24.697 回答