反復深化 Iterative Deepening

単純な深さ優先探索では初期状態から最終状態までの最短経路を求めることは不可能でした。しかし、深さを制限した深さ優先探索（深さ制限探索）を繰り返すことによって最短経路を求めることができます。つまり深さの制限 d を増加させながら深さ制限探索を繰り返します。このアルゴリズムを反復深化といいます。




反復深化及び深さ制限探索では高速化を図るために探索空間（探索木）の枝を刈ることが重要になります。探索アルゴリズムでは、現在の状態 n から最終状態までの最短経路コスト h を見積もることができれば枝を刈ることができます。つまり、現在の状態の深さ g に「ここからあと最低でも h 回の状態変化は必要だろう」というコストh を加えた値が深さの制限 d を超えた場合、そこで探索を打ち切ることができます。h は見積もりであって正確な値である必要はありません。h の値が大きいほど探索の速度は上がりますが、大きく見積もりすぎると解を見逃してしまいます。h は以後必ず必要となる明確なコストを表し下限値と呼ばれます。




では８パズルにおける下限値を考えてみましょう。

候補１　h1 = 最終状態の位置にないパネルの数
例えば、以下の状態で最終状態の位置にないパネルの数は 7 となります。




候補２ h2 = 各パネルにおける最終状態までのマンハッタン距離の総和
マンハッタン距離とは「斜めに進むことができない上下左右だけの移動の総距離による２点間の距離」をいいます。例えば、以下の状態での各パネルの最終状態までのマンハッタン距離は、
パネル１ = 2
パネル２ = 1
パネル３ = 1
パネル４ = 3
パネル５ = 2
パネル６ = 3
パネル７ = 1
パネル８ = 0
となり、その総和は 13 となります。




h1 も h2 も下限値として用いることができますが h2 の方が h1 よりも値が大きいので、優位であると言えます。

もちろんこれらの下限値は、深さ優先探索や深さ制限探索にも適用できます。

001 #include<iostream>
002 #include<cmath>
003 using namespace std;
004 #define LIMIT 30
005 
006 struct Puzzle{ char cont[9]; int space; };
007 
008 Puzzle puzzle;
009 int limit, path[LIMIT], MD[9][9];
010 static const int dx[4] = {-1, 0, 1, 0};
011 static const int dy[4] = {0, -1, 0, 1};
012 static const char direction[4] = {'d', 'r', 'u', 'l'};
013 
014 int getHeuristic(){
015     int sum = 0;
016     for ( int i = 0; i < 9; i++ ){
017         if ( puzzle.cont[i] == 'x' ) continue;
018         sum += MD[i][puzzle.cont[i]-'1'];
019     }
020     return sum;
021 }
022 
023 bool isTarget(){
024     for ( int i = 0; i < 8; i++ ){
025         if ( puzzle.cont[i] != '1' + i ) return false;
026     }
027     return true;
028 }
029 
030 bool dfs(int depth, int prev){
031     if ( isTarget() ) return true;
032     if ( depth + getHeuristic() > limit ) return false;
033     
034     int px, py, tx, ty;
035     Puzzle tmp;
036     px = puzzle.space / 3;
037     py = puzzle.space % 3;
038     
039     for ( int r = 0; r < 4; r++ ){
040         tx = px + dx[r];
041         ty = py + dy[r];
042         if ( max(prev, r)-min(prev, r) == 2 ) continue;
043         if ( tx < 0 || ty < 0 || tx >= 3 || ty >= 3 ) continue;
044         tmp = puzzle;
045         puzzle.cont[px*3+py] = puzzle.cont[tx*3+ty];
046         puzzle.cont[tx*3+ty] = 'x';
047         puzzle.space = tx*3+ty;
048         if ( dfs( depth+1, r ) ) { path[depth] = r; return true;}
049         puzzle = tmp;
050     }
051     return false;
052 }
053 
054 void solve(){
055     for ( limit = getHeuristic(); limit <= LIMIT; limit += 2 ){
056         if ( dfs(0, -100) ){
057             for ( int i = 0; i < limit; i++ ) cout << direction[path[i]];
058             cout << endl;
059             return;
060         }
061     }
062     cout << "unsolvable" << endl;
063 }
064 
065 void input(){
066     for ( int i = 0; i < 9; i++ ){
067         cin >> puzzle.cont[i]; cout << puzzle.cont[i] << " ";
068         if ( puzzle.cont[i] == 'x' ) puzzle.space = i;
069     }
070     cout << endl;
071 }
072 
073 main(){
074     for ( int i = 0; i < 9; i++ ){
075         for ( int j = 0; j < 9; j++ ){
076             MD[i][j] = abs(i/3-j/3) + abs(i%3-j%3);
077         }
078     }
079     input();
080     solve();
081 }

