一介のCS人の綴り

トップ > プログラミング > プログラミングTips
Tweet

今回の主題は?

今回は、全探索のひとつである深さ優先探索(縦型探索)についてまとめます。

ここでは、競技プログラミング初心者が実力を高めていくのに必須かつ基本的なプログラミングテクニックをまとめていく記事となります。

プロコンテクを学ぼう! - No.2

深さ優先探索とは

ある状態から先へ先へと遷移できなくなるまで状態を進め、行き止まりになったら1つ前の状態に戻って(バックトラック;backtrack)別の枝に進むという全探索の一種である。深さ優先探索もしくは縦型探索、 またDepth-First Searchの頭文字からDFSとも呼ばれる。

再帰版

再帰関数を利用すると、条件を満たさなくなるまで再帰を続けることができるため深さ優先探索が実現可能である。 現在の状態を引数nowとして再帰ごとに更新していきながら、そのnowが条件を満たさなくなった場合処理をやめて値を返す。

引数nowが条件を満たす限りは、現在の状態から遷移できるすべての状態について再帰して状態を進めていく。 このとき、再帰の深度が深すぎるとスタックオーバーフローしてしまうため、注意が必要である。

int dfs(int now){
    if(nowが終了条件を満たす) return now;

    int ans = (更新され、かつ答えとしてあり得ない数値);
    for(int i = 0; i < (次の状態の総数); i++){
        int next = (i番目の状態);
        if(nextが条件を満たす) ans = update(dfs(next), ans);
    }

    return ans;
}
        

以上が、最強最速アリゴリズマー養成講座に掲載のある深さ優先探索のプログラムを参考に記述した、擬似プログラムである。 再帰関数を用いた深さ優先探索は、この記事のNo.1: グリッド(格子)上走査の例題にも実装しているので参考にしていただきたい。

スタック版

スタック版では、再帰版における処理をスタックを用いて非再帰に表現したものである。 再帰版では、再帰が深すぎるとスタックオーパーフローを起こしてしまうが、スタック版では十分なスタックの大きさを準備することが可能である。 また、スタック版ではループを用いて表現できるため、再帰を用いるより速度が向上することも考えられる。

しかし、chokudaiさんのブログより「深さ優先探索を再帰関数なしで書くと速度はどうなるか? - chokudaiのブログ

        stack<CLASS> states;
        int ans = (初期値);
        states.push(初期状態);

        while(!states.empty()){
            CLASS now = states.top();
            states.pop();
            // nowの処理

            for(int i = 0; i < (次の状態の総数); i++){
                CLASS next = (nowから遷移するi番目の状態);
                if(nextが条件を満たす) states.push(next);
            } 
        }
        

スタック版では、現在の状態をどのように保持するのかなど、再帰版より実装が重いのが難点である。 したがって、実装の段階で再帰が深くまでいかないことが想定されるのであれば、再帰を用いて実装したほうが楽である。

Bit全探索版

Bit全探索では2進数の特徴を用いて、各ノードの分岐が2つである場合に深さ優先探索を用いることができる。 下の図からも分かるように、\(n\)個の要素の0,1の組み合わせは0~\(2^{n}-1\)までの間の数のビットの0,1の配置によりすべて網羅される。 したがって、それぞれの数についてビットが立っているかどうかを確認し、処理をすることで全探索ができる。

グリッド(格子)上走査
//n個の0,1全探索: 0~2^n -1の間をループ
for(int i = 0; i < (1 << n); i++){
        int bit = i;
        while(bit){
            if(bit & 1){ // 2^0の位が1なら処理
            //処理
        }
        bit >>= 1; //右に1ビットシフト
    }
}
        

このように、比較的容易に深さ優先探索が記述できる場合が多いのがこの実装手法である。 しかし、この手法に慣れないうちはパッと見ではプログラムの挙動が追えないため、デバッグに苦労する可能性もはらんでいる。

