多次元配列問題 with Data.Array

Haskellは、Data.Arrayモジュールを用いてデータを配列のように扱うことができる。
が、書き換えはコストが高いために苦手。

だからデータ参照などにのみ使用した方が良い。
ならばそうしましょう。

Data.Arrayを利用して、多次元配列問題を解く！
手始めにはちょうど良い難易度の問題を、以前C++で解いたことがあるので、ここではそれを例として扱います。

要約すれば、
進行方向が右・下の二方向限定の最短経路問題です。
解き方は非常にシンプルですし、開放もすぐに頭に思いつきます。

以前C++で解いたときは、
入力として与えられた盤面を保持する二次元配列と、それぞれの点に至る最短経路を保持していくための二次元配列、二つのデータ配列を用意しました。
が。
Haskellでは何度も言いますように、書き換えの多い作業に配列は向いていない。
盤面情報は変化することがないので、これをArrayで保持するのには問題ありませんが、最短路の情報を保持するのには向いていません。
かといってリストを使うと、要素のアクセスや更新のための関数を考えるのが少々面倒です。

ここで注目すべきが。
進行方向は、右・下の2方向だけ、という点です。
それぞれの点からは2つの経路にしか分離しないのです。

ということで。
二分木を使いましょう。
二分木で、前の枝の値を次の枝葉に持ち越して和をとっていけば経路コストは簡単に求まりますし、
最後は、木のLeaf要素をリストに落として、
そこから最小値をとれば良いだけです。

書いてみた。

私の手元で検証した限りでは、このアルゴリズムは正しく動きます。
実行時間は知りません。
C++などには劣るでしょうし、情報が多いと、それだけLeaf要素は増えるのでもしかしたらOUTかもしれません。

あ。このアルゴリズムは、
ダイクストラ法なのか動的計画法なのか、
あるいは別の何かに分類されるのか。
違いがよくわからない.....

import Data.Array

type ArrayI = Array Int Int
type ArrayII = Array Int ArrayI

--二次元配列上の座標
type Pos = (Int,Int)
--二次元配列の大きさと、二次元配列自身のタプル
type Data = (Pos,ArrayII)
--ある座標での値と、その座標
type Elem = (Int,Pos)

data Tree a = Branch a (Tree a) (Tree a) | Leaf a
deriving (Show,Ord,Eq)

makeRange :: String -> (Int,Int)
makeRange = (\[a,b] -> (a,b)).map read.take 2.words

makeArray :: (Int,Int) -> IO (Pos,ArrayII)
makeArray (h,w)
 = do cs <- getContents
      let xs = take h $ lines cs
      return ((h,w),array (1,h)
                 $ zip [1..h]$ map (makeArray' w) xs)

makeArray' :: Int -> String -> ArrayI
makeArray' w str = array (1,w) $ zip [1..w] $ map f str
  where
    f c = read [c]

--配列からindex(h',w')の要素を見る
seeValue :: Int -> Int -> ArrayII -> Int
seeValue h' w' mapData = (mapData ! h') ! w'

makeTree :: Data -> Pos -> Tree Elem
makeTree d@((h,w),mapData) p@(h',w')
 | p == (h,w) = Leaf (seeValue h w mapData,p)
 | h' > h = Leaf (9*h*w,p)
 | w' > w = Leaf (9*h*w,p)
 | otherwise = Branch (seeValue h' w' mapData,p)
                          (makeTree d (h'+1,w'))
                          (makeTree d (h',w'+1))

leafList :: Int -> Tree Elem -> [Int]
leafList n (Leaf v)= [fst v + n]
leafList n (Branch v t1 t2)
  = leafList (n+fst v) t1 ++ leafList (n+fst v) t2

answer :: Data -> Int
answer d@((h,w) ,mapData)
 = foldl min (9*h*w) . leafList 0 $ makeTree d (1,1)

main = do hw <- getLine
          d <- makeArray.makeRange $ hw
          print $ answer d

wvogel日記

自分用の技術備忘録が多めです．

多次元配列問題 with Data.Array