深さ優先探索を実装してみる。

基礎中の基礎ですが、せっかく実装したので。

深さ優先探索とはなんぞや

進めるところまで進んで、行き止まったら直前の分かれ道に戻り他の道を模索するという、探索アルゴリズムの初歩となります。

深さ優先探索は何に使えるのか

行ける場所全てを探索するという性質上、ある地点とある地点がつながっているかを判定することができます。
また、ゴールにたどり着かなかった場合は、取りうる全ての間を途中で試すという関係上、全状態の列挙にも使えたりします。

ただし、深さ優先探索によって見つかったルートが最短とは限りません(地図を見ずに行き当たりばったりで目的地に歩いていくルートが最短とは限らないのと同じです。)

深さ優先探索はどう実装するのか。

主に2つの方法があります。スタックを利用する方法と再帰関数を利用する方法です。このうち、再帰関数を使った実装は(なれれば)簡単にかけるので、再帰関数で簡単に実装できることが深さ優先探索の利点の一つとなっています。

※スタックとは
先に入れたものほど、あとに取り出されるデータ構造です。ものを積み上げておいて、取るときは上からとるイメージです。(stack自体に積み上げるの意味があります。)

*再帰関数とは
その関数の中で自分自身をよんで繰り返し処理をさせるような関数です。

実際の実装

以下のような道を探索していきます。このようにどの頂点がどこにつながっているかを表したリストを頂点隣接リストとよんだりします(今回上から下の道のみを考えています。)

.cpp

std::vector<std::vector<int>> tree = {{1,2},{3,4},{4,10},{},{5,6},{7},{8,9},{},{},{},{};

//                 0
//               /   |
//              1    2
//             /  \ / |
//            3    4   10
//               /  |    |
//              5   6    |
//             /   / |  /
//            7   8   9
//

再帰関数

.cpp

bool dfs_func(int state, int goal){
  if (state==goal){
    return true;
  }
  for (auto next:tree[state]){
    if (dfs_func(next,goal) == true){
      return true;
    };
  }
  return false;
}

自分のいる場所がゴールかどうか判断し、もし違った場合はつながってる道に対して判断することを繰り返して行きます。もし、途中でゴールに行き着いた場合、trueがどんどん連鎖的に返ってきて最終的に大本の関数がtrueになるような構造になっています。

stack

.cpp

bool dfs_stack(int start, int goal){
  std::vector<int> stack;
  stack.push_back(start);
  bool is_goal=false; 
  while(!stack.empty()){
    int now = stack.back();
    stack.pop_back();
    for (int next:tree[now]){
      stack.push_back(next);
      if (next == goal){
        is_goal = true;
        break;
      }
    }
    if(is_goal){break;}
  }
  return is_goal;
}

stackでの実装です。つながっている頂点をstackに入れきって、stackの一番上を見てgoalか判定することを繰り返します。しかし、こちらは少々トリッキーな実装になっており、stackの一番上をみて隣接頂点をstackに積む前にstackから一番上を取り出してしまっています。これをしないと、どこまでいってもgoalにいきつかなかったときの判定が面倒になります。

再帰関数(通った道を表示)

.cpp

bool dfs_func_root(int state, int goal){
    if (state==goal){
      std::cout << state;
    return true;
  }
  for (auto next:tree[state]){
    if (dfs_func_root(next,goal) == true){
      std::cout << state;
      return true;
    };
  }
  return false;
}

再帰関数で、通った道を表示するのは簡単で、trueを返すたびに今いる場所も一緒に捉えればよいです。
stackの実装で道順を表示するのは自分が思いついた限りでは結構面倒な方法しかなく、今回は諦めました。

上記のコードのテスト

.cpp

int main (void){
  int s,g;
  std::cin >> s >> g;
  std::cout << "stack ver" << std::endl;
  show_res(dfs_stack(s,g));
  std::cout << "func ver" << std::endl;
  show_res(dfs_func(s,g));
  std::cout << "root ver" << std::endl;
  dfs_func_root(s,g);
  std::cout << std::endl;
}

0 9
stack ver
true
func ver
true
root ver
96410

0 20
stack ver
false
func ver
false
root ver

この通り、場合によっては遠回りをしてしまっていますし、つながっていない場合にはつながっていないことがわかります。

おわりに

今までずっとstackの方で実装してたのですが、再帰で実装したら思ったより楽だったので今度からこっちで実装しようと思っています。