例題: AOJ0033 Ball

問題リンク

AIZU ONLINE JUDGE #0033 Ball

他の解説サイト

再帰版

再帰関数dfs()を用いて実装している。 配列balls[]に入力された玉の順序が格納されており、それを引数idxによって順に指定し、条件を満たす限り再帰を続けている。 引数b,cは筒B,Cそれぞれの最上部の玉の数値を保持しており、それよりballs[idx]が大きければ問題の条件をみたす。 筒BまたはCのいずれかでも成り立つことが分かった場合、trueを返し、どちらも満たさなければfalseを返すようになっている。

#include <iostream>
using namespace std;
 
int balls[10];
 
bool dfs(int idx, int b, int c){
    if(idx > 9) return true;
     
    bool ok = false;
    if(b < balls[idx]){
        ok = dfs(idx+1, balls[idx], c);
    }
    if(c < balls[idx]){
        ok = dfs(idx+1, b, balls[idx]);
    }
    return ok;
}
 
int main() {
    int n; cin >> n;
    while(n--){
        for(int i = 0; i < 10; i++){
            cin >> balls[i];
        }
          
        if(dfs(0, 0, 0)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}
        

スタック版

ここでは、再帰版のプログラムをスタックを用いて非再帰の形で実装している。 現在取り扱っている玉のidxと、筒B,Cの最上位の玉の値をtuple<int, int, int>より表現し、それをスタックに積むことでそれぞれの状態を格納している。 条件を満たす限り筒に玉を入れていき、最後まで入れることができる状態が一つでもあれば探索を終了し、YESを出力している。。 また、全ての状態を探索し、どの状態についても最後まで入れることができなかった場合はループを終了し、NOを出力している。

#include <iostream>
#include <stack>
#include <tuple>
using namespace std;
 
int main() {
    int n, balls[10]; cin >> n;
    while(n--){
        for(int i = 0; i < 10; i++){
            cin >> balls[i];
        }
         
        enum {IDX, B, C};
        stack<tuple<int, int, int> > states;

        bool sortable = false;
        states.push(make_tuple(0,0,0));
        while(!states.empty()){
            tuple<int, int, int> now = states.top();
            states.pop();

            int idx = get<IDX>(now);
            if(idx < 10){
                if(get<B>(now) < balls[idx]){
                    if(idx == 9){
                        sortable = true; break;
                    }
                    states.push(make_tuple(idx+1,balls[idx],get<C>(now)));
                }
                if(get<C>(now) < balls[idx]){
                    if(idx == 9){
                        sortable = true; break;
                    }
                    states.push(make_tuple(idx+1,get<B>(now),balls[idx]));
                }
            }
        }

        if(sortable) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

        

Bit全探索版

10個の玉を筒BとCへ順番に入れていき、現在の各筒の一番上の玉より値が大きいかどうかを確認するという手法で実装している。 どの玉をどちらに入れるかは変数bitの2進数によるフラグを利用し、0なら筒Bへ、1なら筒Cへ入れ、 配列top[]に保持している現在の各筒の一番上の玉の値と比較し、それより小さかった場合は満たさないため次の状態へ移行している。

#include <iostream>
using namespace std;
 
int main() {
     
    int n, balls[10]; cin >> n;
    while(n--){
        for(int i = 0; i < 10; i++){
            cin >> balls[i];
        }
         
        bool sortable = false;
        for(int i = 0; i < (1 << 10); i++){
            int bit = i;
            bool ok = true;
             
            int top[2] = {0,0}; //top[0]: B, top[1]: C
            for(int j = 0; j < 10; j++){
                if(top[bit & 1] > balls[j]){
                    ok = false; break;
                }
                top[bit & 1] = balls[j];
                bit >>= 1;
            }
             
            if(ok) {
                sortable = true; break;
            }
        }
         
        if(sortable) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}
        

練習問題

参考

Comments

Top