■総当たりでパターンのツリーを作成
総当たりパターンのツリー
よくアルゴリズムの例題などで用いられるバックトラック。
「マッチするパターンをすべて列挙してそれを評価したい」というのが今回の目標。
これをやる上で、何が問題かというと、
「普通のバックトラックは一回やって、ハイ終わり。」
であること。つまり、それでは後から評価できない。評価自体に時間がかかる場合、枝刈りをしてから評価したい。そのためには、総当たりパターンのツリーができてないといけない。
そこで、「総当たりパターンのツリー作成」を行う。
今回の問題はこんな感じ。
「ある配列とパターンの集合が与えられたとき、その配列をすべてパターンで置換できるような組み合わせをすべて列挙する。」
なんじゃそりゃ？という感じなので例。
ある配列： 1 2 3 4 1 2 3 4 5 1 2 3 4
パターンの集合: { (1 2 3 4), (5 1 2 3 4), (1 2 3 4 5), (5) }
これらのパターンで置換する全パターンは
1 2 3 4 , 1 2 3 4 , 5 1 2 3 4
1 2 3 4 , 1 2 3 4 , 5 , 1 2 3 4
1 2 3 4 , 1 2 3 4 5 , 1 2 3 4
となる。これをツリーで表すと、
1 2 3 4
/ \
1 2 3 4 1 2 3 4 5
/ \ \
5 \ 1 2 3 4
/ \
1 2 3 4 5 1 2 3 4
となる。このツリーを作りたい。
やること
変数・関数の定義
まず、入力として、パターンを当てはめるもとの配列とすべてのパターンを決める。
当てはめる配列は１次元配列、パターンの集合は二次元配列で定義する。
ある配列： vector<int> list;
パターンの集合: vector< vector<int> > pattern_array;
pattern_arrayの中身はこんな感じ。
1 2 3 4
5 1 2 3
1 2 3 4 5
5
次に、ツリーのノードの定義をする。今回必要なメンバは、
vector<int> pattern; /* マッチさせたパターン */
vector<int> rest; /* 残りのパターン */
vector<node*> children; /* 子ノードへのリンク */
node* parent; /* 親ノードへのリンク */
さらに、これらのノードを格納するリストと、パスを保存するリストを定義する。
面倒なのでグローバル変数で。どうしても嫌な人はポインタで。
vector<node*> nodelist;
vector<node*> path;
定義する変数は以上で終わり。
次に、パターンを含むかどうか判別する関数(isMatchPattern)を定義する。
bool isMatchPattern( vector<int>& list, vector<int>& pattern, int start ){
for(int i=start,j=0; j<(int)pattern.size(); i++,j++){
if( list[i] != pattern[j] ){
return false;
}
}
return true;
}
ツリー作成
ここが肝心。基本的には深さ優先探索のように行う。深さ優先探索は再帰を使って
void DFS( ノードのポインタ ){
ノードをprintする
for( すべての子ノードに対して ){
DFS( 子ノードのポインタ )
}
}
のように書くことができる。ツリーを作成する場合には一般的に、
・親ノード
・子ノード
を設定する必要がある。今回は、
・マッチしたパターン
・残りのパターン
・全ノードのリスト
・子ノード
を設定する。
全体の流れは、
for( すべてのパターン ) {
if( マッチする ){
新しいノードを作る。
新しいノードのパターン、親、残りの配列、子ノードをセット
新しいノードをノードのリストに追加
if( 残りの配列がある ){
ノードのポインタ、残りの配列を渡して再帰的に
}
}
}
以下、ソースコード。
void genTree(node* t, vector<int>& list, vector< vector<int> >& pattern, int start ){
vector<int> temp;
node* p;
for(int i=0; i<(int)pattern.size(); i++){
if( isMatchPattern( list, pattern[i], start ) ){
p = new node;
/* pattern */
p->pattern = pattern[i];
/* rest */
for(int j=pattern[i].size(); j<(int)list.size(); j++){ temp.push_back( list[j] ); }
p->rest = temp;
temp.clear();
/* parent */
p->parent = t;
/* children */
t->children.push_back( p );
/* node list */
nodelist.push_back( p );
if( p->rest.size() != 0 ){
genTree( p, p->rest, pattern, start );
}
}
}
}
ポイントは以下の２つ。
・新しいノードはパターンがマッチした場合に初めて確保する。
・子ノード、親ノードの設定はすべて渡されたポインタ(t)に対して行う。
・再帰的に行う場合には、今のノードに対して行うので渡すポインタは作成したもの、すなわちp。
ついでに、ツリーを作るときの一般的な注意は
・ノードのリストはかならずポインタのリストで作る。今回はpをpush_backする。*pではない。
・デバッグの為にプリントする場合はprintf("%p¥n", p)を使う。coutは使うな!!
ということ。これではまった。
walk
ここで、使うwalkは通常の深さ優先のように単に、子ノードに対して再帰的に行うだけではいけない。なぜなら、書き出すのはルートからのパスであるため、一つ上に戻った際には、その差分しか書き出されない。従って、パスを保存しておき、そのパスにそってパターンを書き出すということを考える。
流れは以下の通り。
pathにpush
if( 子ノードがある )[
for( パス ){
print パターン
}
}
for( 子ノード ){
walk( 子ノードのポインタ )
}
pathからpop
パスからpopするタイミングは戻る際、すなわち、再帰の処理が終わった直後に行う。ソースは以下のようになる。
void walk( node* t ){
path.push_back(t);
/* print */
if( t->children.size() == 0 ){
for(int i=0; i<(int)path.size(); i++){
/* pattern */
for(int j=0; j<(int)path[i]->pattern.size(); j++){
printf("%d ", path[i]->pattern[j] );
} cout << ",";
}
cout << endl;
}
/* child */
for(int i=0; i<(int)t->children.size(); i++){
walk( t->children[i] );
}
path.pop_back();
}
ダウンロード
フリーです。ソースのみなので各自コンパイルしてください。C++です。STL使っているので、libstdc++が必要かもしれないです。
開発環境
とりあえず、動作確認は
debain woody gcc 3.3.5
mac OS X 10.4.8 gcc version 4.0.1 (Apple Computer, Inc. build 5250)
で行いました。他にもある程度行っているので、体外動くはずです。
カウンター
total -
today -
yesterday -
最終更新：2006/10/21
最終更新：2006年10月24日 23:38
