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

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

источник

2015-10-18 MaiaVictor

Вы имеете в виду как 2-мерную сетку? Связанная дискуссия SO: http://stackoverflow.com/questions/8905030/two-dimensional-zipper – ErikR

ОК, я понимаю, что нельзя построить двумерную молнию, как определено. Но означает ли это, что просто невозможно эффективно пройти через 2-мерную сетку? Я считаю, что трудно поверить ... – MaiaVictor

@ Viclib На самом деле, я не думаю, что кто-то утверждает, что это невозможно. Насколько я знаю, это открытый вопрос, возможно ли это. –

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

Это все еще дает ужасные асимптотики так !! О (п). Но мы можем улучшить это, отметив, что нам не нужен произвольный доступ; мы точно знаем, какие ячейки нам нужно вычислить каждую ячейку сетки. Так что все, что нам нужно сделать, это предоставить эти ячейки, когда это необходимо.

Так же, как классический 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-18 02:48:24 rampion

Шаблон случайный, потому что проблема заключается в реализации карты для игры, в которой существа пройдут ... – MaiaVictor

Viclib: это будет хорошая деталь, чтобы добавить к вопросу! – rampion

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

ответ

Смежные вопросы