4

たとえば、リスト ジッパーを使用すると、1 次元空間を歩くことができます。二次元グリッドを (パターンなしで) 歩くという概念をエンコードする同様にエレガントで効率的な方法はありますか?

4

1 に答える 1

6

本当の問題は、2D グリッドを何をしたいのかということです。

それはランダムアクセスですか、それとも何らかのパターンですか？動的プログラミングの問題は、2D グリッドをトラバースするものとしてモデル化されることがよくありますが、ランダム アクセスではなく、かなりパターン化されています。そして、私たちが扱うことができるパターン。

たとえば、与えられた 2 つの文字列間の編集距離を見つける問題を考えてみましょう。

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

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

2 つの文字列間の編集距離を決定するために、次の再帰式を与えることができます。

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
  ]

しかし、それは本当に非効率的です - 4 番目の方程式で、editDistance as bsが 3 回計算されることeditDistance (a:as) bsに注意してくださいeditDistance as (b:bs)。

動的計画法では、結果をキャッシュするために 2 次元グリッドを導入する必要があります。

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 に答える