ACM-ICPC

バックトラック法


☆関連問題☆
2004年 B問題 Red and Black
2004年 C問題 Unit Fraction Partition
2001年 C問題 Jigsaw Puzzles for Computers
2006年 D問題 カーリング 2.0

後戻り法(バックトラック法)は、簡単に言うと、「とりあえず行けるところまで進み、ダメだったら戻る、これを繰り返す」という探索方法です。再帰と密接な関係にあります。
これを使う問題は例年1,2問ほど必ず出題されるので、基本的なパターンをしっかり抑えておきましょう。

↑mia2的バックトラック法のイメージ


バックトラック関数

バックトラック法を扱う問題では、たいてい次のようなバックトラック関数を書くことになります。
void backtrack( ... ) {
 if( 終了条件 ) {
   終了時の処理をする。
   return;
 }
 ...
 backtrack( ... );  /* 再帰 */
 ...
}

再帰で呼び出す方の関数には、もとの引数の値を少し変えた値を渡すのが一般的です。

また、これは私の場合はですが、バックトラック関数が値を返さないvoid型なので、その中では大域変数をいじる場合が多いです。

グラフの中を歩き回る。

例えば、次の問題を考えてみよう。
n個の町があり、それぞれの町同士をつなぐ道がm本ある。町sから町gへ道を使っていくとして、
同じ町を2回以上通らないようなルートはいくつあるか答えるプログラムをかきなさい。
ただしnは10以下の正整数、s,gは1以上n以下の整数で、sとgは異なると仮定してよい。

データは町の数n、道の数m、スタートs、ゴールgに続いて、道の情報がm行続く。それぞれの行は
2つの整数からなり、道がつないでいる町を表す。

例えば、
4 5 1 4
1 2
2 3
3 4
1 3
2 4
のようなデータなら、4通りのルートがあるので、4が正解。

では、入力部分から。
 scanf("%d%d%d%d", &n,&m,&s,&g);
実際の問題なら、n,m,s,gがゼロなら終了、といったところでしょうか。

ここで、読み込みながらグラフの隣接行列を作ります。
隣接行列とは、点iと点jがつながっているとき、i行j列目は1、そうでなければ0という行列です。普通は辺の長さ(重み)をいれたりします。

例えば上の例ならこうなります。
0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0

実際に作ってみましょう。
ここはCでしか書きませんが、他の言語の人は上手く変えてください。
 for(x = 1; x <= n; x++)for(y = 1; y <= n; y++){ /* 初期化 */
   map[x][y] = 0;
 }
 for(i = 0; i < m; i++) {
   scanf("%d%d", &x, &y);
   map[x][y] = map[y][x] = 1;
 }

ここで、2次元配列mapは、大域変数で宣言します。1〜nまでを使うので、サイズを11にするのをお忘れなく。

次に、バックトラック関数を書いてみましょう。引数pは、今いる町の番号です。
void walk( int p ) {
 ...
}

終了条件はもちろんpとgが等しいことです。着いたら1つルートを見つけたということでカウントアップします。

 if(p == g) {
   count++;
   return;
 }

そうでなければ、道でつながっている町の中でまだ訪れてないものを1つ選び、そこに行ってみます。

 visited[p] = 1;
 for(q = 1; q <= n; q++) {
   if(map[p][q] && !visited[q])
     walk(q);
 }
 visited[p] = 0;

g, count, visited[]も大域で宣言します。

最後に、mainからの呼び出し部分は、次のようにします。
 count = 0;
 walk( s );
 printf("%d\n", count);

まとめるとこのようになります。
ソースコード




組み合わせ問題

ある古代ピラミッドの王室には、財宝が詰まった箱が10個一列に並んでいる。
トレジャーハンターのMimutea氏は、そのありかをついに突き止めた。
箱に入っている財宝の価値はまちまちで、1〜10000までの評価がつけられる。
彼は合計の価値をできるだけ多く持ち帰りたいが、2つの連続した箱を取り去ると
王室に仕掛けられたトラップが発動して閉じ込められてしまうことがわかっている。
全ての宝箱の価値が与えられたとき、最高でどれくらい持ち帰れるかを
計算するプログラムをつくりなさい。

問題が意味不明だが、要は2つ続けて取ってはいけないということ・・・。

バックトラック関数は次のようになります。
void backtrack(int k, int sel, int value)
{
 if(k == 10){
   if(max < value)
     max = value;
   break;
 }
 if(sel == 0)
   backtrack(k+1, 1, value+t[k]);
 backtrack(k+1, 0, value);
}

kは今見ている箱、selは前の箱を選んだかどうか、valueはそれまでの合計。
もしselが1なら、前の箱(k-1番目)を選んでいるのでk番目の箱は選べません。0なら選べます。
全ての箱を見終わったらkが10になるので、その時点でmaxを更新します。

残された仕事は最初の呼び出しです。kとvalueは0でよいでしょう。ではselはどうすればよいでしょう?
結論を言うと、これも0です。最初の(0番目の)箱は無条件に取ってよいので。

というわけで、
 max = 0;
 backtrack(0, 0, 0);
 printf("%d\n", max);
と書けばよいでしょう。

え?

そんなことしなくても
OXOX・・・・

XOXO・・・・
だけ調べればいいじゃないかって?

そうすると下のような場合に対応できません!
1  1  1  9999  1  1  9999  1  1  1