プログラムには明らかに無駄があります。高速化を図るのであれば、毎回下限値を計算するのではなく、状態変化した際にマンハッタン距離の差分を計算するとよいでしょう。

幅優先探索 Breadth First Search

幅優先探索はグラフにおける幅優先探索と同様に動作し（グラフのノードを状態とみなします）、幅広く状態変化を行います。つまり、現在の状態から可能な全ての状態変化を行い新しい状態を作ります。この探索をシステマティックに行うために、状態変化によってつくられた新しい状態をキューに追加し、探索を展開するためにキューの先頭の状態からさらに状態変化を繰り返します。一度生成した状態を再び作らないために、生成された状態を全て記録する必要があります。幅優先探索は、問題に解が存在すれば初期状態から最終状態までの最短の経路を求めます。

それでは、８パズルを幅優先探索で解いてみましょう。

プログラムの説明

以下のプログラムは、例えば

2 8 3
x 1 5
4 7 6

というような、'x' をスペースとみなしたパズルを読み込み、

ldruuldlu

という、l = left, r = right, u = up, d = down の方向へパネルを移動するような、パズルを解くための経路を出力します。


基本的なデータ構造や状態変化の方法などは、深さ優先探索のプログラムと同様です。幅優先探索では生成された状態を記録するためのバッファが必要です。これをmapを使って実現するためには、パズルをクラスとして定義し、異なるパズルを比較するための演算子を定義します。パズルを対応した数字に変換するハッシュ関数を用いれば演算子は必要なくさらに効率化できるでしょう。また、幅優先探索では探索を展開するために生成された状態が新しいものであればそれをキューに追加します。

001 #include<iostream>
002 #include<cmath>
003 #include<string>
004 #include<map>
005 #include<queue>
006 using namespace std;
007 #define LIMIT 30
008 
009 struct Puzzle{
010     char cont[9];
011     int space;
012     string path;
013     bool operator < ( const Puzzle &p ) const{
014         for ( int i = 0; i < 9; i++ ){
015             if ( cont[i] == p.cont[i] ) continue;
016             return cont[i] > p.cont[i];
017         }
018         return false;
019     }
020 };
021 
022 int limit;
023 static const int dx[4] = {-1, 0, 1, 0};
024 static const int dy[4] = {0, -1, 0, 1};
025 static const char direction[4] = {'d', 'r', 'u', 'l'};
026 
027 bool isTarget(Puzzle puzzle){
028     for ( int i = 0; i < 8; i++ ){
029         if ( puzzle.cont[i] != '1' + i ) return false;
030     }
031     return true;
032 }
033 
034 void bfs(Puzzle s){
035     queue<Puzzle> Q;
036     map<Puzzle, bool> V;
037     Puzzle u, v;
038     s.path = "";
039     Q.push(s);
040     V[s] = true;
041     
042     while( !Q.empty() ){
043         u = Q.front(); Q.pop();
044         if ( isTarget(u) ){
045             cout << u.path << endl;
046             return;
047         } else if ( u.path.size() > LIMIT ) break;
048         
049         int sx, sy, tx, ty;
050         sx = u.space/3;
051         sy = u.space%3;
052         
053         for ( int r = 0; r < 4; r++ ){
054             tx = sx + dx[r];
055             ty = sy + dy[r];
056             if ( tx < 0 || ty < 0 || tx >= 3 || ty >= 3 ) continue;
057             v = u;
058             v.cont[u.space] = u.cont[tx*3+ty];
059             v.cont[tx*3+ty] = 'x';
060             v.space = tx*3+ty;
061             if ( !V[v] ){
062                 V[v] = true;
063                 v.path += direction[r];
064                 Q.push(v);
065             }
066         }
067     }
068     cout << "unsolvable" << endl;
069 }
070 
071 main(){
072     Puzzle in;
073     for ( int i = 0; i < 9; i++ ){
074         cin >> in.cont[i];
075         if ( in.cont[i] == 'x' ) {
076             in.space = i;
077         }
078     }
079     
080     bfs(in);
081 }

