Как вы проникаете через двумерную сетку чисто функционально?

Question

Например, используя застежку-молнию, можно пройти через одномерное пространство. Есть ли такой же элегантный и эффективный способ кодирования понятия ходьбы (без рисунка) через двумерную сетку?

Answer 1

Реальный вопрос в том, что вы хотите пройти через 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
    ]

---

Не каждая проблема на двумерной сетке поддается такой завязке, но для некоторых она работает.