Zenn版

TL;DR

どの言語でも手順は選択､展開､生成
生成はm.chain(L) (= concat(m, L))

背景

講義でDFSとBFSを習ったのでRustで実装する｡以上

DFS(Depth First Search)について

日本語では深さ優先探索
与えられた木構造に対して､問題固有の情報を使わない探索法の一つ｡(<=> BFS)
探索する木が有限であれば必ず解が見つかる

選択した対象のノードが子を所持していない階層まで降下して行き､葉(子を持たないノード)に到達したら､浅いレベルのノードに戻り探索していく｡

詳しい解説は別にゆずるが､この葉をめざして兄弟ノードを保持しながら探索をするので､使用する空間量が線形に増加するので､空間計算量が節約しやすい
ただし､選択するノードによっては､ごく浅い階層に目標ノードがあっても到達するまでに時間がかかってしまう(無駄な探索をする)場合がある｡

この記事のコード

DFSの擬似コード

DFSの大まかな手順は以下の通り｡
(※DFSによる探索木の生成)

開始ノードをオープンリストに登録
ノードを選択する(select)
- オープンリストの先頭を取り出す
- ノードがゴールなら終了
ノードが子を持つ場合
- 子を取り出す(expand)
取り出された子と､探索対象を結合する(generate)
- このリストをオープンリストともいう
上記を繰り返す
- オープンリストが空になった場合､不能解

プログラムのソースコードっぽく書くなら､


list = [start]

while(list が空でない) {
  //select
  s = list.front_pop() // Depueue､オープンリストから先頭を取り出す
  if s == goal {
    break // 探索木の生成終了
           // ゴールまでの経路を生成する場合､ここでコネコネする
           // ゴールノードの親を辿った配列の逆順が､正解の経路
  }

  //expand
  children = s.children

  //generate
  list = concat(children, list) // expandで入手した子をオープンリストの前に挿入する
}

ここから発展させると先に述べた無駄な訪問をしないようにできたりと最適化は可能だが､今回は学習目的なのでひとまずここまで

Rustで書く場合

GitHubに上げたコードのみが正解ではない｡(例えばオープンリストにはVecではなくVecDequeを使うなど)
のでRustでアルゴリズムを勉強したい!というような人は疑似コードから頑張って書いてみてください｡

ノードの構造の一例

構造上､親は単独か0(ルートノード)になる｡
https://github.com/raiga0310/simple-dfs/blob/9f2d8466b6defeaf7408128ac1b6a493fb7a4e31/src/node.rs#L3-L8

グラフを生成する部分は今回本題でない(し､あまりすっきりとした実装というわけでもない)ので割愛｡src/node.rsに書いてあります｡

先頭要素を取り出す

Vecの場合
- s = list.remove(0)
VecDequeの場合
- s = list.pop_front()
  VecDequeのほうがやることはわかりやすい(removeは値を返却するとは思いつきにくい)
  まぁVecで実装して気になる人は適当に作ってもいいかもしれない
  実際にやってみたが冗長なのでオープンリスト固有のメソッドをもっと実装したいとなった場合についでに実装するくらいがちょうどいいと思います｡

generateで子ノードとオープンリストを結合する

Rustはマルチパラダイムを採用している(表現が不正確)ので関数型の機能を使って結合を表現できる(iterを使うと所有権が移動することには気をつけたい)

値を複製する場合､clone()メソッドが使用されるが､Option<T>や今回のようなIterator<T>のようなラップされている値をclone()すると､返却される型はWrapped<&Inner>のようにラップされている要素は借用型になる｡そこで､cloned()を用いることで､Wrapped<Inner>を返却するようにする｡

実行例

木構造(bul listなので見づらいかもしれません)

0
- 1
  - 5
  - 4 (goal)
- 2
  - 6
  - 7
- 3
  - 8
  - 9

   Compiling dfs v0.1.0 (C:\Users\raiga\dev\assignments\algo\dfs)
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 1.58s
     Running `target\debug\dfs.exe`
Depth First Search
select: 0, list: []
expand: [1, 2, 3]
generate: [1, 2, 3]
select: 1, list: [2, 3]
expand: [5, 4]
generate: [5, 4, 2, 3]
select: 5, list: [4, 2, 3]
expand: []
generate: [4, 2, 3]
select: 4, list: [2, 3]
----- reached the goal!! -----
answer: [4, 1, 0]

この場合は探索をはじめた枝にゴールが存在していたので､割合早く探索が終了している｡
これを､例えば0の子要素を[3, 2, 1]にかえて探索を実行すると､

    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.01s
     Running `target\debug\dfs.exe`
Depth First Search
select: 0, list: []
expand: [3, 2, 1]
generate: [3, 2, 1]
select: 3, list: [2, 1]
expand: [8, 9]
generate: [8, 9, 2, 1]
select: 8, list: [9, 2, 1]
expand: []
generate: [9, 2, 1]
select: 9, list: [2, 1]
expand: []
generate: [2, 1]
select: 2, list: [1]
expand: [6, 7]
generate: [6, 7, 1]
select: 6, list: [7, 1]
expand: []
generate: [7, 1]
select: 7, list: [1]
expand: []
generate: [1]
select: 1, list: []
expand: [5, 4]
generate: [5, 4]
select: 5, list: [4]
expand: []
generate: [4]
select: 4, list: []
----- reached the goal!! -----
answer: [4, 1, 0]

ほぼ全探索と変わらない回数ノードを訪問することがわかる｡
なので､愚直なDFSで時間制約を越える問題に直面した場合､明らかにゴールノードには到達しない枝を刈ったりするのが必要なのだろう(私はまだ知らないのでどこかでまた)

余談実装を少し変えるとBFS(幅優先探索)もできる

先で紹介した実装を少し変えると､BFSになる｡
考え方としては､子がいなくなるまで要素を展開するのがDFSで､オープンリストのノードをすべて訪問するのがBFSである｡selectで先頭を取り出すのを変えないとすれば､結合部分を工夫する､generateにおいて次に探索する要素がオープンリストの先頭になるようにすればいい｡

擬似コードでは

list = concat(list, children)

Rustでは､

list = list.iter().cloned().chain(leaves).collect();

のようになる｡

実行例

Breadeth First Search
select: 0, list: []
expand: [1, 2, 3]
generate: [1, 2, 3]
select: 1, list: [2, 3]
expand: [5, 4]
generate: [2, 3, 5, 4]
select: 2, list: [3, 5, 4]
expand: [6, 7]
generate: [3, 5, 4, 6, 7]
select: 3, list: [5, 4, 6, 7]
expand: [8, 9]
generate: [5, 4, 6, 7, 8, 9]
select: 5, list: [4, 6, 7, 8, 9]
expand: []
generate: [4, 6, 7, 8, 9]
select: 4, list: [6, 7, 8, 9]
----- reached the goal!! -----
answer: [4, 1, 0]

ついでに言うならBFSは$O(b^d)$です｡