深さ優先探索 Depth First Search

深さ優先探索はグラフにおける深さ優先探索と同様に動作し（グラフのノードを状態とみなします）、初期状態から最終状態に至るまで可能な限り状態変化を繰り返します。ただし、

• 現在の状態からそれ以上状態変化が不可能な場合


• 状態変化が一度生成した状態を生成してしまう場合


• 問題の性質からこれ以上探索しても明らかに無駄があると断定できる場合

などは探索（状態変化）を打ち切って前の状態に戻ります。これをバックトラックといいます。また探索を打ち切るので、「枝を刈る」とも表現されます。

深さ優先探索の深さに制限を持たせた方法を深さ制限探索といいます。つまり、探索の深さがある定められた値 d に達したところで探索を打ち切ります。問題の性質から深さを制限することができれば探索を高速化することができます。

それでは、８パズルを単純な深さ優先探索（深さ制限探索）で解いてみましょう。

以下のプログラムは、例えば

2 8 3
x 1 5
4 7 6

というような、'x' をスペースとみなしたパズルを読み込み、

dlurdlurdlurdlurdluruldlu

という、l = left, r = right, u = up, d = down の方向へパネルを移動するような、パズルを解くための経路を出力します。

このプログラムでは、８パズルを9つの要素を含むchar型の配列で表現しています。生成した状態を保存していないので、一度生成した状態へ状態変化する場合がありますが、深さを３０と制限し、状態変化のとき１つ前の状態へ戻らないようにする（プログラム033行目）ことで、探索の空間を狭めています。

001 #include<iostream>
002 #include<cmath>
003 using namespace std;
004 #define LIMIT 30
005 
006 struct Puzzle{ char cont[9]; int space; };
007 
008 Puzzle puzzle;
009 int cost, path[LIMIT];
010 static const int dx[4] = {-1, 0, 1, 0};
011 static const int dy[4] = {0, -1, 0, 1};
012 static const char direction[4] = {'d', 'r', 'u', 'l'};
013 
014 bool isTarget(){
015     for ( int i = 0; i < 8; i++ ){
016         if ( puzzle.cont[i] != '1' + i ) return false;
017     }
018     return true;
019 }
020 
021 bool dfs(int depth, int prev){
022     if ( isTarget() ) { cost = depth; return true;}
023     if ( depth > LIMIT ) return false;
024     
025     int px, py, tx, ty;
026     Puzzle tmp;
027     px = puzzle.space / 3;
028     py = puzzle.space % 3;
029     
030     for ( int r = 0; r < 4; r++ ){
031         tx = px + dx[r];
032         ty = py + dy[r];
033         if ( max(prev, r) - min(prev, r) == 2 ) continue;
034         if ( tx < 0 || ty < 0 || tx >= 3 || ty >= 3 ) continue;
035         tmp = puzzle;
036         puzzle.cont[px*3+py] = puzzle.cont[tx*3+ty];
037         puzzle.cont[tx*3+ty] = 'x';
038         puzzle.space = tx*3+ty;
039         if ( dfs( depth+1, r ) ) { path[depth] = r; return true;}
040         puzzle = tmp; // backtracking

041     }
042     return false;
043 }
044 
045 main(){
046     for ( int i = 0; i < 9; i++ ){
047         cin >> puzzle.cont[i];
048         if ( puzzle.cont[i] == 'x' ) puzzle.space = i;
049     }
050     if ( dfs(0, -100) ){
051         for ( int i = 0; i < cost; i++ ) cout << direction[path[i]];
052         cout << endl;
053     } else {
054         cout << "unsolvable" << endl;
055     }
056 }

