スポンサーサイト

--.--.-- --:--  スポンサー広告

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

| - | - | ↑ページトップ |




幅優先探索 Breadth First Search

2008.02.22 16:00  探索 II

searchBFS.gif


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

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

プログラムの説明

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

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 }


スポンサーサイト

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(1) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

管理人のみ閲覧できます

このコメントは管理人のみ閲覧できます

| | 2016.12.18 02:43

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。