在haskell中記住多維遞回解決方案-有解無憂

我正在解決 Haskell 中的一個遞回問題，盡管我可以得到解決方案，但我想快取子問題的輸出，因為它具有重疊子問題的屬性。問題是，給定一個維度為的網格n*m和一個整數k。有多少種方法可以從 (1, 1) 到達網格 (n, m) 且方向變化不超過 k。

這是沒有記憶的代碼

paths :: Int -> Int -> Int -> Int -> Int -> Int -> Integer
paths i j n m k dir
    | i > n || j > m || k < 0 = 0
    | i == n && j == m = 1
    | dir == 0 = paths (i 1) j n m k 1   paths i (j 1) n m k 2        -- is in grid (1,1)
    | dir == 1 = paths (i 1) j n m k 1   paths i (j 1) n m (k-1) 2    -- down was the direction took to reach here
    | dir == 2 = paths (i 1) j n m (k-1) 1   paths i (j 1) n m k 2    -- right was the direction took to reach here 
    | otherwise = -1

這里的因變數是i, j, k, dir。在像 c /java 這樣的語言中，可以使用 4-d DP 陣列（dp[n][m][k][3]，在 haskell 中我找不到實作它的方法。

uj5u.com熱心網友回復：

正如我在評論中提到的，“打結”是一種眾所周知的技術，可以讓 GHC 運行時為您記憶結果，如果您提前知道您需要查找的所有值。這個想法是把你的遞回函式變成一個自參考的資料結構，然后簡單地查找你真正關心的值。為此我選擇使用 Array，但 Map 也可以。在任何一種情況下，您都必須使用惰性/非嚴格陣列/映射，因為我們將向其中插入值，而在整個陣列被填滿之前我們還沒有準備好計算這些值。

import Data.Array (array, bounds, inRange, (!))

paths :: Int -> Int -> Int -> Integer
paths m n k = go (1, 1, k, 0)
  where go (i, j, k, dir)
          | i == m && j == n = 1
          | dir == 1 = get (i 1, j, k, 1)   get (i, j 1, k-1, 2)    -- down was the direction took to reach here
          | dir == 2 = get (i 1, j, k-1, 1)   get (i, j 1, k, 2)    -- right was the direction took to reach here
          | otherwise = get (i 1, j, k, 1)   get (i, j 1, k, 2)     -- is in grid (1,1)
        a = array ((1, 1, 0, 1), (m, n, k, 2))
            [(c, go c) | c <- (,,,) <$> [1..m] <*> [1..n] <*> [0..k] <*> [1..2]]
        get x | inRange (bounds a) x = a ! x
              | otherwise = 0

我稍微簡化了你的 API：

在m和n引數不隨每次迭代改變，所以他們不應該是遞回呼叫的一部分
客戶端不應該告訴您 what i、j和dirstart as，因此它們已從函式簽名中洗掉并分別隱式地從 1、1 和 0 開始
我還交換了mand的順序n，因為先取一個n引數很奇怪。這讓我有點頭疼，因為我有一段時間沒有注意到我還需要更改基本案例！

然后，正如我之前所說，我們的想法是用我們需要進行的所有遞回呼叫來填充陣列：這就是array呼叫。請注意，中的單元格array通過對的呼叫進行初始化go，其中（除了基本情況！）涉及呼叫get，這涉及在陣列中查找元素。這種方式a是自參考的或遞回的。但是我們不必決定以什么順序查找，或者以什么順序插入它們：我們足夠懶惰，GHC 根據需要評估陣列元素。

我也有點厚臉皮，只在陣列中為dir=1and留出空間，而dir=2不是dir=0。我沒有這樣做，因為dir=0只發生在第一次呼叫時，我可以go直接呼叫這種情況，繞過邊界檢查get。這個技巧確實意味著如果你傳遞一個m或n小于 1 或k小于零的值，你會得到一個運行時錯誤。paths如果您需要處理這種情況，您可以為其本身添加一個保護。

當然，它確實有效：

> paths 3 3 2
4

您可以做的另一件事是為您的方向使用真實的資料型別，而不是Int：