単純な深さ優先探索の特徴

• 最短の解を求めるとは限らない


• 無駄な探索をしてしまうため計算量が大きい


• 枝を刈らなければ最悪の場合（解がない場合など）は全探索してしまう


• 深さを制限しなければ、解を見逃し堂々巡りに陥ってしまう


• など

探索アルゴリズム

与えられた問題が解析的に解くことが困難な（不可能な）場合には、試行錯誤を繰り返すことによって解を探さなくてはなりません。しかし多くの場合、探索しなければならない空間は膨大であり、どのような経路が解へと導くかは不明です。従って、無駄な探索を避けたり、より速く解を見つけるための工夫が必要です。それらを体系的に行う方法が探索アルゴリズムであり、問題や状況に応じて様々なアルゴリズムが考えられます。

探索のアルゴリズムは、与えられた初期状態から最終状態への状態変化の列を求めます（このような列の長さをコストと言うことにします）。従って探索アルゴリズムでは「状態」そして「状態変化」という概念が重要になります。

例えば、８パズルを探索アルゴリズムで解くことを考えましょう。８パズルとは上図のような１つの空白を含む３×３のパネルを上下左右にスライドさせることによって、パズルを完成させます。

ここで、全てのパネルと空白の位置情報が「状態」であり、パネルを上下左右に動かすことが「状態変化」に相当します。




多くの探索アルゴリズムでは、一度生成した状態を再度生成しないようにするために、探索の空間は木構造になります。木（またはグラフ）のノードが状態を表し、エッジが状態変化を表します。

探索アルゴリズム

• 深さ優先探索 Depth First Search(DFS)


• 幅優先探索 Breadth First Search(BFS)


• 反復深化 Iterative Deepening


• Ａ*アルゴリズム A* Algorithm


• 双方向幅優先探索 Bidirectional BFS

探索で解く問題の例

8クイーン問題 Eight Queens Problem

8クイーン問題とは、8 × 8 のチェス版に、どのクイーンも他のクイーンを襲撃できないように、8 つのクイーンを配置する問題です。(※チェスでは、クイーンは以下のように襲撃することができます)

この問題を解くための最も素朴な方法が、8 つのクイーンを全ての組み合わせについて配置し、上記のコンディションを満たすかをチェックする方法です。つまり、8 × 8 = 64 のマスから、8 個選ぶ組み合わせなので、

₆₄C₈ = 4,426,165,368 通り

無論、この天文学的な数の組み合わせを全て調べることは現実的ではありません。まず、２つ以上のクイーンが同じ行には配置できないので、１行に１つのクイーンしか配置できないことを考えれば、

8⁸ = 16,777,216 通り

と大幅に組み合わせ数を少なくすることができます。さらに、２つ以上のクイーンが同じ列に配置できないことを考えれば、1 行目は 8 つの候補、2 行目は 7 つの候補、3 行目は 6 つの候補、、、8 行目は 1 つの候補、となるので、

8! = 40,320 通り

と導くことは容易です。

しかし、上記の組み合わせを全て調べるよりも、以下のようにバックトラッキングアルゴリズムを適用すれば、さらに効率的に 8 クイーン問題を解くことができます。

	1 行目の任意のコマに、クイーンを配置する
	１行目に配置したクイーンによって襲撃されない２行目のコマに、クイーンを配置する
	...
	全てのクイーンが他のどのクイーンも襲撃しないように、i 個のクイーンを最初の i 行に配置したとすれば、前の i 個のどのクイーンにも襲撃されない (i + 1) 行目のコマに、クイーンを配置する
	もしも、そのようなコマが (i + 1) 行目のコマに存在しなければ、i 行目に戻り i 行目に配置するクイーンのための他の襲撃されないコマを探し（もしそのようなコマがなければ、さらに (i - 1) 行目に戻る）、探索を続行します。

