algorithm - Haskell での動的プログラミングのメモ化

Question

これは、(私が理解している) 動的プログラミングを使用する最初の試みです。私はこの興味深い問題に取り組もうとしています: A* グリッド上でサイコロを転がすための許容ヒューリスティック

このq関数は、サイコロの向きを追跡しながら逆方向に再帰しようとします (visited技術的には次のセルですが、無限の前後ループを防ぐために再帰の観点から「訪問」されます)。それが提供する答えが最善の解決策であるかどうかはわかりませんが、それでも答えを提供しているようです.

ある種のメモ化を実装して高速化する方法についてのアイデアを期待しています -の組み合わせのリストにマッピングする代わりに(ここでmemoized_fib見られる)のようなものを実装しようとしましたが、しゃれた意図はありませんでした。lookup!!q(i,j)Nothing

Haskell コード:

import Data.List (minimumBy)
import Data.Ord (comparing)

fst3 (a,b,c) = a

rollDie die@[left,right,top,bottom,front,back] move
  | move == "U" = [left,right,front,back,bottom,top]
  | move == "D" = [left,right,back,front,top,bottom]
  | move == "L" = [top,bottom,right,left,front,back]
  | move == "R" = [bottom,top,left,right,front,back]

dieTop die = die!!2

leftBorder = max 0 (min startColumn endColumn - 1)
rightBorder = min columns (max startColumn endColumn + 1)
topBorder = endRow
bottomBorder = startRow

infinity = 6*rows*columns

rows = 10
columns = 10

startRow = 1
startColumn = 1

endRow = 6
endColumn = 6

dieStartingOrientation = [4,3,1,6,2,5] --left,right,top,bottom,front,back

q i j visited 
  | i < bottomBorder || i > topBorder 
    || j < leftBorder || j > rightBorder = (infinity,[1..6],[])
  | i == startRow && j == startColumn    = (dieTop dieStartingOrientation,dieStartingOrientation,[])
  | otherwise                            = (pathCost + dieTop newDieState,newDieState,move:moves)
      where previous
              | visited == (i, j-1) = zip [q i (j+1) (i,j),q (i-1) j (i,j)] ["L","U"]
              | visited == (i, j+1) = zip [q i (j-1) (i,j),q (i-1) j (i,j)] ["R","U"]
              | otherwise           = zip [q i (j-1) (i,j),q i (j+1) (i,j),q (i-1) j (i,j)] ["R","L","U"]
            ((pathCost,dieState,moves),move) = minimumBy (comparing (fst3 . fst)) previous
            newDieState = rollDie dieState move

main = putStrLn (show $ q endRow endColumn (endRow,endColumn))