深さ優先探索 Depth First Search
2008.02.21 14:29 探索 II

深さ優先探索はグラフにおける深さ優先探索と同様に動作し(グラフのノードを状態とみなします)、初期状態から最終状態に至るまで可能な限り状態変化を繰り返します。ただし、
- 現在の状態からそれ以上状態変化が不可能な場合
- 状態変化が一度生成した状態を生成してしまう場合
- 問題の性質からこれ以上探索しても明らかに無駄があると断定できる場合
などは探索(状態変化)を打ち切って前の状態に戻ります。これをバックトラックといいます。また探索を打ち切るので、「枝を刈る」とも表現されます。
深さ優先探索の深さに制限を持たせた方法を深さ制限探索といいます。つまり、探索の深さがある定められた値 d に達したところで探索を打ち切ります。問題の性質から深さを制限することができれば探索を高速化することができます。
それでは、8パズルを単純な深さ優先探索(深さ制限探索)で解いてみましょう。
以下のプログラムは、例えば
2 8 3
x 1 5
4 7 6
というような、'x' をスペースとみなしたパズルを読み込み、
dlurdlurdlurdlurdluruldlu
という、l = left, r = right, u = up, d = down の方向へパネルを移動するような、パズルを解くための経路を出力します。
このプログラムでは、8パズルを9つの要素を含むchar型の配列で表現しています。生成した状態を保存していないので、一度生成した状態へ状態変化する場合がありますが、深さを30と制限し、状態変化のとき1つ前の状態へ戻らないようにする(プログラム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 }
単純な深さ優先探索の特徴
- 最短の解を求めるとは限らない
- 無駄な探索をしてしまうため計算量が大きい
- 枝を刈らなければ最悪の場合(解がない場合など)は全探索してしまう
- 深さを制限しなければ、解を見逃し堂々巡りに陥ってしまう
- など
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |