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

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

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


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


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


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


• など