探索 その3

グラフの探索のプログラムの仕組みがどうしても気になるので、テストプログラムを作って試してみた。

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

find_next gr k = map snd $ filter (\n -> fst n == k) gr

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

実行例

Main> search gr 1 4 []
[[1,3,6,8,4],[1,4]]

これを手作業でトレースしてみる。find_next gr 1 => [2, 3, 4] だから、
search gr 1 4 [] => concat [search gr 2 4 [1], search 3 4 [1], search 4 4 [1]]

find_next gr 2 => [5] だから、
search gr 2 4 [1] => concat [search gr 5 4 [2, 1]]

find_next gr 5 => [1] だから、ノード1は path = [2,1] に含まれてしまうので、
search gr 5 4 [2,1] => []

したがって、
search gr 2 4 [1] => concat [search gr 5 4 [2,1]] => []
search gr 1 4 [] => concat [[], search 3 4 [1], search 4 4 [1]]
=> concat [search 3 4 [1], search 4 4 [1]]

と、探索がバックトラックするのが分かる。トレースをもう少し続けてみよう。
search 3 4 [1] => concat [search gr 5 4 [3,1], search gr 6 4 [3,1]]
search gr 5 4 [3,1] => concat [search gr 1 4 [3,1]] => []
search gr 6 4 [3,1] = >concat [search gr 7 4 [6, 3, 1], search gr 8 4 [6,3,1]]

だから、結局
search 3 4 [1] => concat [[], [search gr 7 4 [6,3,1], search gr 8 4 [6,3,1]]
=> concatMap [search gr 7 4 [6,3,1], search gr 8 4 [6,3,1]]

のようになり、探索の失敗した枝が次々に抜け落ちてバックトラックされるのがわかる。探索の失敗したルートを省略するようにして探索を続けると、
search gr 7 4 [6,3,1] => concat [search gr 9 4 [7,6,3,1]]
=> concat [concat [[]]] => []
search gr 8 4 [6,3,1] => concat [search gr 4 4 [8,6,3,1]]
concat [[[1,3,4,6,8]]] => [[1,3,4,6,8]]

したがって、
search 3 4 [1] => concat [[1,3,4,6,8], search gr 6 4 [3,1]]

search gr 6 4 [3,1]の探索がすべて失敗すると、serach gr 6 4 [3,1] => [] だから、結局

search 3 4 [1] は [[1,3,4,6,8]] を返す。したがって、 最初の検索式は次のように展開される。

search gr 1 4 [] => concat [[[1,3,4,6,8]], search 4 4 [1]]

search 4 4 [1] について同じように展開して、search 4 4 [1] => [[1,4]]

となるから、結局
search gr 1 4 [] => concat [[[1,3,4,6,8]], [[1,4]]] => [[1,3,4,6,8], [1,4]]

という結果が得られる。プログラムをトレースすると次々に探索の失敗した経路が脱落していく様子が分かるが、どうしてそうなるかを理解する鍵は次の再帰式だ。言い換えると、次の式を理解することが、探索プログラムの動作を理解する鍵になるということだ。

search gr p0 p1 path = concat $ map (\p -> search gr p p1 (p0:path)) [ x | x <- find_next, not (x `elem` path)]

前回の記事とも重なるが、ノード a から探索可能なノードのうち path に含まれない物を [b, c, d] であると仮定してみる。そうすると上の式は次のように展開できる。

search gr a p1 path = concat [search gr b p1 (a:path), search gr a p1 (a:path), search gr d p1 (a:path)]

このとき search gr a p1 path がどういう値を返すのだろうか。

まず、上の例の search gr b p1 (a:path) について考えてみる。b == p1 のとき、つまり、目的のノードが見つかったとき、search gr b p1(a:path) => [reverse(p1:b:path)] が戻される。また、ノード b に連絡するノードが見つからなかったとき、search gr b p1 (a:path) は、[] になる。したがって、concat [ search .. ] の引数のリストが皆確定的な値、たとえば、[[], [path1], [path2]] のとき、

search gr a p1 path => concat [[], [path1], [path2]] => [path1, path2]

となる。search gr b p1 (a:path) がすぐには確定しない場合、次々に関数の展開が起きるが、最後には、[] か [path(n)] のリストの値となって戻値が帰ってくる。したがって、search gr a p1 path は、その下層の関数の値のうち、探索できたパス全てからなるリストを戻値として返すことになる。ノード a の戻値は、ノードa の上層のノードの concat [ .. ] のリストのメンバーとなるから、ノード a の上層のノードはノード a 以下のノードの全ての情報を引き継ぐことになる。

このように search 関数の戻値が確定するまで、出発点のノードから次々にグラフの経路の検索が行われ、全ての経路を検索した結果がリストとして戻されることになる。

上の説明がうまく説明になっているか自信がないが、とにかく、これだけの複雑な操作を2,3行でプログラムできてしまうのがうれしい。
[PR]
by tnomura9 | 2011-06-18 08:14 | Haskell | Comments(0)
<< World is mine 探索 その2 >>