このアルゴリズムの実装では、コマ (i, j) が他のクイーンによって襲撃されているか否かを記録するために、以下の配列を用意します。

row[8]	row[x] が NOT_FREE ならば、row[x] は襲撃されている
col[8]	col[x] が NOT_FREE ならば、col[x] は襲撃されている
dpos[15]	dpos[x] が NOT_FREE ならば、dpos[x] は襲撃されている
dneg[15]	dnedg[x] が NOT_FREE ならば、dneg[x] は襲撃されている

つまり、row[i]、col[j]、dpos[i+j]、dneg[i-j+N-1] のいづれかが NOT_FREE であれば、コマ (i, j) が襲撃されていることになります。逆に考えれば、row[i]、col[j]、dpos[i+j]、dneg[i-j+n-1] すべてが FREE のとき、クイーンを配置することができます。各配列のインデック（i, j, i+j, i-j+N-1）の関係は下図を参照して下さい。

row: x = i	col: x = j

dpos: x = i + j	dneg: x = i - j + (N - 1)

// @author yutaka C++
// N queens problem: 全ての可能な配置と総数を出力
#include<iostream>
using namespace std;

#define N 8
#define FREE -1
#define NOT_FREE 1

int row[N], col[N], dpos[2*N-1], dneg[2*N-1];
int counter;

void initialize(){
    for ( int i = 0; i < N; i++ ){ row[i] = FREE, col[i] = FREE; }
    for ( int i = 0; i < 2*N - 1; i++ ) { dpos[i] = FREE; dneg[i] = FREE; }
}

void printBoard(){
    for ( int i = 0; i < N; i++ ){
        for ( int j = 0; j < N; j++ ){
            cout << (( row[i] == j ) ? "Q" : ".");
        }
        cout << endl;
    }
    cout << endl;
}

void recursive( int i ){
    if ( i == N ){ // SUCCESS
        counter++;
        printBoard(); return;
    }
    
    for ( int j = 0; j < N; j++ ){
        // if (i, j) is attacked by other queens, continue
        if ( col[j] == NOT_FREE || dpos[i+j] == NOT_FREE ||
        dneg[i-j+N-1] == NOT_FREE ) continue;
        // put a queen on (i, j)
        row[i] = j; col[j] = dpos[i+j] = dneg[i-j+N-1] = NOT_FREE;
        // try next row
        recursive( i + 1 );
        // remove the queen from (i, j)
        row[i] = col[j] = dpos[i+j] = dneg[i-j+N-1] = FREE;
    }
    
    // FAIL
}

main(){
    initialize();
    counter = 0;
    recursive( 0 );
    cout << counter << endl;
}

Backtracking バックトラック

とてつもない数の"見込みのある解"の中から、解を探さなければならないというような問題は数多く存在します。これらの問題を解くアルゴリズムは、ある起点から出発し、特定の経路を探索することによって、解を見つけます。

しかし、多くの問題では、どのような経路が解へと導くかが不明です。このような問題を解くためには、可能な経路をすべて探索（総当り）する方法が考えられますが、探索しなければならない空間が膨大な場合には、無駄な探索を避けるためのテクニックが必須となります。

バックトラッキング Backtracking は、見込みのあるすべての探索空間を体系的（計画的）に探索する方法です。バックトラッキングでは、今いる地点からこれ以上探索が不可能と分かった時、または問題の定義によってこれ以上探索しても無駄であると断定できる時に、そこで探索を打ち切り、前の地点に戻って探索を続行します。

グラフにおける Depth First Search が、バックトラックアルゴリズムの良い例となります。

バックトラックが適用できる問題の例

• 8クイーン問題