スポンサーサイト

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

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

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




反復深化 Iterative Deepening

2008.02.22 19:02  探索 II

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

searchIDP.gif


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

searchLimitCut.gif


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

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

heuristic1.gif


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

heuristic2.gif


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 }




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

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

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

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

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

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

↑ページトップ

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