import Data.Array (Ix, array, bounds, inRange, (!))
import Prelude hiding (Right)

data Direction = Neutral | Down | Right deriving (Eq, Ord, Ix)

paths :: Int -> Int -> Int -> Integer
paths m n k = go (1, 1, k, Neutral)
  where go (i, j, k, dir)
          | i == m && j == n = 1
          | otherwise = case dir of
            Neutral -> get (i 1, j, k, Down)   get (i, j 1, k, Right)
            Down -> get (i 1, j, k, Down)   get (i, j 1, k-1, Right)
            Right -> get (i 1, j, k-1, Down)   get (i, j 1, k, Right)
        a = array ((1, 1, 0, Down), (m, n, k, Right))
            [(c, go c) | c <- (,,,) <$> [1..m] <*> [1..n] <*> [0..k] <*> [Down, Right]]
        get x | inRange (bounds a) x = a ! x
              | otherwise = 0

（我和 J 的名字可能比 Down and Right 更好，我不知道這是更容易還是更難記住）。我認為這可能是一個改進，因為型別現在有更多的意義，而且你沒有這個奇怪的otherwise條款來處理dir=7應該是非法的事情。但它仍然有點不穩定，因為它依賴于列舉值的順序：如果我們Neutral在Down和之間放置它會中斷Right。（我嘗試Neutral完全洗掉方向并為第一步添加更多特殊外殼，但這以自己的方式變得丑陋）

uj5u.com熱心網友回復：

實際上，在 Haskell 中，這些事情并不是最瑣碎的事情。您真的希望進行一些就地突變以節省記憶體和時間，所以我認為沒有比裝備可怕的STmonad更好的方法了。

這可以通過各種資料結構、陣列、向量、repa張量來完成。我選擇HashTable了哈希表，因為它使用起來最簡單，而且性能足以在我的示例中發揮作用。

首先介紹：

{-# LANGUAGE Rank2Types #-}
module Solution where

import Control.Monad.ST
import Control.Monad
import Data.HashTable.ST.Basic as HT

Rank2TypesST由于幻像型別，在處理時很有用。我選擇了Basic哈希表的變體，因為作者聲稱它具有最快的查找速度——我們將進行大量查找。

建議為地圖使用型別別名，所以我們開始：

type Mem s = HT.HashTable s (Int, Int, Int, Int) Integer

ST-free 入口點只是為了創建地圖并呼叫我們的怪物：

runpaths :: Int -> Int -> Int -> Int -> Int -> Int -> Integer
runpaths i j n m k dir = runST $ do
  mem <- HT.new
  paths mem i j n m k dir

這是的記憶計算paths。我們只是嘗試在地圖中搜索結果，如果不存在，則保存并回傳：

mempaths mem i j n m k dir = do
  res <- HT.lookup mem (i, j, k, dir)
  case res of
    Just x -> return x
    Nothing -> do
      x <- paths mem i j n m k dir
      HT.insert mem (i, j, k, dir) x
      return x

這是演算法的大腦。它只是一個使用記憶呼叫代替簡單遞回的單子操作：

paths mem i j n m k dir
    | i > n || j > m || k < 0 = return 0
    | i == n && j == m = return 1
    | dir == 0 = do
        x1 <- mempaths mem (i 1) j n m k 1
        x2 <- mempaths mem i (j 1) n m k 2        -- is in grid (1,1)
        return $ x1   x2
    | dir == 1 = do 
        x1 <- mempaths mem (i 1) j n m k 1
        x2 <- mempaths mem i (j 1) n m (k-1) 2    -- down was the direction took to reach here
        return $ x1   x2
    | dir == 2 = do
        x1 <- mempaths mem (i 1) j n m (k-1) 1 
        x2 <- mempaths mem i (j 1) n m k 2    -- right was the direction took to reach here 
        return $ x1   x2
    | otherwise = return (-1)

轉載請註明出處，本文鏈接：https://www.uj5u.com/net/383324.html

標籤：算法哈斯克尔递归函数式编程动态规划

上一篇：Prolog：遞回無法正常作業

下一篇：遞回求和函式javascript