全探索の解き方

TopCoder

動機

ふと、自分が全探索な問題を解く時にどう解いているかをまとめて見ようと思った。 もちろん自分もまだまだなわけなので、解説というものにはならないし、あくまで自分の考えをまとめただけである。

ちなみに自分が少しでも全探索についてちゃんと理解できたかなと思えたのは、競技プログラミングを始めてからだと思う。 それまでも、もちろんスタック・キュー・再帰なんかを使って、深さ優先探索や幅優先探索を書くことがあったけど、今みたいに書く前にどう書けばいいかを整理できていたわけではなくて、消したり書いたりして長時間考え、いろいろ苦労していた気がする。

基本テンプレ

基本的に自分の場合、最小手数を求めるであったり、最短経路を求めるようなものでない限り全部を探索する必要があるものは、深さ優先探索で解くことが多い。再帰でかけるので、コード量が少なく感じるからだと思う。 まず自分は何も考えず以下のように書く。 (まぁ、lispとかで再帰を書く時のイディオムと同じ。)

  //関数名はrecもしくはdfsに決めてる。
  int rec(状態変数){
     if(<終了条件>){

     }
     <選択肢の列挙(recの再帰呼び出し)>
  }

関数名とか、これだけでも書き方を決めておくと、時間少ない中悩む必要がないので楽だったりする。 幅優先探索の場合も下みたいなテンプレートを脳内に用意してたりする。 (Stateはいちいち書くのが面倒なのでpairを使ったりする。)

struct State {
  <状態変数>
};

  queue Q;
  Q.push(<初期状態>)
  while(!Q.empty()){
    State s = Q.front(); Q.pop();

    <選択肢の列挙(Q.pushの呼び出し)>
  }

問題パターン

列挙パターン 例) 1,2,3,4の４数字からなる10桁の数字列を列挙せよ。

  vector > result; //列挙した結果を格納するコンテナ
  char cand[] = {1,2,3,4};

  //状態変数 i は、今現在何桁目までを着目してるかを確認
  //状態変数 v は、現在までに選択した各桁の数字を格納
  void rec(int i, vector &v){
     if(i == 10){
        //列挙対象に何らかの条件がある場合は、最終的に条件に当てはまるかどうかをチェックする。
        //例 末尾が4の数字列の場合
        //if(v.back != 4) return;
        result.push_back(v);
        return;
     }
     for(int j = 0; j < 4; j++){
        //枝刈りする場合はここでもチェックする。
        v.push_back(cand[j]);
        rec(i+1,v);
        v.pop_back(); //後始末を忘れずに
     }
  }

二次元探索パターン i,jの２つの状態を持つが基本同じ。 例) 数独パズルを解け

//左上から各行ごとに、スキャンしていく
//状態変数は現在着目しているセルの(i行,j列)と、数字が埋められた盤面をvとして持つ。
void rec(int i, int j, vector > &v){
  //再下端までいったら終了。条件に合うものが出力される。
  if(i == 9){
    cout << v << endl;
    return;
  }
  //右端までいったら1行下に。
  if(j == 9){
    rec(i+1,0,v);
    return;
  }
  //既に数字が入力されている場合は次へ
  if(v[i][j] != -1){
    rec(i,j+1,v);
    return;
  }
  for(int k = 1; k <= 9; k++){
    //その数字を入力しても問題ないかどうかをチェックして再帰。
    //数独なので、上下左右及び9マス内に同じ数字があるかどうか。
    if(check(i,j,k,v)){
      v[i][j] = k;
      rec(i,j+1,v);
      v[i][j] = -1; //初期値に一応戻す(戻さなくても動くはず)
    }
  }
}

ループパターン ループしてしまう場合は、既にチェックしたかどうかを管理する必要がある。

  //訪れたことがあったらこれ以上探索しない。
  vector > visited;
  void rec(int i,,...){
     if(<終了条件>){
        
     }
     int new_i = i + to[hoge];
     //遷移先が既に訪問済みの場合はこれ以上探索しない
     if(visited[new_i]) return;
     visited[new_i] = true;
     //訪問済みじゃない場合は探索を続ける。
     rec(new_i ...);
  }

まとめ

  • 問題パターンごとに書き方を考えておくと楽ですよ。

個人的には、Project Euler100問解いた時に、全探索系の問題を考えまくったので、その経験が結構生きてる気がする。 あと、夢の中でDPを解いてたほどDPについて考えまくった週があったりとか、結局遠回りながらも時間をかけて考えないと成長できないんだよなぁと思ったり。 (だからって時間をかけるのがいいかというと、社会人的にこればかりに時間をかけられないので、いろいろ難しいところ・・・)

とまぁ、最近微妙なエントリしか書いてないなと思いつつも、このエントリも微妙なままこれで終わる。