探索 その2

Haskell のお勉強 - 探索のサンプルコードの深さ優先探索のプログラム [code 1] の骨格は3つの部分からなっている。

1. グラフの定義 : g0
2. グラフ g0 の k 番目のノードの先にあるノードを取り出す関数 : find_next k gr
3. グラフ gr の p0 番のノードから p1 番のノードに至る経路を検索する関数 : dfs gr po p1

どの部分も非常に簡潔に記述されているので、全体の構成がよく見通せる。

それでは1番のグラフの定義からコードを追ってみよう。グラフはまずグラフ型の宣言から始まっているが、新しい型を定義するわけではなく、次のようなリストの構造に type 宣言で別名をつけているだけだ。グラフは次のようなタプルで構成されている。

g0 = ( [(1,2,3,4,5,6,7,8,9)],
     [(1,2),(1,3),(1,4),(2,5),(3,5),(3,6),(4,7),(5,1),(6,7),(6,8),(7,9),(8,4)] )

つまり、go = ( ノードのタプルのリスト, ノード間の矢印を表すタプルのリスト) だ。数字はノードを表し、数字のペア (1,2) はノード1からノード2への矢印があることを示している。このように、ノードと矢印のペアのタプルを作れば、グラフをプログラムで扱えるように記述できる。非常に簡単だ。

2番目の関数 find_next k gr はグラフ gr の k 番目のノードの次のノードを全て検索する関数。これも、たった1行でできる。

find_next k gr = map snd $ filter ((==k) . fst) (snd gr)

冒頭から読んでいくと、map snd (List) だから、リストの要素であるタプルの2番目の要素を取り出して、そのリストを作っている。つまり、矢印のリスト[(1,2), (1,3)] などが与えられたらそれから [2, 3] のように、矢印の先にあるノードの番号のリストを作る。

$ filter ((==k). fst) (snd gr) は snd gr つまり矢印のリスト [(1,2),(1,3), .. ] から ((==K) . fst)) つまり、タプル (1,2) の1番目の要素が k であるものを filter で抜き出している。たとえば、filter ((==1).fst) (snd gr) => [(1,2), (1,3), (1,4)] だから、

find_next 1 gr => map snd [(1,2),(1,3),(1,4)] => [2,3,4]

だ。

3番目の関数 dfs gr p0 p1 がグラフ gr のノード p0 から p1 までの経路を探索するプログラムだ。

dfs gr p0 p1 = dfs_aux gr p0 p1 [] なので、dfs は dfs_aux の第4引数を隠蔽したシンタックスシュガーである。したがって、経路探索の本体は dfs_aux gr p0 p1 path ということになる。dfs_aux の定義は次のようになっている。

dfs_aux gr p0 p1 path =
  | p0 == p1 = return (reverse (p0:path))
  | otherwise = msum $ map (\p -> dfs_aux gr p p1 (p0:path)) [ x | x <- find_next p0 gr, not (x `elem` path)]

上のコードには、return と msum という見慣れないキーワードがある。これには、モナドを利用したあっと驚くような仕掛けがあるのだが、それは原典を読んでもらうとして、探索のメカニズムに集中するために上のコードを次のように変えてみる。

dfs_aux gr p0 p1 path =
  | p0 == p1 = [ reverse (p0:path) ]
  | otherwise = concatMap (\p -> dfs_aux gr p p1 (p0:path)) [ x | x <- find_next p0 gr, not (x `elem` path)]

コード部分はたったの2行しかない。上のコードで最初に気になるのは path という余分な引数がなぜ必要なのかということだ。gr はグラフのデータだし、p0 は出発点のノードで、p1 は到達点のノードだが、path は一体何なのだろうか。実は、この余分な引数はこの関数が末尾再帰型の関数であることを示している。

再帰型の関数は、次の階乗の計算に見られるように自分自身を呼び出す。

fact n = if n == 0 then 1 else n * fact (n-1)

しかし、これは途中の計算を保持しておくのにスタックを使わなければならない。階乗の計算を末尾再帰で記述すると次のようになる。

fact n result = if n == 0 then result else fact (n-1) (n * result)

実際、このプログラムがきちんと働くのは確かめることができる。

Hugs> fact 5 1 where fact n result = if n == 0 then result else fact (n-1) (n * result)
120

これだと、中間の結果を引数 result に引き継いでいくことができる。Haskell のような関数型言語では変数への代入をすることができない。これは、状態を保持しなければならないようなプログラムでは非常に不便だ。しかし、末尾再帰を利用することで、計算の途中経過を引数の値として保持することができる。

グラフの経路の探索では、探索が失敗したとき元のノードに戻るバックトラックを行わないといけない。しかし、バックトラックを行うためにはもどるためのノードの情報が残っていなければならないが、変数への代入ができないと難しい。そこで、末尾再帰型関数の引数のなかに探索中の経路の状態を保持させるようにするのだ。

dfs_aux に話を戻すが、ガードの条件が p0 == p1 のとき、つまり探索が成功したときは、それまでの経路の記録が path 変数に保持されているのでそれを戻値として返す。ノードの情報を保持するときにリストの頭から付け加えているので、reverse 関数で順序を逆にしておかなければならない。

p0 == p1 でない場合には、p0 から移動可能なノードを次の内包的定義で検索する。

[ x | x <- find_next p0 gr]

ただし、同じノードに戻ったりしてらループを永遠にたどることになるので、path に含まれているノードは除外しないといけない。したがって、上の内包的定義は次のようになる。

[ x | x <- find_next p0 pr, not (x `elem` path)]

述語 x `elem` path はリスト path の要素として x が含まれていれば真となる。その否定だから、x は path に含まれないものだけを選び出すことになる。

いま仮にそのようなノードのリスト[a, b c] が得られたとしよう。そのとき、

concatMap (\p -> dfs_aux gr p p1) [ a, b, c ]

では、concat [ dfs_aux gr a p1, dfs_aux gr b p1, dfs_aux gr c p1]

が実行される。この例でノード a で次に移動するノードがないときは、def_aux gr a p1 は [] リストを返す。なぜなら、Haskellでは、(\p -> dfs_aux gr p p1) [] は戻値 [] を返すようになっているからだ。dfs_aux gr b p1 の戻値もやはり [] で、dfs_aux gr c p1 がパスの値 [[d, e, f]] を返したとするすると、

concatMap (\p -> dfs_aux gr p p1) [a, b, c] => concat [[], [], [[d,e,f]]] => [[d,e,f]]

という結果になる。

dfs_aux の動作を正確に理解するには、この関数の展開を順に追っていく必要があるが、上に述べたことでもなんとなくその動作が感覚的に分かるだろう。あとは、動かしてみて結果オーライなら多分動いているのだ。

経路探索のプログラムを正確に理解するのは難しくはないが、面倒くさい。上のプログラムの雛形を動かしてみて動作が飲み込めたら、色々なグラフに使って応用することができる。そうすれば、Haskell を使えば探索問題のようなものは非常に簡潔にプログラムできるのがわかってうれしくなるだろう。
[PR]
by tnomura9 | 2011-06-16 07:24 | Haskell | Comments(0)
<< 探索 その3 探索 >>