幅優先探索 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 }